Abstract: Cache schema is very important for LSVOD （large scale video on demand） system and it is one of the most important techniques to enable VOD to enter market. The disk cache is different from memory cache in several ways for the large volume and high bandwidth requirement of continuous media data. In this paper, two new cache replacement algorithms based on access frequency: LFRU（least frequency and recently used） and PLFU（period least frequency used） are developed. LFRU is a trade off between LRU and LFU, which has advantages of both algorithms. PLFU is an improved LFU algorithm, which solves the cache pollution problem of LFU algorithm. It is shown by means of simulation and experiments that the new algorithms are more effective and more suitable than others for LSVOD system.