Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors
Author:
Preprint
Abstract
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 $\approx$ 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.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Rank/select queries over mutable bitmapsInformation Systems, 2021
- A Hybrid Compressed Data Structure Supporting Rank and Select on Bit Sequences2020
- Wavelet trees for allJournal of Discrete Algorithms, 2014
- From Theory to Practice: Plug and Play with Succinct Data Structures2014
- Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit SequencesLecture Notes in Computer Science, 2013
- Fast, Small, Simple Rank/Select on Bitmaps2012
- The myriad virtues of Wavelet TreesInformation and Computation, 2009
- Succincter2008
- Broadword Implementation of Rank/Select Queries2008
- Efficient Implementation of Rank and Select Functions for Succinct RepresentationLecture Notes in Computer Science, 2005