Puneet Varma (Editor)

Key independent optimality

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Definitions

There are many binary search tree algorithms that can look up a sequence of m keys X = x 1 , x 2 , ⋯ , x m , where each x i is a number between 1 and n . For each sequence X , let 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 , ⋯ , n , chosen at random, where b ( i ) is the i th entry of b . Let b ( X ) = b ( x 1 ) , b ( x 2 ) , ⋯ , b ( x m ) . Iacono defined, for a sequence X , that KIOPT ( X ) = E [ OPT ( b ( X ) ) ] .

A data structure has key-independent optimality if it can lookup the elements in X in time O ( 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

Key-independent optimality Wikipedia
(Text) CC BY-SA