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

Rank Citing Paper Year Venue Pagerank
389 QPipe: A Simultaneously Pipelined Relational Query Engine 2005 SIGMOD 0.00019269777
546 Faster: A Concurrent Key-Value Store with In-Place Updates 2018 SIGMOD 0.00016590738
593 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm 1994 VLDB 0.00015836342
780 Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering 2002 VLDB 0.00014025444
1,236 Druid: A Real-time Analytical Data Store 2014 SIGMOD 0.00011402848
1,399 LLAMA: A Cache/Storage Subsystem for Modern Hardware 2013 VLDB 0.00010781976
1,817 Broadcast Disks: Data Management for Asymmetric Communication Environments 1995 SIGMOD 9.5749088e-05
2,212 Managing Memory to Meet Multiclass Workload Response Time Goals 1993 VLDB 8.8207908e-05
2,437 Goal-Oriented Buffer Management Revisited* 1996 SIGMOD 8.4668531e-05
2,511 WATCHMAN: A Data Warehouse Intelligent Cache Manager 1996 VLDB 8.3696476e-05
2,839 Turbocharging DBMS Buffer Pool Using SSDs 2011 SIGMOD 7.9506131e-05
2,958 Dual-Buffering Strategies in Object Bases 1994 VLDB 7.8077689e-05
2,999 Sharing Buffer Pool Memory in Multi-Tenant Relational Database-as-a-Service 2015 VLDB 7.7676694e-05
3,032 iBTune: Individualized Buffer Tuning for Large-scale Cloud Databases 2019 VLDB 7.7351139e-05
3,649 Db2 Event Store: A Purpose-Built IoT Database Engine 2020 VLDB 7.1344087e-05
3,671 Leaper: A Learned Prefetcher for Cache Invalidation in LSM-tree based Storage Engines 2020 VLDB 7.1100217e-05
4,058 Semi-Automatic Index Tuning: Keeping DBAs in the Loop 2012 VLDB 6.8257215e-05
4,201 The Case for Distributed Shared-Memory Databases with RDMA-Enabled Memory Disaggregation 2023 VLDB 6.7375318e-05
4,354 Interaction of Query Evaluation and Buffer Management for Information Retrieval 1998 SIGMOD 6.6413283e-05
4,392 Sharing Data and Work Across Concurrent Analytical Queries 2013 VLDB 6.6213651e-05
4,791 Adaptive Database Buffer Allocation Using Query Feedback 1993 VLDB 6.4131306e-05
4,836 The ADABAS Buffer Pool Manager 1998 VLDB 6.3873221e-05
5,016 2R: Efficiently Isolating Cold Pages in Flash Storages 2020 VLDB 6.3133844e-05
5,018 Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems 2021 VLDB 6.3121723e-05
5,088 ROBUS: Fair Cache Allocation for Data-parallel Workloads 2017 SIGMOD 6.2805079e-05
5,360 LeanStore: A High-Performance Storage Engine for NVMe SSDs 2024 VLDB 6.1614422e-05
5,389 Flexible Resource Allocation for Relational Database-as-a-Service 2023 VLDB 6.1511236e-05
5,468 QUIET: Continuous Query-driven Index Tuning 2003 VLDB 6.1192263e-05
5,943 Operation-Aware Buffer Management in Flash-based Systems 2011 SIGMOD 5.9387777e-05
5,949 DEX: Scalable Range Indexing on Disaggregated Memory 2024 VLDB 5.9368754e-05
6,598 Proteus: Autonomous Adaptive Storage for Mixed Workloads 2022 SIGMOD 5.7405915e-05
6,826 SIMPLE: Efficient Temporal Graph Neural Network Training at Scale with Dynamic Data Placement 2024 SIGMOD 5.6700316e-05
6,932 Breaking Down Memory Walls in LSM-based Storage Systems 2020 SIGMOD 5.640907e-05
7,035 Increasing Buffer-Locality for Multiple Index Based Scans through Intelligent Placement and Index Scan Speed Control 2007 VLDB 5.6163837e-05
7,901 Write-Aware Timestamp Tracking: Effective and Efficient Page Replacement for Modern Hardware 2023 VLDB 5.4302737e-05
8,129 Two is Better Than One: The Case for 2-Tree for Skewed Data Sets 2023 CIDR 5.3938156e-05
8,165 Pangea: Monolithic Distributed Storage for Data Analytics 2019 VLDB 5.3851885e-05
8,530 SA-LSM: Optimize Data Layout for LSM-tree Based Storage using Survival Analysis 2022 VLDB 5.3222993e-05
8,768 PreVision: An Out-of-Core Matrix Computation System with Optimal Buffer Replacement 2024 SIGMOD 5.2814045e-05
8,930 Vertical Data Migration in Large Near-Line Document Archives Based on Markov-Chain Predictions 1997 VLDB 5.2559789e-05
9,269 Adaptive Data Broadcast in Hybrid Networks 1997 VLDB 5.2056825e-05
9,302 VIP Hashing - Adapting to Skew in Popularity of Data on the Fly 2022 VLDB 5.1979758e-05
9,463 Optimizing Complex Queries with Multiple Relation Instances 2008 SIGMOD 5.1728359e-05
10,289 Request Window: an Approach to Improve Throughput of RDBMS-based Data Integration System by Utilizing Data Sharing Across Concurrent Distributed Queries 2007 VLDB 5.0446125e-05
10,496 ReStore: A Reinforcement Learning Approach for Data Migration in Multi-Tiered Storage 2026 SIGMOD 4.9793485e-05
10,727 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.9793485e-05
10,904 Clock2Q+: A Simple and Efficient Replacement Algorithm for Metadata Cache in VMware vSAN 2026 VLDB 4.9793485e-05
10,912 Tuning the Lookahead Distance for PostgreSQL Asynchronous IO 2026 VLDB 4.9793485e-05
10,994 ReStore-in-Action: Adaptive Multi-Tier Storage Management via Intelligent Data Migration Policy 2026 VLDB 4.9793485e-05
11,137 ACE-in-Action: A Smart DBMS Bufferpool for SSDs 2025 SIGMOD 4.9793485e-05
Previous Page 1 / 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