Diva++: Dynamic Range Filtering over Hard Workloads
Data Structures and Algorithms
Summary
The authors introduce Diva, a new type of range filter that answers queries about whether any keys exist within a certain range, addressing three common problems found in earlier filters: lack of error or performance guarantees, inability to handle variable key lengths, and no support for updates. Diva learns key patterns by sampling and organizing data in a special trie that compresses keys while keeping enough detail to differentiate them efficiently. They prove Diva balances memory use and false positive rate well and improve it further with Diva++, which compresses data more and stores extra key details. Their tests show Diva and Diva++ perform better or as well as existing methods while handling dynamic and variable-length data.
Authors
Navid Eslami, Ioana O. Bercea, Niv Dayan
Abstract
Range filters are compact probabilistic data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to quickly rule out the existence of keys in a given query range and avoid searching for them in storage. However, all existing range filters exhibit at least one of three shortcomings: (1) they do not provide any false positive rate or performance guarantees, (2) they do not support variable-length keys and query ranges, and (3) they do not allow dynamic updates. We introduce Diva, the first range filter to address all the above challenges simultaneously. Diva learns the dataset's distribution by sampling keys and storing them in a cache-efficient trie. It compresses keys in-between samples by removing their longest common prefix and truncating their suffixes while leaving enough bits in the middle (i.e., an infix) to differentiate the keys in sorted order. It stores infixes in constant-time dynamic data blocks, which it splits to handle insertions and expansions. It processes a range query by traversing the trie and checking for the inclusion of infixes in the target query range. We mathematically prove that Diva provides the best possible trade-off between memory and false positive rate on many common real-world data distributions. We extend these benefits to a wider range of real-world workloads by introducing Diva++, an enhanced Diva variant. Diva++ saves memory by removing redundancies among infixes using order-preserving entropy encoding. It then removes any remaining identical infixes and uses the freed space to store more bits of the original keys within compact binary tries. We compare Diva and Diva++ to all prior range filters, and show that they achieve a false positive rate on par with the state of the art on real-world datasets while supporting dynamicity and variable-length queries and keys.