Rank and select: Another lesson learned

作者：

Highlights：

• We present new solutions for the primitives on binary vectors, ranks and select.

• Special care for blocks with all 0 or all 1 bits poses a good space-time tradeoff.

• Compressed select is not much slower than compressed rank in a similar space.

摘要

•We present new solutions for the primitives on binary vectors, ranks and select.•Special care for blocks with all 0 or all 1 bits poses a good space-time tradeoff.•Compressed select is not much slower than compressed rank in a similar space.

论文关键词：Binary sequences,Rank,Select,Compressed data structures,68W32

论文评审过程：Received 15 January 2017, Revised 10 July 2017, Accepted 2 December 2017, Available online 5 December 2017, Version of Record 11 December 2017.

论文官网地址：https://doi.org/10.1016/j.is.2017.12.001