The cost of cache-oblivious searching

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

    Research output: Contribution to journalConference articlepeer-review


    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(lg lg 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 logB N + 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.

    Original languageEnglish (US)
    Pages (from-to)271-282
    Number of pages12
    JournalAnnual Symposium on Foundations of Computer Science - Proceedings
    StatePublished - 2003
    EventProceedings: 44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003 - Cambridge, MA, United States
    Duration: Oct 11 2003Oct 14 2003

    ASJC Scopus subject areas

    • Hardware and Architecture


    Dive into the research topics of 'The cost of cache-oblivious searching'. Together they form a unique fingerprint.

    Cite this