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 \(\varTheta (\log n/ \log \log n)\) . This is a shame in scenarios where updates are possible but uncommon. We develop a representation of bitvectors that, if there are 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 orders of magnitude compared to standard dynamic implementations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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 \(\varTheta (\log n/ \log \log n)\) . This is a shame in scenarios where updates are possible but uncommon. We develop a representation of bitvectors that, if there are 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 orders of magnitude compared to standard dynamic implementations.