Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors
Open Access
- 1 November 2022
- book chapter
- Published by Springer Nature
- p. 257-272
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 $$ 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.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- 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
- Wavelet trees: A surveyComputer Science and Information Systems, 2012
- The myriad virtues of Wavelet TreesInformation and Computation, 2009
- Broadword Implementation of Rank/Select Queries2008
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisetsACM Transactions on Algorithms, 2007
- Efficient Implementation of Rank and Select Functions for Succinct RepresentationLecture Notes in Computer Science, 2005
- Efficient Storage and Retrieval by Content and Address of Static FilesJournal of the ACM, 1974