Optimality in External Memory Hashing

Morten Skaarup Jensen, Rasmus Pagh

    Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

    Abstract

    Hash tables on external memory are commonly used for indexing in database management systems. In this paper we present an algorithm that, in an asymptotic sense, achieves the best possible I/O and space complexities. Let B denote the number of records that fit in a block, and let N denote the total number of records. Our hash table uses 1+𝑂(1/√B) I/Os, expected, for looking up a record (no matter if it is present or not). To insert, delete or change a record that has just been looked up requires 1+𝑂(1/√B) I/Os, amortized expected, including I/Os for reorganizing the hash table when the size of the database changes. The expected external space usage is 1+𝑂(1/√B) times the optimum of N/B blocks, and just O(1) blocks of internal memory are needed.
    OriginalsprogEngelsk
    TidsskriftAlgorithmica
    Vol/bind52
    Udgave nummer3
    Sider (fra-til)403-411
    Antal sider9
    ISSN0178-4617
    DOI
    StatusUdgivet - 2008

    Emneord

    • External memory
    • Dictionary
    • Hashing
    • Index

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Optimality in External Memory Hashing'. Sammen danner de et unikt fingeraftryk.

    Citationsformater