CS 598 JGE: Advanced Data Structures (Spring 2011)

   About    Schedule    Projects   


   Pointers    Tables    Bits    Time    Big Data    Related Topics   

Key references for each lecture are highlighted. Other references contain related material—historical developments, applications, later improvements and extensions, and the like—which I may only mention briefly (or not at all) in class. Some sources are cited multiple times. *Starred authors were students when the work was written. (Eventually I hope to post a bibtex file that includes everything listed here; stay tuned!) Several relevant topics that I didn't have time to cover are listed after the schedule.


Fun with Pointers

Tue, Jan 18
Thu, Jan 20
[lecture notes]

Lazy binary and lazy Fibonacci counters
after [Bentley Saxe 1980]

Decomposable searching problems: the Bentley-Saxe logarithmic method; local rebuilding; lazy deamortization; O(P(n)log n/n) worst-case insertion time; anti-data structures for invertible queries; weak deletions; (lazy) global rebuilding; O(P(n)log n/n) worst-case insertion time and O(P(n)/n + D(n)) worst-case deletion time.

Tue, Jan 25

No class today — Jeff is at SODA

Thu, Jan 27
[lecture notes]

A well-balanced tree?
[Andersson, J. Alg. 1999]

Scapegoat trees: O(log n) worst-case search and amortized update time using O(1) extra space


A Self-Adjusting Search Tree
by Jorge Stolfi (1987)

Splay trees: rotations, roller-coasters and zig-zags, weighted amortized analysis, O(log n) amortized time, static optimality theorem, static and dynamic finger properties, working set property, dynamic optimality and other splay tree conjectures

Tue, Feb 1
Thu, Feb 3

GREEDYFUTURE in action
[Demaine et al., SODA 2009]

Lower bounds for dynamic binary search trees: arborally satisfied sets, independent rectangle lower bound, Wilber's interleave and alternation lower bounds, SIGNEDGREEDY lower bound, GREEDYFUTURE


Representation of a preferred path in a zipper tree
[Bose et al., SODA 2008]

O(log log n)-competitive binary search trees: tango trees, multisplay trees, chain-splay trees, skip-splay trees, poketrees, zipper trees

Tue, Feb 8
Thu, Feb 10


A multilevel partition of an edge-weighted binary tree, and the resulting topology tree.
[Frederickson 1997]

Dynamic forest maintenance: Link-cut trees; CUT, JOIN, and FINDROOT in O(log n) amortized time; path queries and updates in O(log n) amortized time via lazy propagation; Euler-tour trees; subtree queries and updates in O(log n) amortized time; sketches of topology trees, top trees, rake-compress trees, and self-adjusting top trees.

Tue, Feb 15
Thu, Feb 17

An edge pivots into a planar shortest-path tree as the source node moves along an edge.
After [Chambers Cabello 2007]

Applications of dynamic trees: Maximum flows via network simplex; parametric and multiple-source shortest paths; dynamic graph connectivity

Tue, Feb 22
Thu, Feb 24

Reducing dynamic prefix-sum to dynamic connectivity
[Demaine Pǎtraşcu 2006]

Lower bounds for dynamic connectivity: Cell probe model, prefix sums, reductions, time trees, non-deterministic encoding


Fun with Tables

Tue, Mar 1

Perfect hash browns.
The secret is to get all the moisture out of the potatoes.

Basic hash tables: moments and tail inequalities, chaining, “perfect” hashing, linear probing, cuckoo hashing

Thu, Mar 3

Cuckoo hashing:

Hash functions: (strongly) k-universal hashing, limited independence, tabulation hashing

Tue, Mar 8

The output of a (lower-case) bloom filter.

Bloom filters: basic construction, false positive probability, counting (to support deletions), Bloomier filters

Thu, Mar 10

Periodically covering the plane with balls.
Andoni and Indyk [CACM 2008]

Locality-sensitive hashing


Fun with Bits

Tue, Mar 15
Thu, Mar 17

Bit masks used to solve QBF in polynomial time, on a unit-cost RAM with multiplication.

Unrealistic integer RAMs: Solving anything in #PSPACE in polynomial time and exponential space (sic)


Predecessor search over a finite universe
[Mihai Pătraşcu]

Part of a exponential tree, with the root on the left and children on the right
[Andersson Thorup 2007]

Realistic integer RAMs: transdichotomous RAM, word RAM, AC⁰ RAM
Ordered dictionaries: van Emde Boas trees, x-fast tries, y-fast tries via indirection, fusion trees, exponential search trees

Tue, Mar 22
Thu, Mar 24

Spring break: No class

Tue, Mar 29

Sorting a stack of Indecks notched cards.
From The Last Whole Earth Catalog (1975)

Diagram for Combination Counting
[Hollerith 1890]

A McBee Keysort card.
[Anderson 1949]

Representing 94, without and with a Single Figure notch.
[Anderson 1949]

Fast integer sorting: radix sort, packed sorting, Batcher's bitonic parallel mergesort, signature sort

Thu, Mar 31

A triage tag.
[See also]

Priority queues: atomic heaps, equivalence with sorting, black-box O(1)-time insertion, black-box melding

