Consensus method improves compressed static function space tradeoffs
Consensus for Compressed Static Functions
Data Structures and Algorithms
Summary
Storing data efficiently is important for many computer tasks. The paper explores a way to organize and compress functions that map items to values without storing the items themselves. The authors adapted a technique called Consensus, originally meant for a related problem, to create compressed static functions that use less space close to the theoretical minimum. Their approach uses careful random distribution and task insertion to overcome construction difficulties. Though their implementation is not yet competitive in practice, it introduces new ways to think about this kind of data structure.
What this means in practice
- •For database engineers: Build more space-efficient key-value stores that compress values close to their entropy limits while allowing constant-time queries.
- •For bioinformatics developers: Create compressed index structures for genomic data that store annotations compactly, reducing memory use in large-scale analyses.
Authors
Dominik Rosch, Jonatan Ziegler
Abstract
The Consensus technique marked a breakthrough in the construction of minimal perfect hash functions (MPHFs), reaching a linear tradeoff between construction time and space overhead relative to the optimum. Consensus provides a clever scheme to search for and encode seeds of tasks in random data structures. We apply Consensus to the related field of compressed static functions (CSFs). These data structures store a function $f: S \to Σ$ such that querying a key $x \in S$ returns $f(x)$ and querying $x \not \in S$ returns an arbitrary value. CSFs do not need to store the keys $S$ and only need space close to the zeroth-order empirical entropy of the multiset of values. Often, some values are much more common than others. In these cases, CSFs can use less space than their non-compressed counterparts. CSFs are a useful building block, for example in database design and bioinformatics. We introduce Consensus-CSF, which can reach arbitrarily close to the empirical entropy $n H_0$, with a construction time of $n \exp(\tilde{\cal{O}} (\sqrt{1 / δ}))$ for space usage of $n H_0 (1 + δ)$ when assuming some parameters of the value distribution to be constants. This tradeoff beats previously implemented approaches that can only reach some fixed threshold above the entropy lower bound. We enable Consensus in the setting of CSFs, which is less structured than MPHFs, with the introduction of task insertions. Our approach randomly distributes the keys into one-bit Consensus tasks and then strategically inserts additional tasks in places where the construction would get stuck otherwise. We provide an implemented version of our algorithm which reaches the same order of magnitude in space overhead as competitors but is not competitive in practice. Beyond these results, we present a new way to think and reason about Consensus, which may also be applied to other problems.