A critical problem to peer-to-peer video-on-demand (P2P VoD) systems is to provide efficient user interactivity support. In this paper, we study intra- and inter-video operations separately, aiming to exploit the locality of reference in user access patterns and reduce the latency of these VoD operations. We first introduce the concepts of available, request and delivered locality in intra-video user access patterns and prove that high available locality exists in different videos by both simulation and theoretical analysis. Moreover, with a relaxed definition of data chunk holder, intra-video locality can facilitate a high likelihood of a peer seeking within a video, finding a holder of the requested data among its neighbors. Exploiting this property, an aggressive cached publish scheme is designed to build shortcuts over the DHT network so as to reduce the lookup delay. This scheme may be simple but it is practical and easy to implement. Inter-video locality is exploited via learning association rules from the collective viewing history. A fast association rule learning algorithm is proposed to infer the relations between videos in a distributed manner based on partial knowledge. Both search and content prefetch are incorporated to achieve low inter-video jump delay with minimal overhead. Our simulations demonstrate that the proposed schemes can reduce the buffer and lookup delay for seeking within a video and provide an efficient prediction-based prefetch scheme for inter-video access.