The Cost of Cache-Oblivious Searching

Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz

In Proc. 44th Annual Symposium on Foundations of Computer Science, pages 271-282, 2003.


Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e logB N block transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e+O(lglg B/lg B)] logBN +O(1). This factor approaches lg e ≈ 1.443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory.

As searching in the Disk Access Model (DAM) can be performed in logBN+1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modelled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.

Copyright notice

Copyright © 2003 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Online version

focs03.pdf (208 Kb)



BIBTEX entry

  author = "Michael A. Bender and Gerth St{\o}lting Brodal and Rolf Fagerberg and Dongdong Ge and Simai He and Haodong Hu and John Iacono and Alejandro L\'opez-Ortiz",
  booktitle = "Proc. 44th Annual Symposium on Foundations of Computer Science",
  doi = "10.1109/SFCS.2003.1238201",
  isbn = "0272-5428",
  pages = "271-282",
  title = "The Cost of Cache-Oblivious Searching",
  year = "2003"