# Iacono's working set structure

Iacono's working set data structure
Invented 2001
Invented by John Iacono
Asymptotic complexity
in big O notation
Space O(n)
Search O(log w(x))
Insert O(log n)
Delete O(log n)

In computer science, Iacono's working set structure[1] is a comparison based dictionary. It supports insertion, deletion and access operation to maintain a dynamic set of ${\displaystyle n}$ elements. The working set of an item ${\displaystyle x}$ is the set of elements that have been accessed in the structure since the last time that ${\displaystyle x}$ was accessed (or inserted if it was never accessed). Inserting and deleting in the working set structure takes ${\displaystyle O(\log n)}$ time while accessing an element ${\displaystyle x}$ takes ${\displaystyle O(\log w(x))}$. Here, ${\displaystyle w(x)}$ represents the size of the working set of ${\displaystyle x}$.

## Structure

An example of a search for ${\displaystyle x}$ in the working set structure. After finding ${\displaystyle x}$, it is removed from ${\displaystyle T_{4}}$ and inserted into ${\displaystyle T_{1}}$. Finally, a shift from 1 to 4 is performed in which an element is removed from ${\displaystyle T_{i}}$ and inserted into ${\displaystyle T_{i+1}}$ for ${\displaystyle 1\leq i<4}$.

