17

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Chad Brewbaker
  • 2,359
  • 15
  • 18

3 Answers3

7

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

Rasmus Pagh
  • 962
  • 6
  • 11
6

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

Tatiana Starikovskaya
  • 821
  • 6
  • 9
3

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

jnalanko
  • 131
  • 2