XLDB Tutorial on Data Structures and Algorithms
The tutorial, which is 4 hours on Monday afternoon, aims to cover the following topics (but it’s looking like we’ll have to drop several items for lack of time.)
This tutorial will explore data structures and algorithms for big databases. The topics include:
- Data structures including B-trees, Log Structured Merge Trees, and Streaming B-trees.
- Approximate Query Membership data structures including Bloom filters and cascade filters.
- Algorithms for join including hash joins and Graefe’s generalized join.
- Index design, including covering indexes.
- Consistency (row locks, multiversion concurrency).
- 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 both in NoSQL implementations such as MongoDB, HBase and in SQL-oriented implementations such as MySQL and TokuDB.
This talk includes explaining and analyzing data structures. So it might not be aimed at someone who hates seeing O(N log N). But we’ll keep the content accessible so that anyone who can tolerate some math will benefit from attending.
Judging by early registration information, our tutorial will be well attended. There are some free spaces left, however. The conference is affordable. Registration costs only $130 for the two day conference, and $75 for a day of tutorials.
Hope to see you there!