DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2025.23

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

Authors: Lannie Dalton Hough and Abhinav Bhatele

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

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.

Cite as

Lannie Dalton Hough and Abhinav Bhatele. Elias-Fano Compression for Space-Efficient Rank and Select Structures. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

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

Search Results

Documents authored by Bhatele, Abhinav

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

Abstract

Cite as

Thanks for your feedback!

Could not send message