- Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.
- Joan Boyar, Martin R. Ehmsen, and Kim S. Larsen.
In 4th Workshop on Approximation and Online Algorithms (WAOA), volume 4368 of Lecture Notes in Computer Science, pages 95-107. Springer, 2006.
The paging algorithm LRU-2 was proposed for use in database disk
buffering and shown experimentally to perform better than LRU
[O'Neil, O'Neil, and Weikum, 1993]. We compare LRU-2 and LRU
theoretically, using both the standard competitive analysis
and the newer relative worst order analysis.
The competitive ratio for LRU-2 is shown to be 2k
for cache size k
, which is worse than
LRU's competitive ratio of k
However, using relative worst order analysis,
we show that LRU-2 and LRU are asymptotically comparable
in LRU-2's favor, giving a theoretical justification for the
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.