Iacono's working set structure
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 formula_1 elements. The working set of an item formula_2 is the set of elements that have been accessed in the structure since the last time that formula_2 was accessed (or inserted if it was never accessed). Inserting and deleting in the working set structure takes formula_4 time while accessing an element formula_2 takes formula_6. Here, formula_7 represents the size of the working set of formula_2. Structure. To store a  dynamic set of formula_1 elements, this structure consists of a series of "Red–black trees", or other "Self-balancing binary search trees" formula_10, and a series of "deques" (Double-ended queues) formula_11, where formula_12. For every formula_13, tree formula_14 and deque formula_15 share the same contents and pointers are maintained between their corresponding elements. For every formula_16, the size of formula_14 and formula_15 is formula_19. Tree formula_20 and deque formula_21 consist of the remaining elements, i.e., their size is formula_22. Therefore, the number of items in all trees and the number of elements in all deques both add up to  formula_1. 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 formula_2 lies after formula_25 in deque formula_15 if and only if formula_27. Moreover, for every formula_28, the elements in deque formula_15 have a smaller working sets than the elements in deque formula_30. 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 formula_31 to formula_32, where formula_31 and formula_32 are indices of some trees in the structure. Two cases are considered in a shift from formula_31 to formula_32: If formula_37, then for every formula_38, taken in increasing order, an item is dequeued from formula_15 and enqueued into formula_30. The corresponding item is deleted from formula_14 and inserted into formula_42. The running time of this operation is formula_43. Analogously, if formula_44, then for every formula_45, taken in decreasing order, an item is dequeued from formula_15 and enqueued into formula_47. The corresponding item is  deleted from formula_14 and inserted into formula_49. The running time of this operation is formula_50. Regardless of the case, after a shift operation, the size of formula_51 decreases by one whereas the size of formula_52 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 formula_2, search for formula_2 in formula_55, in increasing order, until finding a tree formula_52 containing formula_2. If no tree is found, the search is unsuccessful. If formula_2 is found, it is deleted from  formula_52 and then inserted into formula_60, i.e., it is moved to the front of the structure. The search finishes by performing a shift from formula_61 to formula_32 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 formula_63 if the search was successful, or formula_64 otherwise. By the Working set property, every element in trees formula_65 belongs to the working set of formula_2. In particular, every element in formula_67 belongs to the working set of formula_2 and hence, formula_69. Thus, the running time of a  successful search is formula_70. Insert. Inserting an element formula_2 into the structure is performed by inserting formula_2 into formula_60 and enqueuing it into formula_74. Insertion is completed by performing a shift from formula_61 to formula_76. To avoid overflow, if formula_77 before the shift, i.e., if the last tree is full, then formula_76 is incremented and a new empty formula_20 and formula_21 is created. The running time of this operation is dominated by the shift from formula_61 to formula_76 whose running time is formula_83. Since element formula_2, whose working set is the smallest, is enqueued in formula_74, the Working set invariant  is preserved after the shift. Delete. Deleting an element formula_2 is done by searching for formula_2 on each tree in the structure, in increasing order, until finding a tree formula_52 that contains it (if non is found the deletion is unsuccessful). Item formula_2 is deleted from formula_52 and formula_91. Finally, a shift from formula_76 to formula_32 maintains the size of formula_52 equal to formula_95. The running time of this operation is formula_96. 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 in 1985. Using restructuring heuristic, splay trees are able to achieve insert and delete operations in formula_4 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 formula_6 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.