Skip to main content
On the Size of Succinct Indices
  • Alexander Golynski
  • Ankur Gupta, Butler University
  • Roberto Grossi
  • Rajeev Raman
  • Satti S. Rao

A succinct data structure occupies an amount of space that is close to the information-theoretic minimum plus an additional term. The latter is not necessarily a lower-order term and, in several cases, completely dominates the space occupancy both in theory and in practice. In this paper, we present several solutions to partially overcome this problem, introducing new techniques of independent interest that allow us to improve over previously known upper and lower bounds.

Publication Date
Citation Information
Alexander Golynski, Ankur Gupta, Roberto Grossi, Rajeev Raman, et al.. On the Size of Succinct Indices. (2007)
Available at: