DescriptionDictionaries are fundamental data structures that associate values to a set of keys. They form the foundation of most storage systems, and are key to the performance of many algorithms.
Dictionaries are well studied from an algorithmic perspective, and many constructions of optimal dictionaries are known. However, these are rarely used in practice, and the ubiquitious implementation, the log-structured merge tree, is theoretically suboptimal.
This work studies a collection of dictionary problems, each of which lies somewhere between theory and practice. These problems take advantage of the flow of ideas back and forth betwen them, yielding interesting and surprising results, both where innovations and ideas in systems have influenced theoretical data structures, and also where those data structures form the foundation for new highly performant systems.