Key-independent optimality

John Iacono

doi:10.1007/s00453-004-1136-8

Key-independent optimality

John Iacono

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	3-10
Number of pages	8
Journal	Algorithmica (New York)
Volume	42
Issue number	1
DOIs	https://doi.org/10.1007/s00453-004-1136-8
State	Published - Mar 2005

Keywords

Data structures
Dictionary
Splay tree

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-004-1136-8

Cite this

@article{73e5adc6999d4ae8a418e43ec350a174,

title = "Key-independent optimality",

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.",

keywords = "Data structures, Dictionary, Splay tree",

author = "John Iacono",

year = "2005",

month = mar,

doi = "10.1007/s00453-004-1136-8",

language = "English (US)",

volume = "42",

pages = "3--10",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Key-independent optimality

AU - Iacono, John

PY - 2005/3

Y1 - 2005/3

N2 - 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.

AB - 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.

KW - Data structures

KW - Dictionary

KW - Splay tree

UR - http://www.scopus.com/inward/record.url?scp=17444402785&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17444402785&partnerID=8YFLogxK

U2 - 10.1007/s00453-004-1136-8

DO - 10.1007/s00453-004-1136-8

M3 - Article

AN - SCOPUS:17444402785

SN - 0178-4617

VL - 42

SP - 3

EP - 10

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -

Key-independent optimality

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this