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

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

DOI arXiv slides pdf code

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 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

BibTeX 

@inproceedings{Kurpicz2022SPIRE,
  author    = {Florian Kurpicz},
  title     = {Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors},
  booktitle = {SPIRE},
  series    = {Lecture Notes in Computer Science},
  volume    = {13617},
  pages     = {257–272},
  publisher = {Springer},
  doi       = {10.1007/978-3-031-20643-6_19},
  year      = {2022}
}

PDF