DBScholar

Back to papers

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
h0f3811b5c589f7d4
Venue
SIGMOD
Year
1993
Pagerank
0.00024767296
Overall Rank
212 | 98.58%
DOI
10.1145/170035.170081

Incoming Non-self Citations Over Time

Authors

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 9 of 59 citing papers.

Rank Citing Paper Year Venue Pagerank
11,292 Locality-Aware Cache Replacement Policy for Graph Traversals 2025 VLDB 4.9793485e-05
11,429 Sampling-based Predictive Database Buffer Management 2025 VLDB 4.9793485e-05
11,815 Making Cache Monotonic and Consistent 2023 VLDB 4.9793485e-05
12,122 Concurrent Updates to Pages with Fixed-Size Rows Using Lock-Free Algorithms 2020 VLDB 4.9793485e-05
12,869 Dynamic Partitioning of the Cache Hierarchy in Shared Data Centers 2008 VLDB 4.9793485e-05
13,134 A One-Pass Aggregation Algorithm with the Optimal Buffer Size in Multidimensional OLAP 2002 VLDB 4.9793485e-05
13,135 A Multi-version Cache Replacement and Prefetching Policy for Hybrid Data Delivery Environments 2002 VLDB 4.9793485e-05
13,201 GHOST: Fine Granularity Buffering of Index Pages 1999 VLDB 4.9793485e-05
13,299 L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS 1995 VLDB 4.9793485e-05
Previous Page 2 / 2 Next

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
128 An Evaluation of Buffer Management Strategies for Relational Database Systems 1985 VLDB 0.00030411805
340 THE 5 MINUTE RULE FOR TRADING MEMORY FOR DISC ACCESSES and THE 10 BYTE RULE FOR TRADING MEMORY FOR CPU TIME 1987 SIGMOD 0.00020539958
843 Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS 1989 SIGMOD 0.00013533222
1,357 Fido: A Cache That Learns to Fetch 1991 VLDB 0.00010922832
1,520 Predictive Load Control for Flexible Buffer Allocation 1991 VLDB 0.00010383163
1,949 Flexible Buffer Allocation Based on Marginal Gains 1991 SIGMOD 9.3203578e-05
2,121 Priority-Hints: An Algorithm for Priority-Based Buffer Management 1990 VLDB 9.0092445e-05
2,560 Extensible Buffer Management of Indexes 1992 VLDB 8.2993451e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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