Key independent optimality

John Iacono

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

    Abstract

    A new form of optimality for comparison based static dictionaries is introduced. This type of optimality, key-independent optimality, is motivated by applications that assign key values randomly. It is shown that any data structure that is key-independently optimal is expected to execute any access sequence where the key values are assigned arbitrarily to unordered data as fast as any offline binary search tree algorithm, within a multiplicative constant. Asymptotically tight upper and lower bounds are presented for key-independent optimality. Splay trees are shown to be key-independently optimal.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
    Pages25-31
    Number of pages7
    DOIs
    StatePublished - 2002
    Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada
    Duration: Nov 21 2002Nov 23 2002

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume2518 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
    CountryCanada
    CityVancouver, BC
    Period11/21/0211/23/02

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Key independent optimality'. Together they form a unique fingerprint.

  • Cite this

    Iacono, J. (2002). Key independent optimality. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (pp. 25-31). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). https://doi.org/10.1007/3-540-36136-7_3