en>Gilliam: Reverted edits by 63.133.246.253 (talk) to last version by Allthingstoallpeople

2014-01-31T15:46:30Z

Reverted edits by 63.133.246.253 (talk) to last version by Allthingstoallpeople

New page

{| class="infobox" style="width: 20em"
! colspan="2" style="font-size: 125%; text-align: center" | Iacono's working set data structure
|-
! Invented
| 2001
|-
! Invented by
| [[John Iacono]]
|-
! colspan="2" style="text-align: center; background-color: #CCCCFF; color: #000000;" | Asymptotic complexity<br />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<ref name=WorkingSetStructure /> is a comparison based [[associative array|dictionary]]. It supports insertion, deletion and access operation to maintain a dynamic set of <math>n</math> elements.
The working set of an item <math>x</math> is the set of elements that have been accessed in the structure since the last time that <math>x</math> was accessed (or inserted if it was never accessed).
Inserting and deleting in the working set structure takes <math>O(\log n)</math> time while accessing an element <math>x</math> takes <math>O(\log w(x))</math>. Here, <math>w(x)</math> represents the size of the working set of <math>x</math>.

==Structure==

[[File:Working Set DS.svg|thumbnail|An example of a search for <math>x</math> in the working set structure. After finding <math>x</math>, it is removed from <math>T_4</math> and inserted into <math>T_1</math>. Finally, a shift from 1 to 4 is performed in which an element is removed from <math>T_i</math> and inserted into <math>T_{i+1}</math> for <math>1\leq i <4</math>.]]
To store a dynamic set of <math>n</math> elements, this structure consists of a series of ''[[Red–black tree]]''s, or other ''[[Self-balancing binary search tree]]''s <math>T_1, T_2, \ldots, T_k</math>, and a series of ''[[Double-ended queue|deques]]'' (Double-ended queues) <math>Q_1, Q_2, \ldots Q_k</math>, where <math>k = \lceil \log\log n\rceil</math>. For every <math>1\leq i\leq k</math>, tree <math>T_i</math> and deque <math>Q_i</math> share the same contents and pointers are maintained between their corresponding elements. For every <math> i < k </math>, the size of <math>T_i</math> and <math>Q_i</math> is <math>2^{2^i}</math>. Tree <math>T_k</math> and deque <math>Q_k</math> consist of the remaining elements, i.e., their size is <math>n - \sum_{i=1}^{k-1} 2^{2^i}</math>. Therefore, the number of items in all trees and the number of elements in all deques both add up to <math>n</math>.
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 <math>x</math> lies after <math>y</math> in deque <math>Q_i</math> if and only if <math>w(x)< w(y)</math>. Moreover, for every <math>1\leq i < k</math>, the elements in deque <math>Q_i</math> have a smaller working sets than the elements in deque <math>Q_{i+1}</math>. 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 <math>h</math> to <math>j</math>, where <math>h</math> and <math>j</math> are indices of some trees in the structure.
Two cases are considered in a shift from <math>h</math> to <math>j</math>: If <math>h< j</math>, then for every <math>h\leq i < j</math>, taken in increasing order, an item is dequeued from <math>Q_i</math> and enqueued into <math>Q_{i+1}</math>. The corresponding item is deleted from <math>T_i</math> and inserted into <math>T_{i+1}</math>. The running time of this operation is <math>O(\sum_{i=h}^{j} \log |T_i|) = O(\sum_{i=h}^{j} \log 2^{2^i}) = O(2^ j)</math>.
Analogously, if <math> j< h</math>, then for every <math>j < i \leq h</math>, taken in decreasing order, an item is dequeued from <math>Q_i</math> and enqueued into <math>Q_{i-1}</math>. The corresponding item is deleted from <math>T_i</math> and inserted into <math>T_{i-1}</math>. The running time of this operation is <math>O(\sum_{i=j}^{h} \log |T_i|) = O(\sum_{i=j}^{h} \log 2^{2^i}) = O(2^ h)</math>.
Regardless of the case, after a shift operation, the size of <math>T_h</math> decreases by one whereas the size of <math>T_j</math> 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 <math>x</math>, search for <math>x</math> in <math>T_1, T_2, \ldots T_k</math>, in increasing order, until finding a tree <math>T_j</math> containing <math>x</math>. If no tree is found, the search is unsuccessful. If <math>x</math> is found, it is deleted from <math>T_j</math> and then inserted into <math>T_1</math>, i.e., it is moved to the front of the structure. The search finishes by performing a shift from <math>1</math> to <math>j</math> 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 <math>O(\sum_{i=1}^{j} \log 2^{2^i}) = O(2^ j)</math> if the search was successful, or <math>O(\sum_{i=j}^{k} \log 2^{2^i}) = O(2^k) = O(\log n)</math> otherwise.
By the Working set property, every element in trees <math>T_1, T_2, \ldots, T_{j-1}</math> belongs to the working set of <math>x</math>. In particular, every element in <math>T_{j-1}</math> belongs to the working set of <math>x</math> and hence, <math>w(x) > |T_{j-1}| = 2^{2^{j-1}}</math>. Thus, the running time of a successful search is <math>O(2^j) = O(\log 2^{2^{j-1}}) = O(\log w(x))</math>.

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

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

==Discussion==
''[[Splay tree]]''s are self adjusting search trees introduced by Sleator and Tarjan<ref name="SleatorTarjan" /> in 1985. Using restructuring heuristic, splay trees are able to achieve insert and delete operations in <math>O(\log n)</math> [[amortized analysis|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 <math>O(\log w(x))</math> [[amortized analysis|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==
{{Reflist|refs=
<ref name=WorkingSetStructure>{{cite journal|last=Iacono|first=John|title=Alternatives to splay trees with O(log n) worst-case access times|journal=Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms|year=2001|pages=516–522| url= http://divespot.ca/~morin/teaching/5408/refs/i2001.pdf}}</ref>

<ref name="SleatorTarjan">{{Citation |first1=Daniel D. |last1=Sleator |first2=Robert E. |last2=Tarjan |title=Self-Adjusting Binary Search Trees |url=http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf |journal=Journal of the ACM ([[Association for Computing Machinery]]) |volume=32 |issue=3 |pages=652–686 |year= 1985 |doi=10.1145/3828.3835 }}</ref>
}}

[[Category:Trees (data structures)]]

Parent function - Revision history

en>Gilliam: Reverted edits by 63.133.246.253 (talk) to last version by Allthingstoallpeople