(Worst-Case) Optimal Adaptive Dynamic Bitvectors
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909617665081344 |
|---|---|
| author | Navarro, Gonzalo |
| author_facet | Navarro, Gonzalo |
| contents | While operations {\em rank} and {\em select} on static bitvectors can be supported in constant time, lower bounds show that supporting updates raises the cost per operation to $Θ(\log n/ \log\log n)$ on bitvectors holding $n$ bits. This is a shame in scenarios where updates are possible but uncommon. We develop a representation of bitvectors that we call adaptive dynamic bitvector, which uses the asymptotically optimal $n+o(n)$ bits of space and, if there are $q$ queries per update, supports all the operations in $O(\log(n/q)/\log\log n)$ amortized time. Further, we prove that this time is \new{worst-case} optimal in the cell probe model. We describe a large number of applications of our representation to other compact dynamic data structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15088 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | (Worst-Case) Optimal Adaptive Dynamic Bitvectors Navarro, Gonzalo Data Structures and Algorithms While operations {\em rank} and {\em select} on static bitvectors can be supported in constant time, lower bounds show that supporting updates raises the cost per operation to $Θ(\log n/ \log\log n)$ on bitvectors holding $n$ bits. This is a shame in scenarios where updates are possible but uncommon. We develop a representation of bitvectors that we call adaptive dynamic bitvector, which uses the asymptotically optimal $n+o(n)$ bits of space and, if there are $q$ queries per update, supports all the operations in $O(\log(n/q)/\log\log n)$ amortized time. Further, we prove that this time is \new{worst-case} optimal in the cell probe model. We describe a large number of applications of our representation to other compact dynamic data structures. |
| title | (Worst-Case) Optimal Adaptive Dynamic Bitvectors |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.15088 |