Outperforming LRU with an adaptive replacement cache algorithm
The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
The self-tuning, low-overhead, scan-resistant adaptive replacement cache algorithm outperforms the least-recently-used algorithm by dynamically responding to changing access patterns and continually balancing between workload recency and frequency features. Caching, a fundamental metaphor in modern computing, finds wide application in storage systems, databases, Web servers, middleware, processors, file systems, disk drives, redundant array of independent disks controllers, operating systems, and other applications such as data compression and list updating. In a two-level memory hierarchy, a cache performs faster than auxiliary storage, but it is more expensive. Cost concerns thus usually limit cache size to a fraction of the auxiliary memory's size.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
A study of replacement algorithms for a virtual-storage computer
Belady, L. A. (1966) · IBM Systems Journal · doi:10.1147/sj.52.0078 · Cited by 1,659
Evaluation techniques for storage hierarchies
Mattson, R. L., Gecsei, J., Slutz, D. R., & Traiger, I. L. (1970) · IBM Systems Journal · doi:10.1147/sj.92.0078 · Cited by 1,302
ARC: a self-tuning, low overhead replacement cache
Megiddo, N., & Modha, D. S. (2003) · File and Storage Technologies · Cited by 1,120
Self-citation2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm
Johnson, T. J., & Shasha, D. E. (1994) · Very Large Data Bases · Cited by 811
Coffman, E. G., & Denning, P. J. (1973) · Medical Entomology and Zoology · Cited by 795
Lee, D., Choi, J., Kim, J.-H., Noh, S. H., Min, S. L., Cho, Y., & Kim, C. S. (2001) · IEEE Transactions on Computers · doi:10.1109/tc.2001.970573 · Cited by 590
Jiang, S., & Zhang, X. (2002) · Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems · doi:10.1145/511334.511340 · Cited by 489
The Multi-Queue Replacement Algorithm for Second Level Buffer Caches
Zhou, Y., Philbin, J. F., & Li, K. (2001) · USENIX Annual Technical Conference · Cited by 408
Denning, P. J. (1980) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1980.230464 · Cited by 396
Research works printed but not linked: 1
- Corbato, 1969, A Paging Experiment with the Multics System, 217
Cited by
Items 201–274 of 274
Database Tuning using Trade-off Elimination
Chaudhuri, S., & Weikum, G. (2009) · Springer eBooks · doi:10.1007/978-0-387-39940-9_44 · Cited by 1
Switching Between Page Replacement Algorithms Based on Work Load During Runtime in Linux Kernel
Subramaniyam, P. (2017) · San José State University ScholarWorks (San Jose State University) · doi:10.31979/etd.xj6w-cucm · Cited by 1
A Top-K-Based Cache Model for Deep Web Query
Kou, Y., Shen, D., Yu, G., Nie, T., & Li, D. (2007) · Scalable Information Systems · doi:10.4108/infoscale.2007.965 · Cited by 1
Improving grid performance by dynamically deploying applications
Wu, Y., Chen, G., Liu, J., Fang, R., Yang, G., & Zheng, W. (2010) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.1568 · Cited by 1
Dynamic Cache Switching: Developing configurable caches for use in softcore processors
Shield, J. (2010) · Cited by 1
Effective on-chip cache utilization in chip multiprocessors
Hossain, H., & Dwarkadas, S. (2010) · UR Research (University of Rochester) · Cited by 1
Machine Learning for Network Resource Management
Hassine, N. B. (2017) · theses.fr (ABES) · doi:10.70675/d1661a72za7ecz4577z8e31z716d75cac8cd · Cited by 1
Multi-Head Recurrent Memory AgentsPreprint
Li, J., Yeh, S., & Li, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.01523 · Cited by 1
Improving Caches in Consolidated Environments
Koller, R. (2012) · FIU - Digital Commons (Florida International University) · doi:10.25148/etd.fi12080801
Database Tuning Using Trade-Off Elimination
Chaudhuri, S., & Weikum, G. (2018) · Springer eBooks · doi:10.1007/978-1-4614-8265-9_44
Traffic Splitting over ECMPs using ACC Scheme
Lin, W. M., Tang, Y., & Liu, B. (2006) · International Conference on Communications and Networking in China (ChinaCom) · doi:10.1109/chinacom.2006.344703
Cost Based Approach to Block Placement for Distributed File Systems
Srinivasan, L., & Varma, V. (2014) · International Conference on Future Internet of Things and Cloud (FiCloud) · doi:10.1109/ficloud.2014.30
Kim, H., & Okada, K. (2012) · Asia-Pacific Magnetic Recording Conference
A Hierarchical Cache Scheme for Object Storage System
Shan, Y., Yao, N., & Yu, J. (2009) · International Conference on New Trends in Information Science and Service Science · doi:10.1109/niss.2009.29
Network centric improvements to resource caching
Zuck, A. W. R. (2005) · IEEE Consumer Communications and Networking Conference · doi:10.1109/ccnc.2005.1405169
Amer, A., Mossé, D., & Essary, D. (2011) · PhDT
ALR-MIN: A Replacement Strategy to Reduce Overhead during Dynamic Deployment of Applications in Grid
Gang, C., Wu, Y., Liu, J., Fang, R., Yang, G., & Zheng, W. (2009) · International Conference on Embedded Computing · doi:10.1109/embeddedcom-scalcom.2009.65
Traffic Splitting overECMPsusing ACC Scheme
Uni, T. (2006)
Effective on-chip cache utilization in chip multiprocessors
Dwarkadas, S., & Hossain, H. (2010)
Markov Chain Analysis of Web Cache Systems under TTL-based Consistency
Gomaa, H. (2013) · Libraries and Cultural Resources (University of Calgary) · doi:10.11575/prism/26833
Query Algorithms for Location Based Services in Road Network Distance
Htoo, H. (2013) · Institutional Repositories DataBase (IRDB)
Performance enhancements in large scale storage systems
Rajesh, V. A. (2015) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/65630
Application Streaming: A Mobile Application Distribution Method
Wang, Y., Jia, L., & Wang, G. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-27119-4_21
Reversible, information-preserving logic and its application
Lukáč, M., Shuai, B., Kameyama, M., & Miller, D. M. (2014)
Runtime support for effective memory management in large-scale applications
Sivasubramaniam, A., & Vilayannur, M. (2005)
Optimizing Main Memory Usage in Modern Computing Systems to Improve Overall System Performance
Campello, D. (2016) · FIU - Digital Commons (Florida International University) · doi:10.25148/etd.fidc000755
Multicore processors: Status quo and future directions
Zahran, M. (2014) · International Computer Engineering Conference · doi:10.1109/icenco.2014.7050422
Unifying the approach to histogram visualisation in ATLAS The Online Histogram Presenter
Adragna, P., Carpana, D., Cimino, D., Dotti, A., & Vitillo, R. (2008) · IEEE Nuclear Science Symposium and Medical Imaging Conference (NSS/MIC) · doi:10.1109/nssmic.2008.4774727
Research on the second-level query results cache in Web search engines
Ma, H., Zhang, X., & Wang, B. (2012) · IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS) · doi:10.1109/ccis.2012.6664248
APPENDIX G VIRTUAL MEMORY PAGE REPLACEMENT ALGORITHMS
Stallings, W. (2012)
A Survey on Optimal Data Storage of Cache Manager for Big Data Using Map Reduce Framework
Pashte, R. V., & Thakur, R. (2014)
Quality-driven management of video streaming services in segment-based cache networks
Claeys, M. (2017) · Institutional Repository University of Antwerp (University of Antwerp)
Wiseman, A. (2013) · OhioLink ETD Center (Ohio Library and Information Network)
Harris, M. (2017) · BIROn (Birkbeck, University of London) · doi:10.18743/pub.00040236
Low latency data retrieval solutions for big data
Datye, C. S. (2016) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)
Al-Manasia, M. (2017) · UTS ePRESS (University of Technology Sydney)
Cache Optimization for the Modern Web
Lam, J. (2015) · eScholarship (California Digital Library)
Kleanthous, M. (2012) · The Library of Electronic Cyprus Thematic Organized Collections (LYKYTHOS) (University of Cyprus) · doi:10.82357/gnosis/923
Re-Reference Interval Prediction Swap Policy in the Linux Kernel
Singer, A. R. (2017) · OakTrust (Texas A&M University Libraries)
Video popularity metrics and bubble cache eviction algorithm analysis
Weisenborn, H. J. (2018) · Open Access at Essex (University of Essex)
Performanceanalyse und plattformspezifische Optimierungen am Beispiel des Grid-ALU-Prozessors
Jahr, R. (2012) · OPUS (Augsburg University)
Improving cache replacement policy using deep reinforcement learning
Benson, C. E. (2018) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)
Øren, M. (2019) · NORA - Norwegian Open Research Archives
Video Popularity Forecasting to Improve Cache Miss Rate in Content Delivery Networks
Rojas-Delgado, J., Trujillo-Rasúa, R., Bello, R., & Moya, G. E. J. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-33904-3_73
On I/O Performance and Cost Efficiency of Cloud Storage: A Client's Perspective
Hou, B. (2019) · Louisiana State University · doi:10.31390/gradschool_dissertations.5090
Ozen, G. (2020) · Digital Access to Scholarship at Harvard (DASH) (Harvard University)
Realtime Congestion Forecasting of Remote Space Through BLE Beacons
Taiki, I., & Fujita, S. (2020) · International Symposium on Computing and Networking Workshops (CANDARW) · doi:10.1109/candarw51189.2020.00018
Evaluating Multiple Caching Strategies for Semantic Network Applications
Malis, S. M., & French, J. D. (2015)
(2022) · Elsevier eBooks · doi:10.1016/b978-0-32-390796-5.00023-1
Thomasian, A. (2022) · Elsevier eBooks · doi:10.1016/b978-0-32-390796-5.00010-3
Research on SpMV Implementation and vector x Hit Rate Optimization for SW26010p Many-Core PlatformPreprint
Ma, M., Wei, Z., Jing, X., Jia, D., Xu, J., Wang, Y., Zhang, C., & Han, H. (2022) · Research Square · doi:10.21203/rs.3.rs-1940073/v1
Database Tuning using Trade-off Elimination
Chaudhuri, S., & Weikum, G. (2016) · Springer eBooks · doi:10.1007/978-1-4899-7993-3_44-2
An Enhanced Method for Running Embedded Applications in a Power-Efficient Manner
Kumar, N. M. G., Ahmad, A., Gowda, D., V, Lokesh, S., & Kadam, K. (2022) · Advances in computer and electrical engineering book series · doi:10.4018/978-1-6684-4974-5.ch013
Selection of Cache Replacement Algorithm for PostgreSQL
Prasad, P. Y., Velayduam, L. N., Kumar, S. S., Shaikshavali, M., Reddy, V. V., & Kumar, N. A. (2023) · International Conference on Sustainable Computing and Data Communication Systems (ICSCDS) · doi:10.1109/icscds56580.2023.10105126
Interpretability of AI in Computer Systems and Public Policy
Yusuf, F. (2021) · FIU - Digital Commons (Florida International University) · doi:10.25148/etd.fidc010230
ADAPTING THE ARC CACHE MANAGEMENT POLICY TO FILE GRANULARITY
Mahni, H., Rubini, S., Boukhobza, J., Gougeaud, S., & Deniel, P. (2023) · HAL
A Hybrid Data Storage Method for Pulse-to-Pulse Optimizations
Hoosier, T. V., Alexander, J., Montgomery, M., Egbert, A., Roessler, J., Baylis, C., & Marks, R. J. (2024) · IEEE Transactions on Radar Systems · doi:10.1109/trs.2024.3428450
Page Replacement Algorithms: A Survey of Performance and Case Studies
Deshmukh, B. M. M., Savji, A., Thorat, V., Patil, V., & Deshmukh, M. S. (2024) · INTERANTIONAL JOURNAL OF SCIENTIFIC RESEARCH IN ENGINEERING AND MANAGEMENT · doi:10.55041/ijsrem39275
Towards Optimal Content Replication and Request Routing in the Presence of Unreliable LinksPreprint
Derakhshan, S. F., Tyrychtr, J., & Benda, T. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5396448
Equité d'accès aux ressources dans les systèmes partagés best-effort
Goichon, F. (2013) · theses.fr (ABES) · doi:10.70675/af98da64zb53ez46edz9d7fz13eb548f6bb5
Oddsdóttir, J., & 1989, S. Ó. S. B. (2018) · Skemman
Evaluating Multiple Caching Strategies for Semantic Network Applications
French, J. D., & Malis, S. M. (2015) · Digital WPI
Enhanced caching mechanisms for named data networking
Taher, S. J. (2023) · UUM Electronic Theses and Dissertation [eTheses] (Northern University of Malaysia)
Improving cooperative caching in Autonomic Wireless Mesh Networks
Nkwe, T. K. R. (2009) · The Atrium (University of Guelph)
On designing effective user interfaces
Zheng, Q. (2016) · ThinkTech (Texas Tech University)
Reinforcement Learning-Enhanced Adaptive Buffer Replacement for Modern Databases
Zhang, S., Wu, K., Chen, Z., & Liu, Y. (2026) · Lecture notes in computer science · doi:10.1007/978-981-95-5640-3_44
Evolving Sketch: Time-Decaying Frequency Estimation for Evolving Streams
Gao, G., Du, Y., Huang, H., Sun, Y.-E., & Tang, J. (2026) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65706.2026.00023
Adaptive write-cache management for alternating deep learning and non-AI workloads on mobile devices
Lee, J., & Bahn, H. (2026) · Future Generation Computer Systems · doi:10.1016/j.future.2026.108759
5G ağları ve ötesinde uyarlanabilir uç ön bellekleme
Demirci, İ. (2025) · Marmara University Open Access System
Improved Buffer Size Adaptation through Cache/Controller Coupling.
Lang, C. A., Bhattacharjee, B., Malkemus, T., & Stanoi, I. (2007)
Metadata
- Authors
- Megiddo, N., & Modha, D. S.
- Affiliations
- IBM Research - Almaden (US)
- Venue
- Computer
- Published
- 2004-04
- Volume
- 37
- Issue
- 4
- Pages
- 58-65
- ISSN
- 0018-9162 (ISSN-L)
- OpenAlex
- W2003549201
- Cited by
- 243
- References
- 18
- Citations by year
- 2026: 6 · 2025: 5 · 2024: 6 · 2023: 9 · 2022: 9 · 2021: 13 · 2020: 11 · 2019: 9 · 2018: 16 · 2017: 19 · 2016: 17 · 2015: 12 · 2014: 18 · 2013: 11 · 2012: 17
- FWCI
- 14.18
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Computer (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Caching and Content Delivery
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Data Storage Technologies
- Keywords
- LRU cache, cache replacement policy, auto-tuning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.