Cache-Oblivious Algorithms and Data Structures


We present methods for constructing cache-oblivious algorithms and data structures. Cache-oblivious algorithms run efficiently on a hierarchical memory, even though they completely avoid any memory-specific parameterization (such as cache block sizes or access times). We first review the regular and static problems in the literature. Then we show new methods for designing memory efficient cache-oblivious algorithms for dynamic and irregular problems, such as data structures. We show how to design a cache-oblivious B-tree, which matches the performance of the standard B-tree. Then we outline future directions in this area.

Joint work with Erik Demaine and Martin Farach-Colton.

Top of Page