[Brown CS Talks] Brown CS Colloquium: Michael Bender in Lubrano on 5/16/02 at 4 pm

[talks-admin@list.cs.brown.edu]

			   BROWN UNIVERSITY

		     COMPUTER SCIENCE COLLOQUIUM

				
			       presents

			    Michael Bender
			     
			   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

			       
			       Abstract

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