A Theoretical Comparison of LRU and LRU-K
Joan Boyar, Martin R. Ehmsen, Jens S. Kohrt, Kim S. Larsen
Acta Informatica

The paging algorithm Least Recently Used Second Last Request (LRU-2) was proposed for use in database disk buffering and shown experimentally to perform better than Least Recently Used (LRU). We compare \lrutwo 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 comparable in LRU-2's favor, giving a theoretical justification for the experimental results. Many of our results for LRU-2 also apply to its generalization, Least Recently Used Kth Last Request.

Last modified: Mon Aug 30 11:07:38 CEST 2010
Joan Boyar (joan@imada.sdu.dk)