Key independent optimality

John Iacono

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


    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
    Number of pages7
    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


    Other13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
    CityVancouver, BC

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


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

    Cite this