Practical Adaptive Dynamic Bitvectors
Gonzalo Navarro
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 bitvectors of
length n, which is close to optimal. 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 can use (1 + e) n
bits of space for any constant e > 0 and, if there are on average
q queries per update, supports all the operations in O(log(n/q))
amortized time. Our experimental results support the theoretical findings,
displaying speedups of up to an order of magnitude compared to standard dynamic
implementations. We offer a public implementation of our data structure.