EmergencyEMERGENCY? Get 24/7 Help Now!

Review of the Tutorial on Algorithms for Memory Sensitive Computing at STOC

 | June 1, 2012 |  Posted In: Tokutek, TokuView


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.


Leave a Reply


Percona’s widely read Percona Database Performance blog highlights our expertise in enterprise-class software, support, consulting and managed services solutions for both MySQL® and MongoDB® across traditional and cloud-based platforms. The decades of experience represented by our consultants is found daily in numerous and relevant blog posts.

Besides specific database help, the blog also provides notices on upcoming events and webinars.
Want to get weekly updates listing the latest blog posts? Subscribe to our blog now! Submit your email address below and we’ll send you an update every Friday at 1pm ET.

No, thank you. Please do not ask me again.