Write Optimization for Databases

Abstract

Much of the way we use databases is a consequence of the performance characteristics of algorithms for indexing data. For example, much of the drive towards NoSQL solutions are due to such performance limitations. So-called write optimized indexes are making a splash, both in academia and in industry, and hold the promise of making databases much more useful. In this talk, I'll analyze database bottlenecks from an algorithmic point of view, explain how write- optimized indexes work, and explore the challenges that lie ahead.

Martin Farach-Colton is a Professor in the Computer Science Department at Rutgers University and Founder and CTO of Tokutek, a database company based in New York and Lexington, MA. He was a Senior Research Scientist at Google from 2000 to 2002. He received his PhD in Computer Science from the University of Maryland and his MD from the Johns Hopkins School of Medicine. His primary research interest is in memory-sensitive algorithms for high-performance databases and file systems, particularly Cache-Oblivious Algorithms.