# 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.

## Abstract

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)

**DOI**

10.1007/978-3-540-27810-8_2

**Links**

**Slides**

swat04invited.pdf (545 Kb)

**BIBT**_{E}X entry

@incollection{swat04invited,
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"
}