The LRU-K Page Replacement Algorithm For Database Disk Buffering

Summary: LRU-K tracks the last K references per page to estimate interarrival times and drive per-page eviction decisions. Self-tuning with lightweight bookkeeping, it adapts in real time, outperforming conventional buffering and approaching manually tuned, workload-specific pools. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2712
Venue: SIGMOD
Year: 1993
Pagerank: 0.00023846898
Overall Rank: 231 | 98.42%
DOI: 10.1145/170035.170081

Incoming Non-self Citations Over Time

Authors

1. Elizabeth J. O'Neill (University of Massachusetts Boston)
2. Patrick E. O'Neill (University of Massachusetts Boston)
3. Gerhard Weikum (ETH Zurich)

BibTeX Citation

@inproceedings{oneill_sigmod93,
        title = {{The LRU-K Page Replacement Algorithm For Database Disk Buffering}},
        author = {O'Neill, Elizabeth J. and O'Neill, Patrick E. and Weikum, Gerhard},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170081},
        url = {https://dl.acm.org/doi/10.1145/170035.170081},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 56 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,821	Concurrent Updates to Pages with Fixed-Size Rows Using Lock-Free Algorithms	2020	VLDB	5.093636e-05
12,579	Dynamic Partitioning of the Cache Hierarchy in Shared Data Centers	2008	VLDB	5.093636e-05
12,844	A One-Pass Aggregation Algorithm with the Optimal Buffer Size in Multidimensional OLAP	2002	VLDB	5.093636e-05
12,845	A Multi-version Cache Replacement and Prefetching Policy for Hybrid Data Delivery Environments	2002	VLDB	5.093636e-05
12,911	GHOST: Fine Granularity Buffering of Index Pages	1999	VLDB	5.093636e-05
13,009	L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS	1995	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
135	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00030209257
336	THE 5 MINUTE RULE FOR TRADING MEMORY FOR DISC ACCESSES and THE 10 BYTE RULE FOR TRADING MEMORY FOR CPU TIME	1987	SIGMOD	0.00020845451
837	Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS	1989	SIGMOD	0.0001370733
1,346	Fido: A Cache That Learns to Fetch	1991	VLDB	0.00011078024
1,527	Predictive Load Control for Flexible Buffer Allocation	1991	VLDB	0.00010489064
1,940	Flexible Buffer Allocation Based on Marginal Gains	1991	SIGMOD	9.4473794e-05
2,145	Priority-Hints: An Algorithm for Priority-Based Buffer Management	1990	VLDB	9.0846355e-05
2,590	Extensible Buffer Management of Indexes	1992	VLDB	8.3696843e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,324	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
2	1,940	Flexible Buffer Allocation Based on Marginal Gains	1991	SIGMOD
3	2,145	Priority-Hints: An Algorithm for Priority-Based Buffer Management	1990	VLDB
4	3,236	Sharing Buffer Pool Memory in Multi-Tenant Relational Database-as-a-Service	2015	VLDB
5	13,074	Local Disk Caching for Client-Server Database Systems	1993	VLDB
6	2,590	Extensible Buffer Management of Indexes	1992	VLDB
7	4,719	Adaptive Database Buffer Allocation Using Query Feedback	1993	VLDB
8	13,030	Estimating Page Fetches for Index Scans with Finite LRU Buffers	1994	SIGMOD
9	7,663	Index Access with a Finite Buffer	1987	VLDB
10	637	2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm	1994	VLDB