Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
Joan Boyar, Martin R. Ehmsen, Kim S. Larsen
WAOA 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 experimental results.


Last modified: Sat Aug 19 14:31:46 CEST 2006
Joan Boyar (joan@imada.sdu.dk)