17
$\begingroup$

Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them.

For those that don't know about succinct data structures:

Given a combinatorial structure, with a(n) distinct configurations, and a known "useful" representation $R(n)$. Is there a "succinct" data structure that takes storage of around $\lg(a(n))$ bits yet lets us perform operations as fast as we can with the normal representation $R$?

The top ones I am interested in if anyone would like to entertain a discussion

  1. Suffix Arrays. They are a subset of all permutations.

  2. Ordered Trees. They are a subset of all binary "parenthesis" strings (the matched variety).

  3. All nearest smaller values, as in the paper (1). Not only can you compress in both dimensions; the allowable "smaller value" arrays in one direction are a small subset of lists $\{0,...,n-1\}^n$ , and thus you need to store less than $n \lg(n)$ bits.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

Also check out the thesis of Ankur Gupta, with emphasis on compressible data.

Improve this answer
$\endgroup$
6
$\begingroup$

If to speak about succit suffix data structures, this one by Navarro and Mäkinen is really good: http://portal.acm.org/citation.cfm?doid=1216370.1216372

Improve this answer
$\endgroup$
4
$\begingroup$

There is now a book on the subject: Compact Data Structures: A Practical Approach, by Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.