Events - Colloquia & Seminars

CCIS Colloquia Spring 2004
Cache-Oblivious Searching

Michael A. Bender
SUNY Stony Brook & MIT

Date:Apr 20, 2004
Talk:11:00am, 149 Cullinane

Abstract

We present recent developments in cache-oblivious search trees. Cache-oblivious data structures and algorithms are platform independent, achieving nearly optimal locality of reference simultaneously at every granularity. Thus, cache-oblivious data structures free the programmer from the burden of tuning the code for cache and disk effects. Because cache-oblivious data structures optimize all levels of the memory hierarchy, they hold the promise of outperforming traditional data structures and algorithms.