Advanced Data Structures

History of memory models: idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious

Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity

Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey

Dynamic graphs: link-cut trees, heavy-light decomposition

Succinct: compact suffix arrays and trees

Succinct: rank, select, tries

Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval

Integer: sorting in linear time for w = O(lg2+ε n), priority queues

Static trees: least common ancestor, range minimum queries, level ancestor

Fusion trees: sketching, parallel comparison, most significant set bit

Integer: models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection

Integer data structure lower bounds. In particular, we'll prove that the min of van Emde Boas and fusion trees is an optimal (static) predecessor data structure up to a log log factor, assuming polynomial space.

Dictionaries: universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing

Memory hierarchy: distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online

Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues

Cache-efficient structures. B-trees are good at data transferred in blocks between cache and main memory, main memory and disk, and so on, achieving O(logB N) insert/delete/predecessor/successor for N items and memory block transfers of size B.

Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees

Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm

Fractional cascading in 3D orthogonal range searching in O(log n) time. Moving data, e.g., where 2D points move at known velocity and acceleration: kinetic predecessor and kinetic priority queues.

Point location and range searching: persistence, retroactivity, dynamization of augmentation through weight balance, and fractional cascading.

Partial and full retroactivity let us to alter and manipulate the order of operations, and investigate the results. A third type, "non-oblivious", puts queries on the timeline as well, and reports the first query whose answer changed.

"Persistence” - remembering all past versions of a data structure (“partial persistence”), being able to modify them - forking off new ones (“full persistence”), and merging different versions into one (“confluent persistence”).