<p>Also check out the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9944&amp;rep=rep1&amp;type=pdf">thesis of Ankur Gupta</a>, with emphasis on compressible data.</p>

CC BY-SA 2.5
2011-02-21T19:48:37.927Z
2011-02-21T19:48:37.927Z
Rasmus Pagh
<p>If to speak about succit suffix data structures, this one by Navarro and Mäkinen is really good: <a href="http://portal.acm.org/citation.cfm?doid=1216370.1216372" rel="noreferrer">http://portal.acm.org/citation.cfm?doid=1216370.1216372</a></p>

CC BY-SA 2.5
2011-02-19T12:01:33.997Z
2011-02-19T12:01:33.997Z
Tatiana Starikovskaya
<p>There is now a book on the subject: Compact Data Structures: A Practical Approach, by Gonzalo Navarro. <a href="https://dl.acm.org/citation.cfm?id=3092586" rel="nofollow noreferrer">https://dl.acm.org/citation.cfm?id=3092586</a></p>

CC BY-SA 3.0
2018-01-01T03:30:13.453Z
2018-01-01T03:30:13.453Z
jnalanko
<p><a href="http://arxiv.org/abs/1102.0395">Fischer's paper this month</a> reminded me how little I know about the art of succinct data structures, and algorithms to use them. </p>

<p>For those that don't know about succinct data structures: </p>

<blockquote>
  <p>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$?</p>
</blockquote>

<p>The top ones I am interested in if anyone would like to entertain a discussion</p>

<ol>
<li><p>Suffix Arrays. They are a subset of all permutations.</p></li>
<li><p>Ordered Trees. They are a subset of all binary "parenthesis" strings (the matched variety). </p></li>
<li><p>All nearest smaller values, as in the paper (<a href="http://arxiv.org/abs/1102.0395">1</a>). 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.</p></li>
</ol>

<ds.data-structures><lower-bounds>
Succinct data structures survey?
Chad Brewbaker
# Succinct data structures survey?

(Asked by: username_0 on 2011-02-18)

[Fischer's paper this month](http://arxiv.org/abs/1102.0395) 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](http://arxiv.org/abs/1102.0395)). 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.

**Tags:** ds.data-structures, lower-bounds

---

## 3 answers

### Answer by username_1 on 2011-02-21. Score: 7

Also check out the [thesis of Ankur Gupta](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9944&rep=rep1&type=pdf), with emphasis on compressible data.


---

### Answer by username_2 on 2011-02-19. Score: 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>


---

### Answer by username_3 on 2018-01-01. Score: 4

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>


---

