ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The LRU-K Page Replacement Algorithm For Database Disk Buffering.

Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum: The LRU-K Page Replacement Algorithm For Database Disk Buffering. SIGMOD Conference 1993: 297-306
@inproceedings{DBLP:conf/sigmod/ONeilOW93,
  author    = {Elizabeth J. O'Neil and
               Patrick E. O'Neil and
               Gerhard Weikum},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {The LRU-K Page Replacement Algorithm For Database Disk Buffering},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {297-306},
  ee        = {http://doi.acm.org/10.1145/170035.170081, db/conf/sigmod/ONeilOW93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper introduces a new approach to database disk buffering, called the LRU-K method. The basic idea of LRU-K is to keep track of the times of the last K references to popular database pages, using this information to statistcally estimate the interarrival times of references on a page by page basis. Although the LRU-K approach performs optimal statistical inference under relatively standard assumptions, it is faily simple and incurs little bookkeeping overhead. As we demonstrate with simulation experiments, the LRU-K algorithm surpasses conventional buffering algorithms in discriminating between frequently and infrequently referenced pages. In fact, LRU-K can approach the behavior of buffering algorithms in which page sets with known access frequencies are manually assigned to different buffer pools of specifically tuned sizes. Unlike such customized buffering algorithms however, the LRU-K method is self-tuning, and does not rely on external hints about workload characteristics. Furthermore, the LRU-K algorithm adapts in real time to changing patterns of access.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]

References

[ABG]
Rafael Alonso, Daniel Barbará, Hector Garcia-Molina: Data Caching Issues in an Information Retrieval System. ACM Trans. Database Syst. 15(3): 359-384(1990) BibTeX
[ADU]
Alfred V. Aho, Peter J. Denning, Jeffrey D. Ullman: Principles of Optimal Page Replacement. J. ACM 18(1): 80-93(1971) BibTeX
[CHAKA]
Ellis E. Chang, Randy H. Katz: Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS. SIGMOD Conference 1989: 348-357 BibTeX
[CHOUDEW]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 BibTeX
[CKS]
...
[COL]
Chee Yong Chan, Beng Chin Ooi, Hongjun Lu: Extensible Buffer Management of Indexes. VLDB 1992: 444-454 BibTeX
[COFFDENN]
Edward G. Coffman Jr., Peter J. Denning: Operating Systems Theory. Prentice-Hall 1973
BibTeX
[DANTOWS]
Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152 BibTeX
[DENNING]
Peter J. Denning: The Working Set Model for Program Behaviour. Commun. ACM 11(5): 323-333(1968) BibTeX
[EFFEHAER]
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) BibTeX
[FNS]
Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274 BibTeX
[GRAYPUT]
Jim Gray, Gianfranco R. Putzolu: The 5 Minute Rule for Trading Memory for Disk Accesses and The 10 Byte Rule for Trading Memory for CPU Time. SIGMOD Conference 1987: 395-398 BibTeX
[HAAS]
Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX
[JCL]
Rajiv Jauhari, Michael J. Carey, Miron Livny: Priority-Hints: An Algorithm for Priority-Based Buffer Management. VLDB 1990: 708-721 BibTeX
[KNUTH]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[NFS]
Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396 BibTeX
[OOW]
...
[PAZDO]
Mark Palmer, Stanley B. Zdonik: Fido: A Cache That Learns to Fetch. VLDB 1991: 255-264 BibTeX
[REITER]
...
[ROBDEV]
John T. Robinson, Murthy V. Devarakonda: Data Cache Management Using Frequency-Based Replacement. SIGMETRICS 1990: 134-142 BibTeX
[SACSCH]
Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986) BibTeX
[SHASHA]
Dennis Shasha: Database Tuning - A Principled Approach. Prentice-Hall 1992, ISBN 0-13-205246-6
Contents BibTeX
[STON]
Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) BibTeX
[TENGGUM]
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) BibTeX
[TPC-A]
...
[YUCORN]
Philip S. Yu, Douglas W. Cornell: Optimal Buffer Allocation in A Multi-Query Environment. ICDE 1991: 622-631 BibTeX

