STOC Tutorial on Algorithms for Memory-Sensitive Computing
Memory effects -- be they cache misses or page misses -- can have a
dominant impact on the running time of an algorithm. In the case of
page misses, a disk seek can be more than six orders of magnitude
slower than a CPU instruction. Thus, even small savings in the number
of memory transfers can have a large impact on running time.
This disproportionate importance of the memory
hierarchy, combined with the large and growing appetite for large
data, make memory-sensitive algorithms an area with active
technology transfer from algorithmics to the rest of
computer science and to the commercial world. This workshop focuses
on algorithmic approaches that have seen high impact outside of
academic TCS. The tutorials themselves will highlight the importance
of algorithmic advances in making the technology possible.
May 19th, 2011
Location NYU Courant Institute
Registration is free for STOC attendees.
1:30-2:30 The History of I/O Models
Erik Demaine, MIT
2:30-3:30 I/O and Geometry
Pankaj Agarwal, Duke and Scalgo, Inc
Lars Arge, Aarhus and Scalgo, Inc
3:30-4:00 Break
4:00-5:00 I/O and Strings
Paolo Ferragina, Pisa
5:00-6:00 I/O and Databases
Michael Bender, Stony Brook and Tokutek, Inc
Martin Farach-Colton, Rutgers and Tokutek, Inc