Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets

Rajeev Raman; Venkatesh Raman; Srinivasa Rao Satti

doi:10.1145/1290672.1290680

paper

Succinct Indexable Dictionaries with Applications to Encoding $k$ -ary Trees, Prefix Sums and Multisets

arXiv:0705.0552 · doi:10.1145/1290672.1290680

Abstract

We consider the {\it indexable dictionary} problem, which consists of storing a set $S \subseteq {0, ..., 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 data structure that supports both operations in O(1) time on the RAM model and requires $B (n, m) + o (n) + O (l g l g 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 (l g l g m)$ additive term in the space bound, answering a question raised by Fich and Miltersen, and Pagh. We present extensions and applications of our indexable dictionary data structure, including: An information-theoretically optimal representation of a $k$ -ary cardinal tree that supports standard operations in constant time, A representation of a multiset of size $n$ from ${0, ..., m - 1}$ in $B (n, m + n) + o (n)$ bits that supports (appropriate generalizations of) $\Rank$ and $\Select$ operations in constant time, and A representation of a sequence of $n$ non-negative integers summing up to $m$ in $B (n, m + n) + o (n)$ bits that supports prefix sum queries in constant time.

Final version of SODA 2002 paper; supersedes Leicester Tech report 2002/16

Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets

Abstract

Cited by in corpus (33)

Succinct Indexable Dictionaries with Applications to Encoding $k$ -ary Trees, Prefix Sums and Multisets