Interreference interval for purged objects: a new metric for design and analysis of Web caching algorithms

This paper proposes a new metric, called interreference interval for purged objects (II-PO for short) to capture temporal locality in Web references. The metric is used in a partitioned cache model to design and optimize Web caching algorithms. We derive an optimal condition, using the proposed metric, for cache hit ratio in a partitioned cache model. An optimization of the 2Q algorithm is described, as an example, through the obtained optimal partitioning. The case study with the WebPolygraph3 benchmark shows up to 20% relative improvement of the cache hit ratio over the Least Recently Used (LRU) algorithm.