Most of the current proxy caching algorithms for streaming video media assume that users favor the beginning part of the media object. However, this assumption is questionable in highly interactive scenarios, such as e-Learning, where some parts of the video other than the prefix can also be popular. In this paper, a new segment-based proxy caching algorithm, named Popularity-wise Caching, is proposed for highly interactive streaming. It is designed to deal with arbitrary popularity distribution of media content. Simulations are performed using synthetic traces with different kinds and levels of user interactivity. The results show that the performance of current segment-based caching (Exponential caching and Soccer caching) degrade with increasing user interactivity, while Popularity-wise Caching can provide the lowest user startup latency for interactive requests and highest bandwidth saving for backbone network.