CS 598 JGE: Advanced Data Structures (Fall 2015)

   Announcements    Schedule    Projects   

   Pointers    Tables    Bits    Time    Big Data    Related Topics   

Lecture notes are available for the first few lecture topics, but I do not plan to write notes for the rest of the semester.

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 key sources are cited multiple times. *Starred authors were students when the work was written. These reference lists are out of date, but I will do my best to update them as the semester progresses. Eventually I hope to post a bibtex file that includes everything listed here; stay tuned!

All future lecture topics are subject to change! This schedule mostly mirrors the sequence of topics I covered in Spring 2011. Several relevant topics that I didn't have time to cover are listed after the main schedule; I might cover some of these topics this semester.

I am traveling Oct 15–17, Nov 11, and Dec 2. I hope to schedule makeup lectures outside the normal class meeting time. If scheduling proves prohibitive, I will try to arrange for guest lecturers instead.

Fun with Pointers

Wed Aug 26
Fri Aug 28
[lecture notes]

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.

Lazy binary and lazy Fibonacci counters
after [Bentley Saxe 1980]
  • Lars Arge and Jeffrey Scott Vitter. Optimal external memory interval management. SIAM J. Computing 32(6):1488–1508, 2003. [Among other results, describes weight-balanced B-trees, a prime example of a data structure that directly supports insertions and weak deletions.]
  • Jon L. Bentley. Decomposable searching problems. Information Processing Letters 8:244–251, 1979.
  • Jon L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM 18:509–517, 1975. [Introduces kd-trees, a prime example of a data structure that easily supports weak deletions, but not insertions or real deletions.]
  • Jon L. Bentley and James B. Saxe*. Decomposable searching problems: 1. Static-to-dynamic transformations. J. Algorithms 1(4):301–358, 1980. [Introduces the logarithmic method for adding insertion to any static data structure for a decomposable search problem.]
  • Michael J. Clancy* and Donald E. Knuth. A Programming and Problem-Solving Seminar. Stanford University Computer Science Department Report STAN-CS-77-606, April 1977. [One of the earliest examples of non-standard number systems being used to design efficient dynamic data structures—in this case, finger search trees.]
  • Kurt Mehlhorn. Lower bounds on the efficiency of transforming static data structures into dynamic data structures. Mathematical Systems Theory 15:1–16, 1981.
  • Kurt Mehlhorn. Data Structures and Algorithms III: Multi-dimensional Searching and Computational Geometry. EATCS Monographs, Springer, 1984. [Begins with a thorough overview of dynamization techniques for decomposable search problems. Still one of the best references for this material.]
  • Kurt Mehlhorn and Mark H. Overmars*. Optimal dynamization of decomposable search problems. Information Processing Letters 12:93–98, 1981.
  • Mark H. Overmars*. The Design of Dynamic Data Structures. Lecture Notes in Computer Science 156, Springer, 1983. [Mark's PhD thesis. Describes several families of methods for transforming static data structures into fully dynamic data structures, along with several geometric applications. Still one of the best references for this material.]
  • Mark H. Overmars* and Jan van Leeuwen. Two general methods for dynamizing decomposable searching problems. Computing 26:155–166, 1981. [Describes a lazy version of Bentley-Saxe to modify data structures that support weak deletions and insertions, so that they support real deletions.]
  • Mark H. Overmars* and Jan van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problems. Information Processing Letters 12(4):168–173, 1981. [Introduces the lazy local rebuilding technique for deamortizing Bentley-Saxe.]
  • Himanshu Suri and Victor Vazquez. Combination Pizza Hut and Taco Bell. Shut Up, Dude, 2010. [They're at the Pizza Hut. They're at the Taco Bell. They're at the combination Pizza Hut and Taco Bell. Nearest neighbor searching is a decomposable search problem over an idempotent but non-inversive semigroup.]

Wed Sep 2
Fri Sep 4
[lecture notes]

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

A well-balanced tree?
[Andersson, J. Alg. 1999]
  • Arne Andersson*. Improving partial rebuilding by using simple balance criteria. Proc. Workshop on Algorithms and Data Structures, 393–402. Lecture Notes in Computer Science 382, Springer, 1989. [The first discovery of scapegoat trees.]
  • Arne Andersson. General balanced trees. J. Algorithms 30:1–28, 1999. [The journal version of the previous paper.]
  • Arne Andersson and Tony W. Lai*. Fast updating of well-balanced trees. Proc. 2nd Scandinavian Workshop on Algorithm Theory 111–121. Lecture Notes in Computer Science 447, Springer, 1990. [Scapegoat trees with depth lg n+c require only O(log²n/c) amortized time per insertion or deletion, for any constant c. The amortized update time can be reduced to O(log n/c) using a standard indirection trick: replace the leaves of the scapegoat tree with perfectly balanced subtrees of size Θ(log n).]
  • Igal Galperin* and Ronald L. Rivest. Scapegoat trees. Proc. 4th th Annual ACM-SIAM Symposium on Discrete Algorithms, 165–174, 1993. [The second independent discovery of scapegoat trees and the origin of the name.]

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

A Self-Adjusting Search Tree
by Jorge Stolfi (1987)
  • Ranjan Chaudhuri and Hartmut Höft. Splaying a search tree in preorder takes linear time. International J. Mathematics and Mathematical Sciences 14(3):545–551, 1991. Also appeared in SIGACT News 24(2):88–93, 1993.
  • Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM J. Computing 30:1–43, 2000.
  • Richard Cole. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM J. Computing 30:44–85, 2000.
  • Amr Elmasry. On the sequential access theorem and deque conjecture for splay trees. Theoretical Computer Science 314(3):459–466, 2004. [Best upper bound known for the sequential access theorem: Accessing all n elements of a splay tree in increasing order requires at most 4.5n rotations.]
  • Seth Pettie. Splay trees, Davenport-Schinzel sequences, and the deque conjecture. Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms 1115–1124, 2008. [Proves that n deque operations on an n-node splay tree require at most O(n α*(n)) time, where α*(n) is the iterated inverse Ackermann function. The paper includes a thorough survey of other splay tree results, up to 2008.]
  • Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees. J. ACM 32:652-686, 1985. [HTML demo and C code] [The original splay tree paper.]
  • Rajamani Sundar*. On the deque conjecture for the splay algorithm. Combinatorica 12(1):95–124, 1992. [Proves that n deque operations on an n-node splay tree require at most O(n α(n)) time, where α(n) is the inverse Ackermann function.]
  • Robert E. Tarjan. Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics 44, SIAM, 1983. [Includes a chapter on splay trees. Yes, it took less time to publish an entire 130-page book than one 35-page journal paper.]
  • Robert E. Tarjan. Sequential access in splay trees takes linear time. Combinatorica 5:367–378, 1985. [Established the sequential access theorem: Accessing all n elements of a splay tree in increasing order requires O(n) time.]

Fri Sep 4
Wed Sep 9 [incomplete lecture notes]

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

[Demaine et al., SODA 2009]
  • Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Self-Adjusting Binary Search Trees: What Makes Them Tick? Proc. 23rd European Symposium on Algorithms, 2015, to appear. arXiv:1503.03105.
  • Erik D. Demaine, Dion Harmon*, John Iacono, Daniel Kane*, and Mihai Pătraşcu. The geometry of binary search trees. Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms 496–505, 2009. [Introduces arborally satisfied sets, and proves their equivalence to dynamic binary search trees. See also Derryberry et al. 2005.]
  • Jonathan Derryberry*, Daniel D. Sleator, and Chengwen Chris Wang*. A lower bound framework for binary search trees with rotations. Technical Report CMU-CS-05-187, Carnegie Mellon University, November 22, 2005. [A variant of the geometric view of dynamic binary search trees, developed independently from Demaine et al. 2009]
  • George F. Georgakopoulos. Splay trees: a reweighting lemma and a proof of competitiveness vs. dynamic balanced trees. J. Algorithms 51:64–76, 2004. [Defines a class of so-called parametrically balanced dynamic binary search tree and proves that splay trees are O(1)-competitive within this class.]
  • Dion Harmon*. New Bounds on Optimal Binary Search Trees. Ph.D. dissertation, Department of Mathematics, MIT, June 2006. [Describes the results in Demaine et al. 2009 in more detail, using slightly different terminology.]
  • John Iacono. Key independent optimality. Algorithmica, 42:3–10, 2005.
  • John Iacono. In pursuit of the dynamic optimality conjecture. Space-Efficient Data Structures, Streams, and Algorithms, 236–250, 2013. arXiv:1306.0207. [Surveys lower bound techniques and presents a dynamic BST that is optimal, assuming that an optimal dynamic BST exists at all.]
  • Joan M. Lucas. Canonical forms for competitive binary search tree algorithms. Tech. Rep. DCS-TR-250, Rutgers University, 1988. [Introduces an offline dynamic binary search tree algorithm, called GREEDYFUTURE by Demaine et al.; see also Munro 2000.]
  • J. Ian Munro. On the competitiveness of linear search. Proc. 8th Annual European Symposium on Algorithms 338–345. Lecture Notes in Computer Science 1879, Springer, 2000. [Independently describes the offline dynamic binary search tree algorithm called IAN (“Introduce As Necessary”) in Harmon's thesis and GREEDYFUTURE by Demaine et al.; see also Lucas 1988.]
  • Robert E. Wilber*. Lower bounds for accessing binary search trees with rotations. SIAM J. Computing 18(1):56-67, 1989. [Proves two important lower bounds on the total access cost of dynamic binary search trees.]

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

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

Fri Sep 11
Wed Sep 16

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.

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

Fri Sep 18
Wed Sep 23

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

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

Fri Sep 25

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

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

Wed Sep 30
Fri Oct 1

Efficient priroty queues: Implicit d-ary heaps, Fibonacci heaps, pairing heaps, rank-pairing heaps

An implicit binary tree [Eytzinger 1590]
  • Clark A. Crane*. Linear lists and priority queues as balanced binary trees. Ph.D. thesis, Computer Science Department, Stanford University, 1972. Technical Report STAN-CS-72-259, [Leftist heaps, the first priority queue to support Meld in O(log n) time.]
  • Michaël Eytzinger. Thesavrvs principvm hac ætate in Evropa viventium. Kempensem, Köln, 1590. [The first use of implicit binary trees.]
  • Robert W. Floyd. Algorithm 113: Treesort. Communications of the ACM 5(8):434, 1962. [An early version of heapsort, which used an array as an implicit tournament tree.]
  • Robert W. Floyd. Algorithm 245: Treesort 3. Communications of the ACM 7(12):701, 1964. [The algorithm now universally known as heapsort, including a linear-time in-place algorithm for building an implicit binary heap from an unsorted array.]
  • David B. Johnson. Priority queues with update and finding minimum spanning trees. Information Processing Letters 4(3):53–57, 1975. [Implicit d-ary heaps.]
  • John W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM 7(6):347–348, 1964. [Array-based implicit heaps, and possibly the first use of the word “heap” to mean a data structure implementing a priority queue.]
  • Gerth Stølting Brodal*. Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 52–58, 1996. [The first priority queue whose worst-case time bounds match the amortized time bounds of Fibonacci heaps.]
  • Gerth Stølting Brodal, George Lagogiannis, and Robert E. Tarjan. Strict Fibonacci heaps. Proc. 44th ACM Symposium on Theory of Computing 1177--1184, 2012. [The first pointer-based priority queue whose worst-case time bounds match the amortized time bounds of Fibonacci heaps.]
  • Timothy Chan. Quake heaps: A simple alternative to Fibonacci heaps. Space-Efficient Data Structures, Streams, and Algorithms: 27-32. Lecture Notes in Computer Science 8066, Springer, 2013.
  • James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commununications of the ACM 31(11):1343–1354, 1988. [Frankie say the heap property doesn't always have to be satisfied everywhere.]
  • Stefan Edelkamp. Rank-relaxed weak queues: Faster than pairing and Fibonacci heaps? Technical report 54, TZI, Universität Bremen, 2009. [Answer: Only if you don't need DecreaseKey.]
  • Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen, and Armin Weiß. Weak heaps and friends: Recent developments. Proc. 24th International Workshop on Combinatorial Algorithms 1–6. Lecture Notes in Computer Science 8288, Springer, 2013. [A brief survey of descendants of Dutton's weak heaps.]
  • Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. The weak-heap family of priority queues in theory and praxis. Proc. 18th Computing: The Australasian Theory Symposium, 103–112, 2012.
  • Amr Elmasry. The violation heap: A relaxed Fibonacci-like heap. Proc. 16th Annual International Conference on Computing and Combinatorics 479–488, 2010.
  • Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. Association for Computing Machinery 34(3):596–615, 1987. [The original Fibonacci heap paper.]
  • Bernard Haeupler*, Siddhartha Sen*, and Robert E. Tarjan. Rank-pairing heaps. SIAM J. Computing 40(6):1463–1485, 2011. [Lazy binomial queues with pairing by rank and rank-adjustment. Following the Red Herring Principle, rank-pairing heaps are not actually a variant of pairing heaps; by analogy, Fibonacci heaps should be called “degree-pairing heaps”.]
  • Peter Høyer. A general technique for implementation of efficient priority queues. Proc. 3rd Israel Symposium on Theory of Computer Systems, 57–66, 1995. [Just what it says on the tin. Red-black heaps and mergeable double-ended priority queues.]
  • Haim Kaplan and Robert E. Tarjan. Thin heaps, thick heaps. ACM Transactions on Algorithms 4(1), Article 3, 2008.
  • Daniel H. Larkin*, Siddhartha Sen*, Robert E. Tarjan. A back-to-basics empirical study of priority queues. Proc. 16th Workshop on Algorithm Engineering and Experiments, 61–72, 2014. arXiv:1403.0252. Code available at https://code.google.com/p/priority-queue-testing/. [Implicit d-ary heaps and pairing heaps are the best choices in practice. Binomial and Fibonacci heaps are next best. Everything else sucks.]
  • Daniel D. Sleator* and Robert E. Tarjan. Self-adjusting heaps. SIAM J. Computing 15(1):52–69, 1986. [Skew heaps, otherwise known as self-adjusting leftist heaps.]
  • Tadao Takaoka. Theory of 2-3 heaps. Discrete Applied Mathematics 126(1):115–128, 2003.
  • Tadao Takaoka. Theory of trinomial heaps. Proc. 6th Annual Int. Conf. Computing and Combinatorics, 362-372. Lecture Notes in Computer Science 1858, 2000.
  • Jean Vuillemin. A data structure for manipulating priority queues. Communications of the ACM 21, 309–314, 1978. [Binomial “queues”.]
  • Ronald D. Dutton. Weak-heap sort. BIT 33(3):372–381, 1993. [Weak heaps, a clever implicit variant of binomial queues. Roughly a factor of 2 faster than standard binary heaps, at the cost of one extra bit per item.]
  • Amr Elmasry. Pairing heaps with O(log log n) decrease cost. Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 471–476, 2000. [A variant of pairing heaps that is not covered by Fredman's lower bound.]
  • Amr Elmasry. Pairing heaps, scrambled pairing and square-root trees. International J. Computer Mathematics 87(14):3096–3110, 2010. [A pairing heap with a bad pairing strategy can require Ω(√n) amortized time per operation.]
  • Michael L. Fredman. On the efficiency of pairing heaps and related data structures. J. ACM 46(4):473–501, 1999. [Pairing heaps require Ω(log log n) amortized time for DecreaseKey.]
  • Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator*, and Robert E. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica 1(1):111–129, 1986.
  • John Iacono. Improved upper bounds for pairing heaps. Proc. 7th Scandinavian Workshop on Algorithm Theory, 63--77. Lecture Notes in Computer Science 1851, Springer, 2000. arXiv:1110.4428.
  • Daniel H. Larkin*, Siddhartha Sen*, Robert E. Tarjan. A back-to-basics empirical study of priority queues. Proc. 16th Workshop on Algorithm Engineering and Experiments, 61–72, 2014. arXiv:1403.0252. Code available at https://code.google.com/p/priority-queue-testing/. [Implicit d-ary heaps and pairing heaps are the best choices in practice. Binomial and Fibonacci heaps are next best. Everything else sucks.]
  • Seth Pettie. Towards a final analysis of pairing heaps. Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, 174–183, 2005. [O(22 sqrt{log log n}) amortized time for Insert, Meld, and DecreaseKey. Not universally believed.]

Fun with Tables

Wed Oct 6
[CS 473 notes]

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:

Fri Oct 9

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

Wed Oct 14
Fri Oct 16

No class this week; Jeff is at Oberwolfach.

Fri Oct 9

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

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

Wed Oct 21

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

Locality-sensitive hashing

Fun with Bits

Fri Oct 23
Wed Oct 28

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

Fri Oct 30

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

Wed Nov 4

A triage tag.
[See also]

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

Fri Nov 6

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)

Wed Nov 11

Overview of project proposals

Fun with Time

Fri Nov 13

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

Wed Nov 18

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.

Fri Nov 20

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

Wed Nov 25
Fri Nov 27

Thanksgiving break: No class

Wed Dec 2
Fri Dec 5
No class(?): Jeff is at the Simons Institute

Fun with Big Data

Wed Dec 9

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

makeup lecture, date TBA

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.

makeup lecture, date TBA

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

Finals week
dates TBA

Chicken chicken chicken.
[Zongker 2002, 2006]

[Vargomax 2007]

Project presentations! — Siebel 4407

Related Topics

Here is a woefully incomplete list of relevant topics that I did not have time to cover the liast time I taught this course. Some of these may find their way into this semester's schedule.

Fun with Pointers

Linking two pairing heaps
Efficient heaps: Fibonacci heaps, leftist heaps, skew heaps, randomized meldable heaps, pairing heaps, rank-pairing heaps, queaps, soft heaps, fast minimum spanning trees, ...

[Nelson 1972]
String data structures: KMP automata, PATRICIA trees, suffix trees/arrays/trays/trists, DAWGs, ropes (aka “Model-T enfilades”), ...
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, ...
More dynamic graphs: dynamic minimum spanning trees, sparsification, ...
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

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