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.