Using hashing to solve the dictionary problem (In external memory)

John Iacono, Mihai Pǎtraşcu

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

    Abstract

    We consider the dictionary problem in external memory and improve the update time of the well-known buffer tree by roughly a logarithmic factor. For any λ ≥ max{lg lg n, logM/B(n/B)}, we can support updates in time O(λ/B) and queries in sublogarithmic time, O(log λ n). We also present a lower bound in the cell-probe model showing that our data structure is optimal. In the RAM, hash tables have been use to solve the dictionary problem faster than binary search for more than half a century. By contrast, our data structure is the first to beat the comparison barrier in external memory. Ours is also the first data structure to depart convincingly from the indivisibility paradigm.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    PublisherAssociation for Computing Machinery
    Pages570-582
    Number of pages13
    ISBN (Print)9781611972108
    DOIs
    StatePublished - 2012
    Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
    Duration: Jan 17 2012Jan 19 2012

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    CountryJapan
    CityKyoto
    Period1/17/121/19/12

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Using hashing to solve the dictionary problem (In external memory)'. Together they form a unique fingerprint.

  • Cite this

    Iacono, J., & Pǎtraşcu, M. (2012). Using hashing to solve the dictionary problem (In external memory). In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 (pp. 570-582). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.48