TY - BOOK
T1 - On the Size of Succinct Indices
AU - Golynski, Alexander
AU - Gupta, Ankur
AU - Grossi, Roberto
AU - Raman, Rajeev
AU - Rao, Satti S.
N1 - Part of the Lecture Notes in Computer Science book series (LNCS, volume 4698) 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.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - https://doi.org/10.1007/978-3-540-75520-3_34
U2 - 10.1007/978-3-540-75520-3_34
DO - 10.1007/978-3-540-75520-3_34
M3 - Book
BT - On the Size of Succinct Indices
PB - Springer
ER -