Abstract: In this paper, ELFU （extended least frequently used）, a new data replacement algorithm based on the characteristics of continuous media services, is presented. This algorithm reduces the video page miss ratio by conducting an active replacement policy. First, the characteristics of continuous media services are studied thoroughly. Second, the storage model of continuous media server is expounded. Then a new data replacement algorithm——ELFU is put forward based on the characteristics and storage model. The implementation of this algorithm is described in detail, and the simulation result is also mentioned.