Practical Adaptive Dynamic Bitvectors

Gonzalo Navarro

While operations rank and select on static bitvectors can be supported in constant time, lower bounds show that supporting updates raises the cost per operation to Theta(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 worst-case optimal in the cell probe model. We describe a large number of applications of our representation to other compact dynamic data structures.