The cost of cache-oblivious searching

M. A. Bender, G. S. Brodal, R. Fagerberg, D. Ge, Simai He, Haodung Hu, J. Iacono, A. López-Ortiz

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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/sub B/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/ lgB)] logB N + 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 modeled. 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)
    Title of host publicationProceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
    PublisherIEEE Computer Society
    Pages271-282
    Number of pages12
    ISBN (Electronic)0769520405
    DOIs
    StatePublished - 2003
    Event44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States
    Duration: Oct 11 2003Oct 14 2003

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    Volume2003-January
    ISSN (Print)0272-5428

    Other

    Other44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
    CountryUnited States
    CityCambridge
    Period10/11/0310/14/03

    Keywords

    • Algorithm design and analysis
    • Computational modeling
    • Computer science
    • Contracts
    • Cost function
    • Helium
    • Information science
    • Laboratories
    • Random access memory
    • Read-write memory

    ASJC Scopus subject areas

    • Computer Science(all)

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

    Cite this