Key-independent optimality

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

References

↑ "John Iacono. Key independent optimality. Algorithmica, 42(1):3-10, 2005." (PDF).

This article is issued from Wikipedia - version of the 5/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.