[Brown CS Talks] Brown CS Colloquium: Michael Bender in Lubrano on 5/16/02 at 4 pm
Thu, 02 May 2002 16:26:08 -0400
COMPUTER SCIENCE COLLOQUIUM
SUNY Stony Brook
Thursday, May 16, 2002 at 4:00 pm
Lubrano Conference Room (CIT 4th floor)
Refreshments will be served at 3:45 pm
Cache-Oblivious Data Structure
A new promising line of research is to develop data structures and
algorithms that run efficiently on a hierarchical memory, even though
they avoid any memory-specific parameterization (e.g., block sizes or
access times). Such platform-independent algorithms are said to be
cache-oblivious. If a cache-oblivious algorithm works optimally on a
two-level hierarchy, then it works optimally on all levels of a
multilevel memory hierarchy; cache-oblivious algorithms automatically
tune to arbitrary memory architectures.
This talk summarizes recent results in cache-oblivious data
structures. First we present cache-oblivious B-trees, which match the
performance of standard B-trees. Then we summarize other
cache-oblivious structures, including cache-oblivious priority queues,
tries, and dynamic structures supporting efficient scans.
Joint work with L. Arge, R. Cole, E. Demaine, Z. Duan, J. Iacono,
M. Farach-Colton, B. Holland-Minkley, I. Munro, and J. Wu.
Michael A. Bender is an Assistant Professor of Computer Science at
SUNY Stony Brook. He received his BA in Applied Mathematics from
Harvard University in 1992 and obtained a DEA in Computer Science from
the Ecole Normale Superieure de Lyon, France in 1993. He completed a
PhD on Scheduling Algorithms from Harvard University in 1998.
Michael A. Bender conducts algorithmic research in cache and
I/O-efficient computing, scheduling algorithms, data structures, and
asynchronous parallel and distributed computing. He is currently
writing a book on advanced data structures.
Host: Professor Maurice Herlihy