Paper by Erik D. Demaine
- Erik D. Demaine, “Cache-Oblivious Algorithms and Data Structures”, in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002.
A recent direction in the design of cache-efficient and disk-efficient
algorithms and data structures is the notion of cache obliviousness,
introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999.
Cache-oblivious algorithms perform well on a multilevel memory hierarchy
without knowing any parameters of the hierarchy, only knowing the existence of
a hierarchy. Equivalently, a single cache-oblivious algorithm is efficient on
all memory hierarchies simultaneously. While such results might seem
impossible, a recent body of work has developed cache-oblivious algorithms and
data structures that perform as well or nearly as well as standard
external-memory structures which require knowledge of the cache/memory size and
block transfer size. Here we describe several of these results with the intent
of elucidating the techniques behind their design. Perhaps the most exciting
of these results are the data structures, which form general building blocks
immediately leading to several algorithmic results.
- The paper is 29 pages.
- The paper is available in PostScript (476k), gzipped PostScript (198k), and PDF (230k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2021 by