Streaming media objects have become widely used on the Internet, and the demand of interactive requests to these objects has increased dramatically. Typical interactive requests include fast forward and direct jumps. Unfortunately, most of existing streaming proxies are designed for sequential accesses, and only a few solutions have been proposed to maintain additional data structures in the proxy to support some interactive operations (such as fast forward) other than jumps, which are among the most common interactive requests from the clients. Focusing on interactive accesses, in this paper we present an analysis of streaming media workload collected from thousands of broadband users hosted by a major ISP. Our analysis shows that jump accesses (48%) and pauses (51%) are the dominant client interactive requests and that jump accesses often suffer serious delays due to slow buffering through the network. To support jump accesses effectively, we further propose a novel caching algorithm-DISC (Dynamic Interleaved Segment Caching), which trades cache performance for response time to client interactive requests. In this algorithm, segments of a media object are cached dynamically according to client access patterns. DISC can support direct jumps efficiently while ensuring timely prefetching of uncached segments for sequential accesses. Trace-driven simulations demonstrate that DISC outperforms other caching schemes significantly for interactive requests with only a small degradation in cache performance.