cache-oblivious-algorithm · research · also Cache-oblivious algorithms

Cache-oblivious algorithm

A cache-oblivious algorithm does not use cache capacity or transfer-block size as tuning parameters in its computation or data layout.

Its analysis may still depend on those parameters. The ideal-cache model counts transfers between two memory levels, with a fully associative cache and optimal offline replacement. The name alone does not imply an efficient algorithm. [1]

Recursive layouts can expose locality at several scales. Bender, Demaine and Farach-Colton give dynamic search trees whose transfer bounds do not require the algorithm to know block size. Their first construction matches the classical B-tree search bound; its update guarantee is amortized, whereas the classical comparison is worst-case. [2]

Frigo et al., Lemma 12, bounds LRU misses by twice the misses of an optimal cache of half its capacity, not the same capacity. [1]

Relations

related
B-tree, B-epsilon tree, Least recently used replacement

Citations

  1. Frigo, Leiserson, Prokop and Ramachandran. Cache-Oblivious Algorithms. FOCS 1999, pp. 285-297; sections 1 and 6, Lemma 12 and Corollary 13. (accessed 2026-11-21)
  2. Bender, Demaine and Farach-Colton. Cache-Oblivious B-Trees. SICOMP 35(2), 2005, pp. 341-358, sections 1-2. DOI 10.1137/S0097539701389956. (accessed 2026-11-21)

Further reading

  1. Hesela: cache-oblivious bounds and the LRU capacity comparison (accessed 2026-11-21)
Sources & caveats
  • Primary-source terminology and theoretical guarantees; no performance measurement or implementation replication.

JSON: /data/terms/cache-oblivious-algorithm.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Cache-oblivious algorithm. Hesela. 2026-11-21. https://hesela.dev/terms/cache-oblivious-algorithm/