Key-independent optimality

John Iacono

    Research output: Contribution to journalArticlepeer-review

    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)
    Pages (from-to)3-10
    Number of pages8
    JournalAlgorithmica (New York)
    Volume42
    Issue number1
    DOIs
    StatePublished - Mar 2005

    Keywords

    • Data structures
    • Dictionary
    • Splay tree

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

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

    Cite this