Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929556986789888 |
|---|---|
| author | Kuszmaul, William Putterman, Aaron Xu, Tingqiang Zhou, Hangrui Zhou, Renfei |
| author_facet | Kuszmaul, William Putterman, Aaron Xu, Tingqiang Zhou, Hangrui Zhou, Renfei |
| contents | Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four settings (static, value-dynamic, incremental, or dynamic), each of which offers different levels of dynamism to the user. In this paper, we establish optimal bounds for the final two settings (incremental and dynamic) in the case of a polynomial universe. Our results complete a line of work that has spanned more than two decades, and also come with a surprise: the incremental setting, which has long been viewed as essentially equivalent to the dynamic one, actually has a phase transition, in which, as the value size $v$ approaches $\log n$, the optimal space redundancy actually begins to shrink, going from roughly $n \log \log n$ (which has long been thought to be optimal) all the way down to $Θ(n)$ (which is the optimal bound even for the seemingly much-easier value-dynamic setting). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10002 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval Kuszmaul, William Putterman, Aaron Xu, Tingqiang Zhou, Hangrui Zhou, Renfei Data Structures and Algorithms Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four settings (static, value-dynamic, incremental, or dynamic), each of which offers different levels of dynamism to the user. In this paper, we establish optimal bounds for the final two settings (incremental and dynamic) in the case of a polynomial universe. Our results complete a line of work that has spanned more than two decades, and also come with a surprise: the incremental setting, which has long been viewed as essentially equivalent to the dynamic one, actually has a phase transition, in which, as the value size $v$ approaches $\log n$, the optimal space redundancy actually begins to shrink, going from roughly $n \log \log n$ (which has long been thought to be optimal) all the way down to $Θ(n)$ (which is the optimal bound even for the seemingly much-easier value-dynamic setting). |
| title | Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.10002 |