Skip to main content
Book
On the Size of Succinct Indices
(2007)
  • 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.

Disciplines
Publication Date
2007
Publisher
Springer
Citation Information
Alexander Golynski, Ankur Gupta, Roberto Grossi, Rajeev Raman, et al.. On the Size of Succinct Indices. (2007)
Available at: http://works.bepress.com/ankur_gupta/3/