Referenced by

  1. Gerhard Weikum, Arnd Christian König, Achim Kraiss, Markus Sinnwell: Towards Self-Tuning Memory Management for Data Servers. IEEE Data Eng. Bull. 22(2): 3-11(1999)
  2. Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan: GHOST: Fine Granularity Buffering of Indexes. VLDB 1999: 339-350
  3. Markus Sinnwell, Arnd Christian König: Managing Distributed Memory to Meet Multiclass Workload Response Time Goals. ICDE 1999: 87-94
  4. Achim Kraiss, Gerhard Weikum: Integrated Document Caching and Prefetching in Storage Hierarchies Based on Markov-Chain Predictions. VLDB J. 7(3): 141-162(1998)
  5. Harald Schöning: The ADABAS Buffer Pool Manager. VLDB 1998: 675-679
  6. Björn Þór Jónsson, Michael J. Franklin, Divesh Srivastava: Interaction of Query Evaluation and Buffer Management for Information Retrieval. SIGMOD Conference 1998: 118-129
  7. Boris Y. L. Chan, Antonio Si, Hong Va Leong: Cache Management for Mobile Databases: Design and Evaluation. ICDE 1998: 54-63
  8. Qinglong Hu, Dik Lun Lee, Wang-Chien Lee: Dynamic Data Delivery in Wireless Communication Environments. ER Workshops 1998: 218-229
  9. Ling Feng, Hongjun Lu, Y. C. Tay, Anthony K. H. Tung: Buffer Management in Distributed Database Systems: A Data Mining Based Approach. EDBT 1998: 246-260
  10. Konstantinos Stathatos, Nick Roussopoulos, John S. Baras: Adaptive Data Broadcast in Hybrid Networks. VLDB 1997: 326-335
  11. Achim Kraiss, Gerhard Weikum: Vertical Data Migration in Large Near-Line Document Archives Based on Markov-Chain Predictions. VLDB 1997: 246-255
  12. Markus Sinnwell, Gerhard Weikum: A Cost-Model-Based Online Method for Ditributed Caching. ICDE 1997: 532-541
  13. Jung-Ho Ahn, Hyoung-Joo Kim: SEOF: An Adaptable Object Prefetch Policy for Object-Oriented Database Systems. ICDE 1997: 4-13
  14. Kian-Lee Tan, Beng Chin Ooi, Tat-Seng Chua: On Video-on-Demand sSrvers with Hierarchical Storage. DASFAA 1997: 491-500
  15. Martha Escobar-Molano, Shahram Ghandeharizadeh, Doug Ierardi: An Optimal Resource Scheduler for Continuous Display of Structured Video Objects. IEEE Trans. Knowl. Data Eng. 8(3): 508-511(1996)
  16. Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. VLDB 1996: 51-62
  17. Kurt P. Brown, Michael J. Carey, Miron Livny: Goal-Oriented Buffer Management Revisited. SIGMOD Conference 1996: 353-364
  18. Frank Moser, Achim Kraiss, Wolfgang Klas: L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS. VLDB 1995: 275-286
  19. Swarup Acharya, Rafael Alonso, Michael J. Franklin, Stanley B. Zdonik: Broadcast Disks: Data Management for Asymmetric Communications Environments. SIGMOD Conference 1995: 199-210
  20. Theodore W. Leung: Scheduling Resource Usage in Object-Oriented Queries. DBPL 1995: 9
  21. Alfons Kemper, Donald Kossmann: Dual-Buffering Strategies in Object Bases. VLDB 1994: 427-438
  22. Theodore Johnson, Dennis Shasha: 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994: 439-450
  23. Chung-Min Chen, Nick Roussopoulos: Adaptive Database Buffer Allocation Using Query Feedback. VLDB 1993: 342-353
  24. Kurt P. Brown, Michael J. Carey, Miron Livny: Managing Memory to Meet Multiclass Workload Response Time Goals. VLDB 1993: 328-341
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:15 2009