Key-independent optimality
Key-independent optimality is a property of some binary search tree data structures in computer science proposed by John Iacono.
≈ 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.