key-independent optimality

Key-independent optimality is a property of some binary search tree data structures in computer science

proposed by John Iacono.{{cite web|title=John Iacono. Key independent optimality. Algorithmica, 42(1):3-10, 2005.|url=http://john2.poly.edu/papers/algo04/paper.pdf|url-status=dead|archiveurl=https://web.archive.org/web/20100613054302/http://john2.poly.edu/papers/algo04/paper.pdf|archivedate=2010-06-13}}

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 ith 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