Iacono's Working Set Structure

This site gives a description of Iacono's Working Set Structure, a search structure achieving the same runtime bounds as Splay Trees with better single access worst case bounds.

It will also include an application into analysis of parallel search structures.

You can use the menu bar at the top-left of the page to navigate.

Balanced binary search trees, such as red-black trees, are elementary search structures that give O(logn) worst case access times regardless of access patterns, where n is the number of nodes in the tree. This means for a sequence of m operations (insert, search, delete), the runtime is bounded by O(mlogn) worst case. They generally utilize extra information stored at each node to perform rotations that will keep the tree O(logn) height-balanced.

A Splay Tree is a type of binary search tree that "splays" a node to the root after it is accessed. For example, when a node is inserted at the leaf level, the tree undergoes a series of rotations so that this node becomes the root.

Splaying as a balancing heuristic achieves many desirable properties for the structure of the tree regarding access patterns, but does not guarantee height balance. Therefore, Splay Trees only achieve O(n) worst case for single operations.

Fortunately, for a sequence of m operations with arbitrary access patterns, the runtime is bounded by O(mlogn) using amortized analysis, so O(logn) amortized per operation. In addition, for items that are accessed multiple times, rotating accessed elements to the root generally leads to faster access times in the future. The Splay Tree is therefore sensitive and more efficient to responding to input frequency regarding elements.

Iacono's Working Set Structure is a search structure that reconciles this disadvantage: it achieves similar input response as Splay Trees, but with a single operation worst case guarantee of O(logn) like red-black trees. It is built around a desirable performance theorem of Splay Trees: the Working Set Theorem.