Department of Computer Science
SUNY Stony Brook
(Visiting King's College London)
4pm Tuesday 2nd November 2004
Room 2511, JCMB, King's Buildings
Cache-oblivious algorithms and data structures are platform-independent. They run efficiently on a hierarchical memory, even though they avoid any memory-specific parameterization, such as cache-block sizes or access times.
We give an overview of the work on designing cache-oblivious algorithms and data structures. We then explain how to build cache-oblivious search trees, and we give results from our implementation study. Finally, we outline future directions in the area.