Video objects are much larger in size than traditional web objects and tend not to be viewed in entirety. Hence, caching them partially is a promising approach. Also, the projected growth in video traffic over wireless cellular networks calls for resource-efficient caching mechanisms in the wireless edge to lower traffic over the cellular backhaul and peering links and their associated costs. An evaluation of traditional partial caching solutions proposed in the literature shows that known solutions are not robust to video viewing patterns, increasing object pool size, changing object popularity, or limitation in the resources available for caching at the wireless network elements. In this paper, to overcome the limitations, we propose a novel approach that adopts a flexible segmentation policy and generalizes both LRU and LFU when applied to segmented accesses, and in our simulations, is shown to significantly lower wireless backhaul traffic (by around 20-30% and in some cases even higher). © 2012 IEEE.