Skip to main content Link Search Menu Expand Document (external link)

Slides for our paper "Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors" presented at SPIRE 2022

DOI arXiv slides pdf code


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 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 ≈ 3.51 % [Zhou et al., SEA ‘13]. 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


Preview of the slides.