Partial caching of large media objects such as video files has been proposed recently as the caching of entire objects can easily exhaust the storage resources of a proxy server. In this paper the idea of segmenting video files into chunks and applying replacement decisions at the chunk level rather than on entire videos is examined. It is shown that a higher byte hit ratio (BHR) can be achieved by appropriately adjusting the replacement granularity. The price paid for the improved BHR performance is that the replacement algorithm takes a longer time to converge to the steady state BHR. For the segmentation of video into chunks two methods are presented. The Fixed Chunk Size segmentation scheme that is rather simple and reveals the basic trade-off between byte hit ratio (BHR) and responsiveness to changes of popularity; the Variable Chunk Size segmentation scheme that uses the request frequencies to dynamically adjust the size of the chunk and is shown to be capable of combining a small response time with high BHR. Moreover, a variation of the fixed chunk size segmentation scheme is presented, which is shown to improve its performance by switching between different chunk sizes. Video segmentation is also considered as a mechanism to provide for caching differentiation based on access costs. By employing access cost dependent chunk sizes an overall access cost reduction is demonstrated.