Data Structures and Algorithms for Big Databases

This session will provide a high-level overview of data structures and algorithms for modern big data data applications. Topics include:

-Data structures including B-trees, Log Structured Merge Trees, Streaming B-trees, and Fractal Trees,

-Bloom filters and bloom filter alternatives designed for SSDs

-Index design, including covering indexes

-Getting good performance in memory

-Cache efficiency including both cache-aware and cache-oblivious data structures and algorithms

These algorithms and data structures are used in many NoSQL implementations such as Cassandra, MongoDB, and Percona TokuMX. This session will explain the underlying data structures and algorithms that drive big databases. There will also be an emphasis on write-optimized data structures, such as Log Structured Merge Trees and Fractal Trees.

Dr. Kuszmaul’s research focuses on developing computer systems and hardware that behave well both in practice and in theory. His entry won 5 out of 6 categories in Jim Gray’s 2007 sorting benchmark contest, sorting a terabyte in 197 seconds. He formerly architected Akamai’s distributed data collection system, was a Yale Professor of Computer Science and was a principal network architect for the Thinking Machines CM-5 Supercomputer. Dr. Kuszmaul is also a Research Scientist in the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL).

Michael A. Bender is an associate professor of computer science at Stony Brook University. He is also the Chief Scientist at Tokutek, Inc, an enterprise database company, which he co-founded in 2006. Bender's research interests span the areas of data structures and algorithms, I/O-efficient computing, scheduling, and parallel computing. He has coauthored over 100 articles on these and other topics. He has won several awards, including an R&D 100 Award and four awards for graduate and undergraduate teaching. Bender received his A.B. in Applied Mathematics from Harvard University in 1992 and obtained a D.E.A. in Computer Science from the Ecole Normale Superieure de Lyon, France in 1993. He completed a Ph.D. on Scheduling Algorithms from Harvard University in 1998. He has held Visiting Scientist positions at both MIT and King's College London.