Cache-Oblivious Search Trees via Binary Trees of Small Height

Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob

In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 39-48, 2002.

Abstract

We propose a version of cache oblivious search trees which is simpler than the previous proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In particular, our data structure avoids the use of weight balanced B-trees, and can be implemented as just a single array of data elements, without the use of pointers. The structure also improves space utilization.

For storing n elements, our proposal uses (1+ε)n times the element size of memory, and performs searches in worst case O(logB n) memory transfers, updates in amortized O((log2 n)/(ε B)) memory transfers, and range queries in worst case O(logB n + k/B) memory transfers, where k is the size of the output.

The basic idea of our data structure is to maintain a dynamic binary tree of height log n+O(1) using existing methods, embed this tree in a static binary tree, which in turn is embedded in an array in a cache oblivious fashion, using the van Emde Boas layout of Prokop.

We also investigate the practicality of cache obliviousness in the area of search trees, by providing an empirical comparison of different methods for laying out a search tree in memory.

Copyright notice

Copyright © 2002 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda02.pdf (236 Kb)

DOI

doi.acm.org/10.1145/545381.545386

Note

The source code of the programs, our scripts and tools, and the data we present: brics-rs-01-36-experiments.tgz.

BIBTEX entry

@inproceedings{soda02,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Riko Jacob",
  booktitle = "Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "doi.acm.org/10.1145/545381.545386",
  isbn = "0-89871-513-X",
  pages = "39-48",
  title = "Cache-Oblivious Search Trees via Binary Trees of Small Height",
  year = "2002"
}

Other versions