View publication
| Title | Practical Adaptive Dynamic Bitvectors |
| Authors | Gonzalo Navarro |
| Publication date | 2025 |
| Abstract |
Introduction: While operations rank and select on static bitvectors can be supported in constant time, lower bounds show that this is impossible when supporting updates; practical implementations offer O(log n) time for the operations, which is close to optimal. This is a shame in scenarios where updates are possible but uncommon. \n\n Methods: We develop a representation of bitvectors that we call adaptive dynamic bitvector, which can use (1+e)n bits of space for any constant e and, if there are queries per update, supports all the operations in O(log(n/q)) amortized time. \n\n Results: Our experimental results support the theoretical findings, displaying speedups of orders of magnitude compared to standard dynamic implementations. We offer a public implementation of our data structure. |
| Downloaded | 12 times |
| Pages | 1539-1559 |
| Volume | 55 |
| Journal name | Software: Practice and Experience |
| Publisher | John Wiley & Sons (Hoboken, NJ, USA) |
|
|
| Reference URL |
|