In a video-on-demand (VOD) system, it is desirable to provide the user with interactive browsing functions such as "fast forward" and "fast backward." However, these functions usually require a significant amount of additional resources from the VOD system in terms of storage space, retrieval throughput, network bandwidth, etc. Moreover, prevalent video compression techniques such as MPEG impose additional constraints on the process since they in- troduce inter-frame dependencies. In this paper, we devise methods to support variable rate browsing for MPEG-like video streams and minimize the additional resources required. Specifically, we con- sider retrieval for a disk-array-based video server and address the problem of distributing the retrieval requests across the disks. Our overall approach for interactive browsing comprises (1) a storage method, (2) placement and sampling methods, and (3) a playout method, where the placement and sampling methods are two alternatives for video segment selection. The segment sampling scheme supports browsing at any desired speed, while minimizing the variation on the number of video segments skipped between samplings. On the other hand, the segment placement scheme supports completely uniform segment sampling across the disk array for some specific speedup rates. Experiments for the visual effect of the proposed segment skipping approach have been conducted on MPEG data. It is shown that the proposed method is a viable approach to video browsing.