A locality-preserving cache-oblivious dynamic dictionary

Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu

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


    This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache oblivious and locality preserving. A cache-oblivious data structure has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specific parameterization. A locality-preserving dictionary maintains elements of similar key values stored close together for fast access to ranges of data with consecutive keys. The data structure presented here is a simplification of the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton. Like the cache-oblivious B-tree, this structure supports search operations using only O(logB N) block operations at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(logB N + log2 N/B) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(logB JV + k/B) block operations. This data structure was implemented and its performance was evaluated on a simulated memory hierarchy. This paper presents the results of this simulation for various combinations of block and memory sizes.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
    PublisherAssociation for Computing Machinery
    Number of pages10
    ISBN (Electronic)089871513X
    StatePublished - 2002
    Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
    Duration: Jan 6 2002Jan 8 2002

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
    Country/TerritoryUnited States
    CitySan Francisco

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'A locality-preserving cache-oblivious dynamic dictionary'. Together they form a unique fingerprint.

    Cite this