Cache-Oblivious Algorithms and Data Structures

Gerth Stølting Brodal

In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, pages 3-13. Springer Verlag, Berlin, 2004.


Frigo, Leiserson, Prokop and Ramachandran in 1999 introduced the ideal-cache model as a formal model of computation for developing algorithms in environments with multiple levels of caching, and coined the terminology of cache-oblivious algorithms. Cache-oblivious algorithms are described as standard RAM algorithms with only one memory level, i.e. without any knowledge about memory hierarchies, but are analyzed in the two-level I/O model of Aggarwal and Vitter for an arbitrary memory and block size and an optimal off-line cache replacement strategy. The result are algorithms that automatically apply to multi-level memory hierarchies. This paper gives an overview of the results achieved on cache-oblivious algorithms and data structures since the seminal paper by Frigo et al.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2004. All rights reserved.

Online version

swat04invited.pdf (128 Kb)





swat04invited.pdf (545 Kb)

BIBTEX entry

  author = "Gerth St{\o}lting Brodal",
  booktitle = "Proc. 9th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/978-3-540-27810-8_2",
  isbn = "978-3-540-22339-9",
  pages = "3-13",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Cache-Oblivious Algorithms and Data Structures",
  volume = "3111",
  year = "2004"