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 [math]\displaystyle{ m }[/math] keys [math]\displaystyle{ X = x_1, x_2, \cdots, x_m }[/math], where each [math]\displaystyle{ x_i }[/math] is a number between [math]\displaystyle{ 1 }[/math] and [math]\displaystyle{ n }[/math]. For each sequence [math]\displaystyle{ X }[/math], let [math]\displaystyle{ \textit{OPT}(X) }[/math] be the fastest binary search tree algorithm that looks up the elements in [math]\displaystyle{ X }[/math] in order. Let [math]\displaystyle{ b }[/math] be one of the [math]\displaystyle{ n! }[/math] possible permutation of the sequence [math]\displaystyle{ 1, 2, \cdots, n }[/math], chosen at random, where [math]\displaystyle{ b(i) }[/math] is the [math]\displaystyle{ i }[/math]th entry of [math]\displaystyle{ b }[/math]. Let [math]\displaystyle{ b(X) = b(x_1), b(x_2), \cdots ,b(x_m) }[/math]. Iacono defined, for a sequence [math]\displaystyle{ X }[/math], that [math]\displaystyle{ \textit{KIOPT}(X) = E[\textit{OPT}(b(X))] }[/math].

A data structure has key-independent optimality if it can lookup the elements in [math]\displaystyle{ X }[/math] in time [math]\displaystyle{ O(\textit{KIOPT}(X)) }[/math].

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.