To support various bandwidth requirements for mobile multimedia services for future heterogeneous mobile environments, a transcoding video proxy is usually necessary to provide adapting video streams to mobile clients by not only transcoding videos to meet different needs on demand, but also caching them for later use. Traditional proxy technology is not applicable to a video proxy because it is less cost-effective to cache the complete videos to fit all kind of clients in the proxy server. In this paper, we propose the object relation graph (ORG) to manage the static relationships between video versions, and utilize the cached object relation tree (CORT) and replacement algorithm to manage video segments cached in the proxy dynamically. Experimental results show that the proposed algorithm significantly outperforms companion schemes in terms of the byte hit ratios.