Algorithms and Data Structures
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.