Key-independent optimality

Key-independent optimality is a property of some binary search tree data structures in computer science proposed by John Iacono.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Key-independent optimality is a property of some binary search tree data structures in computer science proposed by John Iacono. Suppose that key-value pairs are stored in a data structure, and that the keys have no relation to their paired values.

A data structure has key-independent optimality if, when randomly assigning the keys, the expected performance of the data structure is within a constant factor of the optimal data structure. Key-independent optimality is related to dynamic optimality.

Definitions

There are many binary search tree algorithms that can look up a sequence of m keys X = x_1, x_2, \cdots, x_m , where each x_i is a number between 1 and n . For each sequence X , let \textit{OPT}(X) be the fastest binary search tree algorithm that looks up the elements in X in order. Let b be one of the n! possible permutation of the sequence 1, 2, \cdots, n , chosen at random, where b(i) is the i th entry of b . Let b(X) = b(x_1), b(x_2), \cdots ,b(x_m) . Iacono defined, for a sequence X , that \textit{KIOPT}(X) = E[\textit{OPT}(b(X))] . A data structure has key-independent optimality if it can lookup the elements in X in time O(\textit{KIOPT}(X)) .

Relationship with other bounds

Key-independent optimality has been proved to be asymptotically equivalent to the working set theorem. Splay trees are known to have key-independent optimality.

Text derived from https://en.wikipedia.org/w/index.php?oldid=918820007 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-000918820007 · captured 2019-09-30 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Key-independent optimality”, snapshot enwiki-000918820007. https://encyclopegia.org/a/key-independent-optimality

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.