About this Site

This site was created by Hamza Qureshi as an Algorithms 2 course project at NYU Tandon School of Engineering.

If you have any questions or comments, you can reach me at hq343@nyu.edu

References

Working Set Structure

Wikipedia page on Iacono's Working Set Structure: https://en.wikipedia.org/wiki/Iacono%27s_working_set_structure

John Iacono's original article on the Working Set Structure: http://cglab.ca/~morin/teaching/5408/refs/i2001.pdf

• The second part of the article relating to the unified structure was improved so the original Working Set Structure was reintroduced along with the revised unified structure in 2007: https://www.sciencedirect.com/science/article/pii/S0304397507001703?via%3Dihub

Splay Trees

Lecture Slides by Professor Keith Schwarz from Stanford University: http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/10/Small10.pdf

Wikipedia page on Splay Trees: https://en.wikipedia.org/wiki/Splay_tree

Sleator and Tarjan's article on Splay Trees: http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

Parallel Search Structures

Article on Implicit Batching: https://www.cse.wustl.edu/~kunal/resources/Papers/batcher.pdf

Article on Parallel Search Structure: https://arxiv.org/pdf/1805.05787.pdf

Extensions

There have been many papers published with extensions to the Working Set Structure, and in general, distribution sensitive data structures:

• Unified Structure:
  • Unified Conjecture - effectively combines the working set theorem and the dynamic finger theorem; access is fast if element is near a rank that has been recently accessed
    • Search for x will be logarithmic in the minimum of (working set of y + rank distance between x and y + 2) for y as any other element in the set
  • Static structure that fulfils this bound was introduced in Iacono's original 2001 paper; updated and dynamic structure with work from Baidou, Cole, Demaine published in 2007: https://www.sciencedirect.com/science/article/pii/S0304397507001703?via%3Dihub
• Distribution-sensitive priority queues:
  • Priority Queue with working-set property fulfilled in the worst case; paper also proves the working-set property is asymptotically equivalent to the (static) unified bound for Splay Trees (distinct from the above Unified Conjecture)
    • Unified bound (for Splay Trees) - "minimum per operation among the static-finger, static-optimality, and working-set bounds"
  • See: https://www.researchgate.net/publication/220266559_A_Unifying_Property_for_Distribution-Sensitive_Priority_Queues
  • Also see Queaps (does not achieve working set bound for deletes) : https://en.wikipedia.org/wiki/Queap
• Layered Working-Set Trees:
  • Iacono's Working Set Structure is a comparison-based dictionary rather than a tree - can't perform all normal tree operations
  • These trees guarantee the working-set property in the worst case
  • For more information, see: http://cglab.ca/~vida/pubs/papers/layered-ws.pdf
• Distribution-Sensitive Dictionary with Low Space Overhead
  • Discusses a space improvement to the Working Set Structure (removes queues and replaces BST's by using randomization)
    • Tradeoff - makes searches expected O(log(w(x)) rather than per operation worst case
    • Also discusses modification to allow expected O(log(w(x))) predecessor search time on an unsuccessful search rather than O(logn)
  • New structure that supports O(logn) insert/deletion and O(log(w(x)) expected search time with sublinear space besides the data
    • Additional O(log(logn)) words of memory, each of O(logn) bits - better than O(n)
  • See: https://www.sciencedirect.com/science/article/pii/S157086671100102X?via%3Dihub