论文标题
在可变位图上排名/选择查询
Rank/Select Queries over Mutable Bitmaps
论文作者
论文摘要
对于许多简洁的数据结构而言，在位图上回答等级/选择查询的问题至关重要。当位图不变时，理论和实用方面存在许多解决方案。在这项工作中，我们考虑允许通过翻转（i）操作来修改其第i-thit位的flip（i）操作来修改位图的情况。通过适应并正确扩展有关前缀和附件数据结构的一些结果，我们为该问题提供了一个实用的解决方案，该解决方案是针对现代CPU指导集量身定制的。与最先进的解决方案相比，我们的解决方案可以提高运行时，而没有空间降解。此外，与最快不变的索引相比，它并没有在重大的运行时罚款，同时为较低的空间提供了较低的空间。
The problem of answering rank/select queries over a bitmap is of utmost importance for many succinct data structures. When the bitmap does not change, many solutions exist in the theoretical and practical side. In this work we consider the case where one is allowed to modify the bitmap via a flip(i) operation that toggles its i-th bit. By adapting and properly extending some results concerning prefix-sum data structures, we present a practical solution to the problem, tailored for modern CPU instruction sets. Compared to the state-of-the-art, our solution improves runtime with no space degradation. Moreover, it does not incur in a significant runtime penalty when compared to the fastest immutable indexes, while providing even lower space overhead.
