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=Θ(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=Θ(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₁ is stored along with another data structure D₂ (whose size is similar to or larger than the size of D1), it is possible to implement the combined data structure D1 D₂ so that queries to D1 take O(1) time, operations on D₂ take the same asymptotic time as if D₂ were stored on its own, and the total space is n v+Space(D₂)+n0.67 bits.