[DB Seminar] Spring 2017: Huanchen Zhang

Succinct data structures are those that require, asymptotically, only the minimum number of bits required by information theory, while still answering queries efficiently. Despite the importance of space efficiency, particularly for today’s massive-scale data services, succinct data structures remain primarily of theoretical interest outside of a few application areas. Our goal in this paper is to make succinct tries practical for general database and file system use. We propose LOUDS-DS, a new succinct trie encoding method that can support fast point (lookup) and range (scan) queries. We then implement the Fast Succinct Trie (FST) based on LOUDS-DS that is optimized for use in database and file system indexing. FST outperforms previous succinct trie implementations by 4–15× and matches the performance of the state-of-the-art pointer-based indexes while remaining compact.