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

    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. 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
    Pages29-38
    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
    Volume06-08-January-2002

    Other

    Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
    CountryUnited States
    CitySan Francisco
    Period1/6/021/8/02

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

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

  • Cite this

    Bender, M. A., Duan, Z., Iacono, J., & Wu, J. (2002). A locality-preserving cache-oblivious dynamic dictionary. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 (pp. 29-38). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002). Association for Computing Machinery.