Academic
Publications
A Universal Online Caching Algorithm Based on Pattern Matching

A Universal Online Caching Algorithm Based on Pattern Matching,10.1007/s00453-008-9196-9,Algorithmica,Gopal Pandurangan,Wojciech Szpankowski

A Universal Online Caching Algorithm Based on Pattern Matching   (Citations: 2)
BibTex | RIS | RefWorks Download
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 ecient 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 specic 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).
Journal: Algorithmica , vol. 57, no. 1, pp. 62-73, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Lund et al. [27] improve on the above result by proposing an ecient randomized 4-competitive online caching algorithm that works for any distribution D but it needs to know for (each pair of) pages p and q the probability that p will next be requested before q. Using the randomized algorithm of Lund et al., Pandurangan and Szpankowski [36] give a universal online caching algorithm based on pattern matching that works on a large class of ...

    Gopal Panduranganet al. Entropy-based bounds for online algorithms

Sort by: