A Universal Online Caching Algorithm Based on Pattern Matching

摘要

We present a universal algorithm for the classical online problem of caching or demand paging. We consider the caching problem when the page request sequence is drawn from an unknown probability distribution and the goal is to devise an efficient algorithm whose performance is close to the optimal online algorithm which has full knowledge of the underlying distribution. Most previous works have devised such algorithms for specific classes of distributions with the assumption that the algorithm has full knowledge of the source. In this paper, we present a universal and simple algorithm based on pattern matching for mixing sources (includes Markov sources). The expected performance of our algorithm is within 4+o(1) times the optimal online algorithm (which has full knowledge of the input model and can use unbounded resources). Keywords Online computation - Caching - Universal algorithm - Stochastic model A preliminary version of this paper was presented at the IEEE International Symposium on Information Theory, Adelaide, Australia, 2005.