6.851: Advanced Data Structures (Spring'21)

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.