A Theoretical Comparison of LRU and LRU-K

Joan Boyar, Martin R. Ehmsen, Jens Svalgaard Kohrt, Kim Skak Larsen

Research output: Contribution to journalJournal articleResearchpeer-review


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 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 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.
Original languageEnglish
JournalActa Informatica
Issue number7-8
Pages (from-to)359-374
Number of pages16
Publication statusPublished - 2010

Cite this