Understanding Dictionaries at the Intersection of Theory and Practice
Thursday, May 28, 2020, 02:00pm - 03:30pm
Location : Remote via Webex
Prof. Martin Farach-Colton (Advisor), Prof. Aaron Bernstein, Prof. Sudarsun Kannen, Dr. Guy Blelloch (External member)
Event Type: PhD Defense
Abstract: Dictionaries are fundamental data structures that map a set of keys to values. A dictionary generally must support insertion and lookup, but also optionally delete, update, successor and scan. A system that implements a dictionary is called a key-value store. The work presented in this talk applies the theory of external memory dictionaries to achieve improved performance in systems and also derives theoretically interesting problems and solutions from commonly used systems data structures. This talk will cover file systems aging, optimal external memory hash tables, and high-performance key-value stores targeting NVMe.