Succinct indexable dictionaries with applications to encoding <i>k</i> -ary trees, prefix sums and multisets

TLDR

The indexable dictionary problem requires storing a subset S of {0,…,m−1} while supporting rank and select queries, and prior work only achieved constant‑time membership queries. This work introduces a data structure that supports both rank and select in O(1) time on the RAM model with space B(n,m)+o(n)+O(lg lg m) bits, and extends it to optimal representations of k‑ary trees, multisets, and prefix‑sum sequences. The structure achieves constant‑time operations by combining succinct encoding techniques to reach the information‑theoretic lower bound B(n,m) plus lower‑order terms, and applies these techniques to tree, multiset, and sequence encodings. In the cell‑probe model the authors eliminate the O(lg lg m) additive space term, resolving an open question posed by Fich and Miltersen (1995) and Pagh (2001).

Abstract

We consider the indexable dictionary problem, which consists of storing a set S ⊆ {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 ∈ 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 (lg lg m ) bits to store a set of size n , where B( n, m ) = ⌊lg ( m / 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 [1995] and Pagh [2001]. 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 + O (lg lg m ) —a representation of a sequence of n nonnegative integers summing up to m in B( n, m + n ) + o ( n ) bits that supports prefix sum queries in constant time.