Key-independent optimality

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 $\text{<mrow data-mjx-texclass="ORD">OPT</mrow>}(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 $\text{<mrow data-mjx-texclass="ORD">KIOPT</mrow>}(X)=E[\text{<mrow data-mjx-texclass="ORD">OPT</mrow>}(b(X))]$.

A data structure has key-independent optimality if it can lookup the elements in $X$ in time $O(\text{<mrow data-mjx-texclass="ORD">KIOPT</mrow>}(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.