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

Technical Report, ALCOMFT-TR-03-76, ALCOM-FT, 18 pages, November 2003.

Abstract

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 log_BN 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)] log_BN +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 log_BN+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.

Online version

alcomft-tr-03-76.pdf (210 Kb)

BIBT_EX entry

@techreport{alcomft-tr-03-76,
  author = "Michael A. Bender and Gerth Stølting Brodal and Rolf Fagerberg and  Dongdong Ge and Simai He and Haodong Hu and John Iacono and Alejandro López-Ortiz",
  institution = "ALCOM-FT",
  month = "November",
  number = "ALCOMFT-TR-03-76",
  pages = "18",
  title = "The Cost of Cache-Oblivious Searching",
  year = "2003"
}