Tue, Apr 5

A phylogeny of Christian churches reconstructed from memetic analysis (with the Episcopalian meme given a weight of 8)
[Lord and Price 2001]

Least common ancestors: reduction from range minimum queries, reduction to ±1 range minimum queries, induction, the four-Russians trick, heavy-light tree decomposition (again), alphabetic coding, longest common prefix (again), rake-compress trees (again)


Fun with Time

Thu Apr 7

A persistent hash map (via path copying) in Clojure
[Hickey 2008]

Fractional cascading, illustrated by Jorge Stolfi
[Chazelle Guibas 1986]

Partial persistence: fat nodes, path copying, node copying, fractional cascading, planar point location

Tue Apr 12

Overview of project proposals

Thu Apr 14

A Final Thought
[Bender et al. 2002]

AVL dags and version trees
[Fraser and Myers 1987]

Full persistence: Euler tours, ordered list maintenance, virtual scapegoat trees


Replacing the prefix of a pedigree in the compressed path method.
[Fiat Kaplan 2000]

Fingers, prosthetic fingers, tendons, knuckles, and the hand.
[Demaine et al. 2010]

Confluent persistence: Hand, hand, fingers, thumb. Dum ditty, dum ditty, dum dum dum.

Tue Apr 19

Primer timelines [SPOILER!]

Retroactively inserting insertions.
[Demaine et al. 2007]

“You're about to have an idea for a time machine.”
“I am?”


Primer timelines [SPOILER!]
Retroactive data structures: changing the past, rollback, lower bounds via polynomial evaluation, retroactive priority queues via bridges, partial to full retroactivity via √m checkpoints


Fun with Big Data

Thu Apr 21

An obsolete tape robot at Fermi National Lab; each tape cartridge holds about a terabyte.

External-memory data structures: basic definitions and parameters (N, M, and B), fundamental upper and lower bounds (scan, sort, permute, and search), B-trees, sub-constant-time updates via buffering

Tue Apr 26

Answering a 3-sided query: One node in an external-memory priority search tree
[Agarwal et al. 2002]


Answering a 3-sided query: Inside the catalog structure
[Agarwal et al. 2002]

External-memory range searching: external-memory interval trees; external-memory priority search trees; catalog structures for O(B²) points/intervals; external-memory range trees.

Thu Apr 28
Tue May 3


The van Emde Boas layout
[Bender et al. 2000]


A funnel heap
[Brodal Fagerberg 2002]

Cache-oblivious data structures: definitions, tall caches, van Embe Boas layout, exponential layout, funnelsort, funnel heaps, exponential-level priority queues


Fun with Research

Thu May 12
Fri May 13

Chicken chicken chicken.
[Zongker 2002, 2006]


QED.
[Vargomax 2007]

Project presentations! — Siebel 4407



Related Topics

Here is a woefully incomplete list of relevant topics that I did not cover this semester.

Fun with Pointers

Other balanced binary trees: AVL trees, balanced binary B-trees (aka half-balanced trees, aka red-black trees), AA-trees (aka left-leaving red-black trees), brother trees, BB(α)-trees, rank-balanced trees, treaps, randomized binary search trees, skip lists, deterministic skip lists, ...

Linkning two pairing heaps
[Sibeyn]
Efficient heaps: Fibonacci heaps, leftist heaps, skew heaps, randomized meldable heaps, pairing heaps, rank-pairing heaps, queaps, soft heaps, fast minimum spanning trees, ...
More dynamic graphs: dynamic minimum spanning trees, sparsification, ...
Level-ancestors
Kinetic/parametric data structures: kinetic heaps/heaters/hangers/tournaments, convex hulls, Voronoi diagrams, BSP trees, bounding volume hierarchies, parametric shortest paths, ...
Mergeable trees and mergeable dictionaries

Enfilade
[Nelson 1972]
String data structures: KMP automata, PATRICIA trees, suffix trees/arrays/trays/trists, DAWGs, ropes (aka “Model-T enfilades”), ...

Fun with Bits

Word-RAM computational geometry: range searching, point location, Voronoi diagrams, 3SUM, ...
Cell-probe lower bounds: lopsided set disjointness, approximate nearest neighbors, dynamic dictionaries, ...

Fun with Geometry

Practical spatial data structures: quad-/oct-trees, kd-trees, approximate nearest neighbors, dynamic and kinetic kd-trees, well-separated and semi-separated pair decompositions, R-trees, BSP trees, bounding volume hierarchies, ...
Orthogonal range searching: multilevel data structures, range trees, segment trees, interval trees, window lists, fractional cascading, filtering search, pointer-machine lower bounds, ...
Non-orthogonal range searching: ε-nets, cuttings, partition trees, linearization, space-time tradeoffs, semigroup arithmetic lower bounds, ...
Other geometric data structures: point location, Dobkin-Kirkpatrick hierarchies, ray shooting, dynamic convex hulls, parametric search, ...
Approximate nearest-neighbor searching: metric trees, balanced box-decomposition trees, ...

Fun with Big Data

Succinct/implicit data structures
Streaming data structures
Distributed data structures