Last modified
February 26, 2001

  Seminar Abstract
Center for Data Intensive Computing



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



Copyright © 1999 Brookhaven National Laboratory ALL RIGHTS RESERVED
Comments/Sugestions about this site contact: Webmaster