lfu.pdf
dhruvbird.com · 2,359 words · saved by 1 readers
N/A
An O(1) algorithm for implementing the LFU cache eviction scheme Prof. Ketan Shah Anirban Mitra Dhruv Matani August 16, 2010 Abstract Cache eviction algorithms are used widely in operating systems, databases and other systems that use caches to speed up execution by caching data that is used by the application. There are many policies such as MRU (Most Recently Used), MFU (Most Frequently Used), LRU (Least Re- cently Used) and LFU (Least Frequently Used) which each have their advantages…
saved by
related reading
- LRU Cache: How It Works (Data Structure & Code) | Interview Cakeinterviewcake.com
- Analyzing the codebase of Caffeine: a high performance caching library | Adri’s Blogadriacabeza.github.io
- A very concrete explanation of how a cache worksparksb.github.io
- abseil / Performance Hintsabseil.io
- Memory access is O(N^[1/3])vitalik.eth.limo
- p197-wang.pdfvldb.org
- Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowellbigocheatsheet.com
- Build Your Own Databasenan.fyi
- Cache Lines - Algorithmicaen.algorithmica.org
- Disk Cachechromium.org
- Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeksgeeksforgeeks.org
- CMSY9people.csail.mit.edu