Rank/select queries over mutable bitmaps
作者：
Highlights：
• An efficient solution to the rank/select over mutable bitmaps problem.
• Efficient searchable prefix-sum data structure with SIMD instructions.
• Support for both AVX2 and AVX-512 instruction sets.
• New algorithms for rank/select queries over small bitmaps without auxiliary space.
• C++ code available at https://github.com/jermp/mutable_rank_select.
摘要
•An efficient solution to the rank/select over mutable bitmaps problem.•Efficient searchable prefix-sum data structure with SIMD instructions.•Support for both AVX2 and AVX-512 instruction sets.•New algorithms for rank/select queries over small bitmaps without auxiliary space.•C++ code available at https://github.com/jermp/mutable_rank_select.
论文关键词：Rank/select,Mutable bitmap,SIMD,Performance evaluation
论文评审过程：Received 7 October 2020, Revised 30 January 2021, Accepted 23 February 2021, Available online 3 March 2021, Version of Record 13 March 2021.
论文官网地址：https://doi.org/10.1016/j.is.2021.101756
