Review of the Tutorial on Algorithms for Memory Sensitive Computing at STOC
Martin Farach-Colton and I ran a Tutorial on Algorithms for Memory Sensitive Computing on May 18th at the 44th ACM Symposium on Theory of Computing (STOC) at NYU. Here is the program for the tutorial.
Erik Demaine (MIT) spoke on the History of I/O Models. Throughout the years, a remarkable variety of computational models have been proposed to explain the effects of caching, data locality, prefetching, and single-and multi-level memory hierarchies. Erik traced the intellectual history and connections between these models. Most approaches now sit on shelves. (For example, lower bounds on the cache and I/O efficiency of matrix multiplication or FFT were proved by playing a game of placing red and blue pebbles on a graph.) Other approaches have become universal. Most asymptotic analysis of I/O efficient algorithms assumes the Disk-Access and Cache-Oblivious Models in which blocks have size B, RAM has size M, and performance is measured by counting memory transfers. This style of analysis will be familiar to those who’ve seen our talks on how Fractal Tree® Indexes work.
Pankaj Agarwal (Duke, Scalgo) and Lars Arge (Aarhus University, MADALGO, Scalgo) gave a joint talk on I/O and Geometry. They spoke about algorithms (buffer trees, distribution sweeping) for manipulating massive geometric (and nongeometric) data sets. They showed how these approaches are used at Scalgo for processing massive terrain data, e.g., to predict floods after heavy rains or innundations caused by rising sea levels.
Paolo Ferragina spoke on I/O and Strings. His presentation was simultaneously a historical reminiscence and a deep technical talk. Paolo explained the interconnections between string searching, suffix trees, string B-trees, and various static and dynamic compressed indexes. He discussed provably good approaches for trading off compression and performance.
Martin and I gave a joint talk on I/O and Databases. We gave an overview of indexing and touched upon good index selection. We then pointed out the difficulty of indexing under heavy data loads and how write-optimization can help. (No surprise here.) We then did a deep dive into the foundations of write optimization and how it’s used in production. We discussed our experience transforming our original theoretically good write-optimized data structure into a full-featured Fractal Tree Index.