A locality-preserving cache-oblivious dynamic dictionary

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

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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. The structure supports search operations on N data items using O(logBN + 1) block transfers at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(logBN + log2N/B + 1) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(logBN + k/B + 1) block transfers. 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)
    Pages (from-to)115-136
    Number of pages22
    JournalJournal of Algorithms
    Volume53
    Issue number2
    DOIs
    StatePublished - Nov 2004

    ASJC Scopus subject areas

    • Control and Optimization
    • Computational Mathematics
    • Computational Theory and Mathematics

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

    Cite this