# Succinct data structures survey?

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.