Elias-Fano Compression for Space-Efficient Rank and Select Structures

Abstract

Bit vectors are an important component in many data structures. Such data structures are used in a variety of applications and domains including databases, search engines, and computational biology. Many use cases depend on being able to perform rank and/or select queries on the bit vector. No existing rank and select structure enabling these queries is most efficient both for space and for time; there is a tradeoff between the two. In practice, the smallest rank and select data structures, cs-poppy and pasta-flat, impose a space overhead of 3.51%, or 3.125% if only rank needs to be supported. In this paper, we present a new data structure, orzo, which reduces the overhead of the rank component by a further 26.5%. We preserve desirable cache-centric design decisions made in prior work, which allows us to minimize the performance penalty of creating a smaller data structure.

BibTeX

@InProceedings{hough_et_al:LIPIcs.SEA.2025.23,
  author = {Hough, Lannie Dalton and Bhatele, Abhinav},
  title = {{Elias-Fano Compression for Space-Efficient Rank and Select Structures}},
  booktitle = {23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages = {23:1--23:15},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN = {978-3-95977-375-1},
  ISSN = {1868-8969},
  year = {2025},
  volume = {338},
  editor = {Mutzel, Petra and Prezza, Nicola},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.23},
  URN = {urn:nbn:de:0030-drops-232617},
  doi = {10.4230/LIPIcs.SEA.2025.23},
  annote = {Keywords: rank and select, cache-aware, succinct data structures, bit vector}
}