On the Size of Succinct Indices

Alexander Golynski
Ankur Gupta, Butler University
Roberto Grossi
Rajeev Raman
Satti S. Rao

Abstract

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.