Key independent optimality

John Iacono

doi:10.1007/3-540-36136-7_3

Key independent optimality

John Iacono

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Pages	25-31
Number of pages	7
DOIs	https://doi.org/10.1007/3-540-36136-7_3
State	Published - 2002
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: Nov 21 2002 → Nov 23 2002

Publication series

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

Other

Other	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Country/Territory	Canada
City	Vancouver, BC
Period	11/21/02 → 11/23/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36136-7_3

Cite this

Key independent optimality. / Iacono, John.
Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. p. 25-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Iacono, J 2002, Key independent optimality. in Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2518 LNCS, pp. 25-31, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, 11/21/02. https://doi.org/10.1007/3-540-36136-7_3

@inproceedings{a69a66a312ed42739642b03929c721cb,

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

author = "John Iacono",

year = "2002",

doi = "10.1007/3-540-36136-7_3",

language = "English (US)",

isbn = "3540001425",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "25--31",

booktitle = "Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings",

note = "13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 ; Conference date: 21-11-2002 Through 23-11-2002",

}

TY - GEN

T1 - Key independent optimality

AU - Iacono, John

PY - 2002

Y1 - 2002

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.

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

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

U2 - 10.1007/3-540-36136-7_3

DO - 10.1007/3-540-36136-7_3

M3 - Conference contribution

AN - SCOPUS:23044533159

SN - 3540001425

SN - 9783540001423

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 31

BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -

Key independent optimality

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this