Abstract
A hit rate curve is a function that maps cache size to the proportion of requests that can be served from the cache. (The caching policy and sequence of requests are assumed to be fixed.) Hit rate curves have been studied for decades in the operating system, database and computer architecture communities. They are useful tools for designing appropriate cache sizes, dynamically allocating memory between competing caches, and for summarizing locality properties of the request sequence. In this paper we focus on the widelyused LRU caching policy.
Computing hit rate curves is very efficient from a runtime standpoint, but existing algorithms are not efficient in their space usage. For a stream of m requests for n cacheable objects, all existing algorithms that provably compute the hit rate curve use space linear in n. In the context of modern storage systems, n can easily be in the billions or trillions, so the space usage of these algorithms makes them impractical.
We present the first algorithm for provably approximating hit rate curves for the LRU policy with sublinear space. Our algorithm uses O( p^2 * log(n) * log^2(m) / epsilon^2 ) bits of space and approximates the hit rate curve at p uniformlyspaced points to within additive error epsilon. This is not far from optimal. Any singlepass algorithm with the same guarantees must use Omega(p^2 + epsilon^{2} + log(n)) bits of space. Furthermore, our use of additive error is necessary. Any singlepass algorithm achieving multiplicative error requires Omega(n) bits of space.
BibTeX  Entry
@InProceedings{drudi_et_al:LIPIcs:2015:5305,
author = {Zachary Drudi and Nicholas J. A. Harvey and Stephen Ingram and Andrew Warfield and Jake Wires},
title = {{Approximating Hit Rate Curves using Streaming Algorithms}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {225241},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5305},
URN = {urn:nbn:de:0030drops53056},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.225},
annote = {Keywords: Cache analysis, hit rate curves, miss rate curves, streaming algorithms}
}
Keywords: 

Cache analysis, hit rate curves, miss rate curves, streaming algorithms 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) 
Issue Date: 

2015 
Date of publication: 

13.08.2015 