Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

TLDR

Prior space‑efficient dictionaries only supported O(1)-time membership queries, and earlier k‑ary tree representations required C(n,k)+Ω(n) bits. The authors aim to provide an indexable dictionary that supports rank and select in O(1) time using B(n,m)+o(n)+O(log log m) bits, and to apply it to optimal representations of k‑ary trees and multisets. They construct a structure that stores a set S in B(n,m)+o(n)+O(log log m) bits and supports rank and select in constant time, extending it to k‑ary trees with C(n,k)+o(n+log k) bits and to multisets with B(n,m+n)+o(n)+O(log log m) bits. The resulting dictionary achieves near‑optimal space, removes the O(log log m) additive term in the cell‑probe model, and yields information‑theoretically optimal representations for k‑ary trees and multisets with constant‑time navigation and rank/select operations.

Abstract

We consider the indexable dictionary problem which consists in 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 e 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 B(n,m) + o(n) + O(lg lg m) bits to store a set of size n, where B(n,m) = ⌈lg (nm)⌉ 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 two applications of our dictionary structure:• An information-theoretically optimal representation for k-ary cardinal trees (aka k-ary tries). Our structure uses C(n,k) + o(n + lg k) bits to store a k-ary tree with n nodes and can support parent, i-th child, child labeled i, and the degree of a node in constant time, where C(n,k) is the minimum number of bits to store any n-node k-ary tree. Previous space efficient representations for cardinal k-ary trees required C(n,k) + Ω(n) bits.• An optimal representation for multisets where (appropriate generalisations of) the select and rank operations can be supported in O(1) time. Our structure uses B(n, m + n) + o(n) + O(lg lg m) bits to represent a multiset of size n from an m element set; the first term is the minimum number of bits required to represent such a multiset.