{"ID":2852003,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18237","arxiv_id":"2510.18237","title":"Static Retrieval Revisited: To Optimality and Beyond","abstract":"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 $nv + 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 $nv + 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_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 $nv + \\mathrm{Space}(D_2) + n^{0.67}$ bits.","short_abstract":"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 usin...","url_abs":"https://arxiv.org/abs/2510.18237","url_pdf":"https://arxiv.org/pdf/2510.18237v1","authors":"[\"Yang Hu\",\"William Kuszmaul\",\"Jingxun Liang\",\"Huacheng Yu\",\"Junkai Zhang\",\"Renfei Zhou\"]","published":"2025-10-21T02:48:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}