To store a dynamic set of ${\displaystyle n}$ elements, this structure consists of a series of Red–black trees, or other Self-balancing binary search trees ${\displaystyle T_{1},T_{2},\ldots ,T_{k}}$, and a series of deques (Double-ended queues) ${\displaystyle Q_{1},Q_{2},\ldots Q_{k}}$, where ${\displaystyle k=\lceil \log \log n\rceil }$. For every ${\displaystyle 1\leq i\leq k}$, tree ${\displaystyle T_{i}}$ and deque ${\displaystyle Q_{i}}$ share the same contents and pointers are maintained between their corresponding elements. For every ${\displaystyle i, the size of ${\displaystyle T_{i}}$ and ${\displaystyle Q_{i}}$ is ${\displaystyle 2^{2^{i}}}$. Tree ${\displaystyle T_{k}}$ and deque ${\displaystyle Q_{k}}$ consist of the remaining elements, i.e., their size is ${\displaystyle n-\sum _{i=1}^{k-1}2^{2^{i}}}$. Therefore, the number of items in all trees and the number of elements in all deques both add up to ${\displaystyle n}$. Every element that has been inserted in the data structure is stored in exactly one of the trees and its corresponding deque.

## Working set Invariant

In the deques of this structure, elements are kept in sorted order according to their working set size. Formally, element ${\displaystyle x}$ lies after ${\displaystyle y}$ in deque ${\displaystyle Q_{i}}$ if and only if ${\displaystyle w(x). Moreover, for every ${\displaystyle 1\leq i, the elements in deque ${\displaystyle Q_{i}}$ have a smaller working sets than the elements in deque ${\displaystyle Q_{i+1}}$. This property is referred to as the Working set invariant. Every operation in the data structure maintains the Working set invariant.

## Operations

The basic operation in this structure is called shift from ${\displaystyle h}$ to ${\displaystyle j}$, where ${\displaystyle h}$ and ${\displaystyle j}$ are indices of some trees in the structure. Two cases are considered in a shift from ${\displaystyle h}$ to ${\displaystyle j}$: If ${\displaystyle h, then for every ${\displaystyle h\leq i, taken in increasing order, an item is dequeued from ${\displaystyle Q_{i}}$ and enqueued into ${\displaystyle Q_{i+1}}$. The corresponding item is deleted from ${\displaystyle T_{i}}$ and inserted into ${\displaystyle T_{i+1}}$. The running time of this operation is ${\displaystyle O(\sum _{i=h}^{j}\log |T_{i}|)=O(\sum _{i=h}^{j}\log 2^{2^{i}})=O(2^{j})}$. Analogously, if ${\displaystyle j, then for every ${\displaystyle j, taken in decreasing order, an item is dequeued from ${\displaystyle Q_{i}}$ and enqueued into ${\displaystyle Q_{i-1}}$. The corresponding item is deleted from ${\displaystyle T_{i}}$ and inserted into ${\displaystyle T_{i-1}}$. The running time of this operation is ${\displaystyle O(\sum _{i=j}^{h}\log |T_{i}|)=O(\sum _{i=j}^{h}\log 2^{2^{i}})=O(2^{h})}$. Regardless of the case, after a shift operation, the size of ${\displaystyle T_{h}}$ decreases by one whereas the size of ${\displaystyle T_{j}}$ increases by one. Since that elements in the deques are sorted with respect to their working sets sizes, a shift operation maintains the Working set invariant.

### Search

To search for an element ${\displaystyle x}$, search for ${\displaystyle x}$ in ${\displaystyle T_{1},T_{2},\ldots T_{k}}$, in increasing order, until finding a tree ${\displaystyle T_{j}}$ containing ${\displaystyle x}$. If no tree is found, the search is unsuccessful. If ${\displaystyle x}$ is found, it is deleted from ${\displaystyle T_{j}}$ and then inserted into ${\displaystyle T_{1}}$, i.e., it is moved to the front of the structure. The search finishes by performing a shift from ${\displaystyle 1}$ to ${\displaystyle j}$ which restores the size of every tree and every deque to their size prior to the search operation. The running time of this search is ${\displaystyle O(\sum _{i=1}^{j}\log 2^{2^{i}})=O(2^{j})}$ if the search was successful, or ${\displaystyle O(\sum _{i=j}^{k}\log 2^{2^{i}})=O(2^{k})=O(\log n)}$ otherwise. By the Working set property, every element in trees ${\displaystyle T_{1},T_{2},\ldots ,T_{j-1}}$ belongs to the working set of ${\displaystyle x}$. In particular, every element in ${\displaystyle T_{j-1}}$ belongs to the working set of ${\displaystyle x}$ and hence, ${\displaystyle w(x)>|T_{j-1}|=2^{2^{j-1}}}$. Thus, the running time of a successful search is ${\displaystyle O(2^{j})=O(\log 2^{2^{j-1}})=O(\log w(x))}$.

### Insert

Inserting an element ${\displaystyle x}$ into the structure is performed by inserting ${\displaystyle x}$ into ${\displaystyle T_{1}}$ and enqueuing it into ${\displaystyle Q_{1}}$. Insertion is completed by performing a shift from ${\displaystyle 1}$ to ${\displaystyle k}$. To avoid overflow, if ${\displaystyle |T_{k}|=2^{2^{k}}}$ before the shift, i.e., if the last tree is full, then ${\displaystyle k}$ is incremented and a new empty ${\displaystyle T_{k}}$ and ${\displaystyle Q_{k}}$ is created. The running time of this operation is dominated by the shift from ${\displaystyle 1}$ to ${\displaystyle k}$ whose running time is ${\displaystyle O(2^{k})=O(2^{\log \log n})=O(\log n)}$. Since element ${\displaystyle x}$, whose working set is the smallest, is enqueued in ${\displaystyle Q_{1}}$, the Working set invariant is preserved after the shift.

### Delete

Deleting an element ${\displaystyle x}$ is done by searching for ${\displaystyle x}$ on each tree in the structure, in increasing order, until finding a tree ${\displaystyle T_{j}}$ that contains it (if non is found the deletion is unsuccessful). Item ${\displaystyle x}$ is deleted from ${\displaystyle T_{j}}$ and ${\displaystyle Q_{j}}$. Finally, a shift from ${\displaystyle k}$ to ${\displaystyle j}$ maintains the size of ${\displaystyle T_{j}}$ equal to ${\displaystyle 2^{2^{j}}}$. The running time of this operation is ${\displaystyle O(2^{k})=O(\log n)}$. The working set invariant is preserved as deleting an element does not change the order of the working set of the elements.

## Discussion

Splay trees are self adjusting search trees introduced by Sleator and Tarjan[2] in 1985. Using restructuring heuristic, splay trees are able to achieve insert and delete operations in ${\displaystyle O(\log n)}$ amortized time, without storing any balance information at the nodes. Moreover, the Working Set Theorem for splay trees states that the cost to access an element in a splay tree is ${\displaystyle O(\log w(x))}$ amortized. Iacono's workings set structure obtains the same running time for search, insert and delete in the worst-case. Therefore, offering an alternative to splay trees.

## References

1. ^ Iacono, John (2001). "Alternatives to splay trees with O(log n) worst-case access times" (PDF). Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms: 516–522.
2. ^ Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees" (PDF), Journal of the ACM (Association for Computing Machinery), 32 (3): 652–686, doi:10.1145/3828.3835