Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
On The Size Of Succinct Indices, Alexander Golynski, Ankur Gupta, Roberto Grossi, Rajeev Raman, Satti Rao
On The Size Of Succinct Indices, Alexander Golynski, Ankur Gupta, Roberto Grossi, Rajeev Raman, Satti Rao
Ankur Gupta
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.