The most popular caching algorithms in practice are based on the Least-Recently-Used (LRU) cache replacement rule that possesses many desirable characteristics, including high hit ratio, low complexity and the flexibility to dynamically adopt to possible changes in request patterns. However, in the context of the independent reference model, the LRU policy can significantly underperform the optimal Least-Frequently-Used (LFU) algorithm. On the other hand, the benefit of the LFU rule is counterbalanced by its higher implementation complexity and lower adaptability to changes in access frequencies.

To alleviate this problem, we introduce a new LRU-based rule, termed the Persistent-Access-Caching (PAC), which essentially preserves all of the desirable attributes of the LRU scheme and, for the independent reference model and generalized Zipf's law request probabilities, it is nearly optimal. In addition, we discuss the modification of the PAC algorithm for caching pages of variable sizes and its performance in the presence of strong statistical correlation in request access patterns.

Lecture #10602

Need help? Visit our help pages at http://www.msri.org/communications/vmath/hints

The video is in post production and will be posted shortly.

See more of our Streaming Videos on our main VMath - Streaming Video page.