6.851: Advanced Data Structures (Fall'17)

In our first class, I'll give a whirlwind tour of the entire class in about an hour, talk about the format of the class, and then we'll solve some problems! In general, the format of the class will focus on problem solving , including solved problems (like you would on a pset) but collaboratively in class, unsolved problems that no one knows the answer to, and coding problems where we can implement data structures (often never before implemented).

To facilitate problem solving, we'll be using (open-source) software I wrote called Coauthor . To that end:

1. Please join the 6851-students mailing list
2. Please sign up for an account now here: https://coauthor.csail.mit.edu/6.851-2017/
3. Please fill out this signup form in particular so that we can give you permission to use Coauthor.
4. Please bring a laptop (or tablet) to class.

In this lecture, the first of two about geometric data structures, we'll talk about two major problems—point location and range searching—and tie them to several major data structural techniques: persistence, retroactivity, dynamization of augmentation through weight balance, and fractional cascading.

In (planar) point location, we need to preprocess a planar map to support queries of the form "which face contains this point?" This problem is useful for figuring out where you clicked in a GUI, or for figuring out what city/country/etc. contain your GPS coordinates. The static (preprocessing) version of this problem can be solved optimally (in logarithmic time per query) by applying persistence to a classic sweep-line technique. The dynamic version, where the map can be modified, can be solved for orthogonal maps in optimal logarithmic time per operation using retroactive successor from Lecture 2.

In (orthogonal) range searching, we need to preprocess n points in d dimensions to support queries of the form "which points are in this box?" Simple range trees solve this problem in O (log ^d n ) query time and O ( n log ^{d −1} n ) space. A cool crosslinking technique (called layered range trees) reduce the query time to O (log ^{d −1} n ). A general technique for dynamizing augmented search trees, called weight-balanced trees, allows us to additionally support insertion and deletion of points in O (log ^d n ) time per update. The crosslinking technique is a part of a more general technique called fractional cascading, which can further improve query time by another logarithmic factor.

First, we'll finish our coverage of fractional cascading from Lecture 3 by illustrating a really cool application: 3D orthogonal range searching in O (log  n ) time. This gives us the second log factor improvement mentioned in Lecture 3, giving O (log ^{d −2} n ) for d dimensions.

Second, we'll cover a style of data structures for moving data, e.g., where 2D points move at known velocity and acceleration. Although the main study here is in 2D (and 3D), we'll focus on two 1D problems that are well-understood and fit in a lecture: kinetic predecessor and kinetic priority queues.

points in 2D? Today's lecture will reveal a surprising new (2009) such connection, which provides an approach to tackling the venerable dynamic optimality conjecture.

The dynamic optimality conjecture is one of the oldest and biggest open problems in data structures, asking a fundamental question: is there one best binary search tree? Traditional wisdom is that “splay trees” are such a tree (up to constant factors), but we'll see a new “greedy” tree data structure that we think is more obviously best—though we still can't prove it.

Dynamic optimality remains an active and exciting area of research, and this lecture and the next focus on the current state-of-the-art.

First we'll finally cover the black box we used last lecture to obtain cache-oblivious B-trees: maintain an ordered file with O (1)-size gaps in O (lg ² N ) moves per insert/delete in the middle of the file. As an extra bonus, we'll see how to maintain a linked list subject to order queries in O (1) time per insert/delete, which is a black box we used back in Lecture 1 to linearize the version tree when implementing full persistence.

Second we'll cover cache-oblivious priority queues, supporting insert and delete-min in what's usually subconstant time per operation (!), O ((1/ B ) log _{M / B} ( N / B )). This will be the first time we see how to adapt to the cache size  M , not just the block size  B , in a cache-oblivious data structure.

This lecture marks our full entry into integer data structures (though hashing was also one), as well as our first of three lectures on the predecessor problem: supporting insert, delete, and predecessor/successor on a set of n w -bit integers. I'll give an overview of what's known about this problem, as well as the appropriate models of computation, and then proceed to the first main result: data structures achieving O (lg  w ) time per operation. When w is polylogarithmic in n (a common case), this bound is O (lg lg  n ), an exponential improvement over binary search trees. The first such data structure is called (and by) van Emde Boas, and it uses Θ(2 ^w ) space. A little addition of hashing reduces the space to optimal Θ( n ). We'll also see simpler ways to achieve the same bounds, using a simple tree view, indirection, and structures called x-fast and y-fast trees by Willard (who was actually the first to get Θ( n ) space).

This lecture describes a tour-de-force in integer data structures, called fusion trees (so named because they were published a year after the 1989 cold-fusion "scandal", and were perhaps just as surprising--though more correct). Fusion trees solve predecessor and successor among n w -bit integers in O (log _w n ) time per operation on the word RAM. The basic idea is to build a B-tree with branching factor w ^ε . The tricky part is to build a w ^ε -size node supporting constant-time predecessor/successor.

We'll see three major techniques for doing so. First, sketching reduces the w ^1+ε bits in a node down to w “essential” bits, by reducing each word down to w ^1−ε “essential” bits. The impressive part is sketching a word in constant time using a single multiplication. Second, parallel comparison lets us compare all of these sketches with a single query in constant time. Third, we'll see how to find the most significant set bit of a w -bit word in constant time on a word RAM, by using most of the fusion techniques again; this problem has tons of applications beyond fusion trees as well. (As a result, most significant set bit is a built-in instruction on most architectures; see e.g. StackOverflow .)

This lecture is our first (of two) about 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. The exact trade-off (up to constant factors) is known, but messier; we'll see the bound but not prove it. In particular, it is known that the log log factor improvements are actually impossible to achieve with roughly linear space, making the min of van Emde Boas and fusion trees actually optimal.

These lower bounds hold in the powerful cell-probe model of computation, where we just count the number of words read by the query algorithm. The proof uses a beautiful technique called round elimination, in a communication-complexity view of data structures, and is actually quite clean and simple given an appropriate lemma.

The best results we know for sorting in linear time (and thus for constant-time priority queues) is when w = O (lg  n ) and when w = Ω(lg ^2+ε n ). The first result is just radix sort. The second result is the main topic of the lecture: a fancy word-RAM algorithm called signature sorting. It uses a combination of hashing, merge sort, and parallel sorting networks.

The range of w in between lg and lg ^2+ε remains unsolved. The best algorithm so far runs in O ( n √ lg lg  n ) expected time.

It's amazing what you can do in constant time using only linear space. This lecture is about such data structures for jumping around (static) rooted trees. Given two nodes, we'll see how to find their least common ancestor in constant time. Given a node and a number k , we'll see how to find the k th ancestor of the node in constant time. Both data structures use a nice collection of ideas, including a powerful trick we haven't used before: lookup tables for small inputs.

Along the way, we'll solve another seemingly unrelated problem: preprocess an array of numbers to support queries of the form: what's the smallest number in a given interval of the array? Again, we'll show that constant-time queries are possible using only linear space.

This lecture continues our theme of dynamic graphs. Beyond surveying results for several such problems, we'll focus on dynamic connectivity, where you can insert and/or delete edges, and the query is to determine whether two vertices are in the same connected component (i.e., have a path between them). We'll cover a few different results for this problem:

1. Link-cut trees (from last lecture) already solve trees in O (lg n ).
2. Euler-tour trees are a simpler way to solve trees in O (lg  n ), which allow us to aggregate over subtrees instead of paths.
3. If we just insert or just delete edges, we can solve trees in O (1), using our friend leaf trimming plus some simple bit-vector tricks.
4. For general graphs, we'll see how to support updates in O (lg ²   n ) and queries in O (lg  n  / lg lg  n ).

This will be our culmination of data structures for dynamic graphs; the next (final) lecture is about matching lower bounds.

This lecture covers our second of two lower bounds. This one is work byMihai Pătraşcu (former 6.851 TA) and myself. We'll show that maintaining a graph subject to edge insertion, edge deletion, and connectivity queries (are v & w connected by a path?) requires Ω(lg  n ) time per operation, even if the graph is just a bunch of paths. This in particular proves optimality of the logarithmic dynamic tree data structures, and shows that the O (lg ² n ) data structure we saw for general graphs is pretty good. The lower bound introduces a new but very simple technique, which at the time was the first “truly logarithmic” lower bound for a natural problem, yet the whole proof is relatively clean.

Ever wonder where the external-memory and cache-oblivious models of Lectures 7–9 come from? It turns out that they both have a natural history. The external-memory model combines two older models: Floyd's idealized 2-level model of 1972, which models blocks but not cache; and Hong and Kung's red-blue pebble game of 1981, which models cache but not blocks. The cache-oblivious model follows a series of attempts to model multilevel memory hierarchies, most notably the HMM model of 1987, where it is possible to prove that a single algorithm runs optimally on all possible memory hierarchies.

This lecture is not an official part of the class, but rather was part of a STOC 2012 tutorial on Algorithms for Memory-Sensitive Computing , organized by Michael Bender and Martin Farach-Colton. Given the relevance of the material, we are including it here. Note that the format differs from the usual blackboard lecture: it uses slides.