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


Suffix Arrays. They are a subset of all permutations.
Ordered Trees. They are a subset of all binary "parenthesis" strings (the matched variety). 
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.
Also check out the thesis of Ankur Gupta, with emphasis on compressible data.