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

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

2007-05-04

arxiv.org/abs/0705.0552v1

ACM Transactions on Algorithms vol 3 (2007), Article 43, 25pp

Computer Science

Data Structures and Algorithms

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

Scientific paper

10.1145/1290672.1290680

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 ${\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 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 ${\cal 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 ${\cal B}(n,m+n) + o(n)$ bits that supports prefix sum queries in constant time.

Affiliated with

Also associated with

No associations

Rating

Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615011