Papers › Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors
Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors
Florian Kurpicz
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Bit vectors are fundamental building blocks of many succinct data structures. They can be used to represent graphs, are an important part of many text indices in the form of the wavelet tree, and can be used to encode ordered sequences of integers as Elias-Fano codes. To do so, two queries have to be answered: namely rank and select queries. Given a position in the bit vector, a rank query returns the number of 1-bits before that position. A select query, given a parameter j, returns the position of the j-th 1-bit. On a length-n bit vector, both queries can be answered in O(1) time and require o(n) bits of additional space. In practice, the smallest (uncompressed) rank and select data structure cs-poppy has a space overhead of ≈ 3.51% [Zhou et al., SEA 13]. In this paper, we present an improved rank and select data structure that has the same space overhead but can answer queries up to 8% (rank) and 16.5% (select) faster compared with cs-poppy.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections