Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors

Abstract

Abstract Bit vectors are fundamental building blocks of succinct data structures used in compressed text indices, e.g., in the form of the wavelet trees. Here, two types of queries are of interest: rank and select queries. In practice, the smallest (uncompressed) rank and select data structure cs-poppy has a space overhead of $$\approx $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>≈</mml:mo> </mml:math> 3.51 % [Zhou et al. SEA 2013] [26]. Using the same overhead, we present a data structure that can answer queries up to 8 % (rank) and 16.5 % (select) faster compared with cs-poppy.

Topics & Concepts