Static Retrieval Revisited: To Optimality and Beyond

In the static retrieval problem, a data structure must answer retrieval queries mapping a set of n keys in a universe $[U]$ to v-bit values. Information-theoretically, retrieval data structures can use as little as nv bits of space. For small value sizes v, it is possible to achieve $O(1)$ query time while using space $n v+o(n)$ bits-whether or not such a result is possible for larger values of v (e. g. , $v=\Theta(\log n)$) has remained open. In this paper, we obtain a tight lower bound (as well as matching upper bounds) for the static retrieval problem. In the case where values are large, we show that there is actually a significant tension between time and space. It is not possible, for example, to get $O(1)$ query time using $n v+o(n)$ bits of space, when $v=\Theta(\log n)$ (and assuming the word RAM model with $O(\log n)$-bit words)At first glance, our lower bound would seem to render retrieval unusable in many settings that aim to achieve very low redundancy. However, our second result offers a way around this: We show that, whenever a retrieval data structure $D_{1}$ is stored along with another data structure $D_{2}$ (whose size is similar to or larger than the size of $D_{1}$), it is possible to implement the combined data structure $D_{1} \cup D_{2}$ so that queries to $D_{1}$ take $O(1)$ time, operations on $D_{2}$ take the same asymptotic time as if $D_{2}$ were stored on its own, and the total space is $n v+\operatorname{Space}\left(D_{2}\right)+n^{0. 67}$ bits.

Authors

• Yang Hu
• William Kuszmaul
• Jingxun Liang
• Huacheng Yu
• Junkai Zhang
• Renfei Zhou

Keywords

• Computer science
• Lower bound
• Upper bound
• Redundancy
• Random access memory
• Data structures
• Indexes
• Time And Space
• Data Structure
• Universe
• Static Problem
• Query Time
• Low Redundancy
• Fraction Of Cells
• Time Constant
• False Positive Rate
• Functional Independence
• Results Of This Paper
• Data Augmentation
• Communication Protocol
• Hash Function
• Random Permutations
• Information Bits
• Word Size
• Sparse Vector
• Parameter Regime
• Worst-case Time
• Fast Query
• Source Of Randomness
• Trade-off Curve
• Additional Bits
• Permutation Group
• Index Terms-static retrieval
• lower bounds
• upper bounds