Rajeev Raman
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 ε 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.
- Succinct indexable dictionaries with applications to encoding k-ary trees and multisets
Recommendations
Fully Functional Static and Dynamic Succinct Trees
We propose new succinct representations of ordinal trees and match various space/time lower bounds. It is known that any n-node static tree can be represented in 2n + o(n) bits so that a number of operations on the tree can be supported in constant time ...
Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets
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 ...
An Improved Succinct Representation for Dynamic k-ary Trees
CPM '08: Proceedings of the 19th annual symposium on Combinatorial Pattern Matchingk-ary trees are a fundamental data structure in many text-processing algorithms (e.g., text searching). The traditional pointer-based representation of trees is space consuming, and hence only relatively small trees can be kept in main memory. Nowadays,...
Comments