In computer science, Iacono's working set structure is a comparison based dictionary. It supports insertion, deletion and access operation to maintain a dynamic set of n {\displaystyle n} elements. The working set of an item x {\displaystyle x} is the set of elements that have been accessed in the structure since the last time that x {\displaystyle x} was accessed (or inserted if it was never accessed). Inserting and deleting in the working set structure takes O ( log n ) {\displaystyle O(\log n)} time while accessing an element x {\displaystyle x} takes O ( log w ( x ) ) {\displaystyle O(\log w(x))} . Here, w ( x ) {\displaystyle w(x)} represents the size of the working set of x {\displaystyle x} .
Structure
To store a dynamic set of n {\displaystyle n} elements, this structure consists of a series of Red–black trees, or other Self-balancing binary search trees T 1 , T 2 , … , T k {\displaystyle T_{1},T_{2},\ldots ,T_{k}} , and a series of deques (Double-ended queues) Q 1 , Q 2 , … Q k {\displaystyle Q_{1},Q_{2},\ldots Q_{k}} , where k = ⌈ log log n ⌉ {\displaystyle k=\lceil \log \log n\rceil } . For every 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} , tree T i {\displaystyle T_{i}} and deque Q i {\displaystyle Q_{i}} share the same contents and pointers are maintained between their corresponding elements. For every i < k {\displaystyle i<k} , the size of T i {\displaystyle T_{i}} and Q i {\displaystyle Q_{i}} is 2 2 i {\displaystyle 2^{2^{i}}} . Tree T k {\displaystyle T_{k}} and deque Q k {\displaystyle Q_{k}} consist of the remaining elements, i.e., their size is n − ∑ i = 1 k − 1 2 2 i {\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 n {\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 x {\displaystyle x} lies after y {\displaystyle y} in deque Q i {\displaystyle Q_{i}} if and only if w ( x ) < w ( y ) {\displaystyle w(x)<w(y)} . Moreover, for every 1 ≤ i < k {\displaystyle 1\leq i<k} , the elements in deque Q i {\displaystyle Q_{i}} have a smaller working sets than the elements in deque Q i + 1 {\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.
… excerpt ends here. Continue reading the full article.
