Constructing Efficient Dictionaries in Close to Sorting Time

Milan Ruzic

    Publikation: Artikel i tidsskrift og konference artikel i tidsskriftKonferenceartikelForskningpeer review

    Abstract

    The dictionary problem is among the oldest problems in computer science. Yet our understanding of the complexity of the dictionary problem in realistic models of computation has been far from complete. Designing highly efficient dictionaries without resorting to use of randomness appeared to be a particularly challenging task. We present solutions to the static dictionary problem that significantly improve the previously known upper bounds and bring them close to obvious lower bounds. Our dictionaries have a constant lookup cost and use linear space, which was known to be possible, but the worst-case cost of construction of the structures is proportional to only loglogn times the cost of sorting the input. Our claimed performance bounds are obtained in the word RAM model and in the external memory models; only the involved sorting procedures in the algorithms need to be changed between the models.
    OriginalsprogEngelsk
    BogserieLecture Notes in Computer Science
    Sider (fra-til)84-95
    ISSN0302-9743
    StatusUdgivet - 2008
    BegivenhedICALP 2008 35th International Colloquium on Automata, Languages and Programming - Reykjavik, Island
    Varighed: 6 jul. 200813 jul. 2008
    Konferencens nummer: 35

    Konference

    KonferenceICALP 2008 35th International Colloquium on Automata, Languages and Programming
    Nummer35
    Land/OmrådeIsland
    ByReykjavik
    Periode06/07/200813/07/2008

    Emneord

    • Dictionary problem
    • Complexity
    • Word RAM model
    • Static dictionaries
    • External memory

    Citationsformater