License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.225
URN: urn:nbn:de:0030-drops-53056
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5305/
Drudi, Zachary ;
Harvey, Nicholas J. A. ;
Ingram, Stephen ;
Warfield, Andrew ;
Wires, Jake
Approximating Hit Rate Curves using Streaming Algorithms
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 widely-used 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 uniformly-spaced points to within additive error epsilon. This is not far from optimal. Any single-pass 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 single-pass 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 = {225--241},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-89-7},
ISSN = {1868-8969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5305},
URN = {urn:nbn:de:0030-drops-53056},
doi = {10.4230/LIPIcs.APPROX-RANDOM.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 |
