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.

$\endgroup$
7
$\begingroup$

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

$\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

$\endgroup$
3
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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