Succinct Indexable Dictionaries

consists in storing a set $S \subseteq \{0,\ldots,m-1\}$ for some integer
$m$, while supporting the operations of rank(x), which returns the number
of elements in $S$ that are less than $x$ if $x \in S$, and $-1$
otherwise; and select(i) which returns the $i$-th smallest element in $S$.

We give a structure that supports both operations in $O(1)$ time on
the RAM model and requires ${\cal B}(n,m) + o(n) + O(\lg \lg m)$ bits
to store a set of size $n$, where ${\cal B}(n,m) = \ceil{\lg {m
\choose n}}$ is the minimum number of bits required to store any
$n$-element subset from a universe of size $m$. Previous dictionaries
taking this space only supported (yes/no) membership queries in $O(1)$
time. In the cell probe model we can remove the $O(\lg \lg m)$
additive term in the space bound, answering a question raised by Fich
and Miltersen, and Pagh.

We also present applications of indexable dictionaries in representing
k-ary trees and multisets succinctly.