Cache-Oblivious Search Trees Project


SuperTech Home  |  About SuperTech  |  Group Members  |  Cilk  |  Papers  |  Opportunities For Students  |  Contact Us  |  News  |  Group Calendar


.: This is the Home Page for Cache-Oblivious Search Trees :.

About This Project

We implemented a cache-oblivious dynamic search tree as an alternative to the ubiquitious B-tree. We used a binary tree with a "van Emde Boas" layout whose leaves point to intervals in a "packed memory structure". The search tree supports efficient lookup, as well as efficient amortized insertion and deletion. Efficient implementation of a B-tree requires understanding the cache-line size and page size and is optimized for a specific memory hierarchy. In contrast, a cache-oblivious dynamic search tree contains no machine-dependent variables, performs well on any memory hierarchy, and requires minimal user-level memory management. For random insertion of data, the data structure performs better than the Berkeley DB and a good implementation of B-trees. Another advantage of my data structure is that the packed memory array maintains data in sorted order, allows sequential reads at high speeds, and data insertions and deletions with few data writes on average. In addition, the data structure is easy to implement because he employed memory mapping rather than making the data stored on disk be a single level store.

We also have designed cache-oblivious search trees for which the keys can be very long (imagine a key, such as a DNA sequence, that is larger than main memory), and trees into which data can be quickly inserted.

People to Contact

Bradley C. Kuszmaul (Faculty)
Jeremy T. Fineman (Alumni)

Papers

Cache-Oblivious Streaming B-trees
by Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley Kuszmaul, and Jelani Nelson
Proceedings of the Nineteenth ACM Symposium on Parallelism in Algorithms and Architectures
San Diego, CA, USA
Pages: 81–92
June 9–11, 2007
To download the paper: ps format  pdf format 
BibTeX

Cache-Oblivious String B-Trees
by Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul
Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Chicago, IL
Pages: 223–242
June, 2006
To download the paper: pdf format 
BibTeX


Concurrent Cache-Oblivious B-Trees
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul
Proceedings of the Seventeenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Las Vegas, NV, USA
Pages: 228–237
July 17–20, 2005
To download the paper: ps format  pdf format 
BibTeX

Cache-Oblivious Dynamic Search Trees
by Zardosht Kasheff
Master's Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
June, 2004
To download the paper: pdf format 
BibTeX


Cache-Oblivious Algorithms
by Harald Prokop
Master's Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
June, 1999
To download the paper: ps format  pdf format 
BibTeX


 

(c) Copyright 2004 Massachusetts Institute of Technology
Last updated: 19:53:33 Tue May 24, 2011
by neboat

Valid XHTML 1.0!