PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti

arXiv:0705.0552v1cs.DScs.DMcs.IT

TL;DR

The paper addresses how to combine succinct set representations with constant-time rank and select. It uses MSB bucketing and related dictionary constructions to achieve near-information-theoretic space, then extends them to trees, multisets, and prefix sums.

  • Problem

    The indexable dictionary problem asks for constant-time rank and select while representing a set near the information-theoretic lower bound.

  • Method

    The paper combines fully indexable dictionaries, searchable prefix-sum structures, and most-significant-bit bucketing to preserve ordering information while reducing space.

  • Results

    B(n, m) + o(n) + O(lg lg m) bits support constant-time rank and select on the RAM model, while B(n, m) + o(n) bits suffice in the cell probe model.

  • Takeaways & Limitations

    The representations extend to information-theoretically optimal or near-optimal encodings of k-ary trees, multisets, and prefix-sum sequences.

  • Takeaways & Limitations

    The paper focuses on static query time and space utilization without extensive consideration of preprocessing or dynamization.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces indexable dictionaries that combine constant-time membership-related functionality with constant-time rank and select while using near-optimal space. It applies this representation to trees, multisets, and prefix sums, while identifying boundaries of the space guarantees.

  • Indexable dictionaries: Constant-time rank and select operations are sought in a representation combining hashing speed with the sorted array’s ordering functionality.Rank returns an element’s predecessor count when present, while select returns the i-th smallest element.
  • Indexable dictionaries: B(n, m) + o(n) + O(lg lg m) bits support constant-time rank and select for n-element subsets of an m-element universe.B(n, m) is the information-theoretic lower bound for representing such subsets.
  • Indexable dictionaries: B(n, m) + o(n) bits suffice in the cell probe model for constant-time operations, answering a question raised by Fich and Miltersen and Pagh.The result also shows that n words of ⌈lg m⌉ bits suffice for constant-time membership queries under the stated condition.
  • Applications: C(n, k) + o(n) + O(lg lg k) bits represent k-ary cardinal trees while supporting standard navigation except subtree size in constant time.C(n, k) is the information-theoretic optimum for representing a k-ary tree with n nodes.
  • Applications: B(n, m+n) + o(n) + O(lg lg m) bits represent multisets with constant-time generalized rank and select operations.The bound follows the lower bound induced by the one-to-one mapping between multisets and n-element subsets of a universe of size m+n.
  • Applications: B(n, m+n) + o(n) bits support constant-time prefix sums for n non-negative integers summing to m.This representation is described as within o(n) bits of the information-theoretic optimum and more space-efficient than prior approaches.
  • Lower bounds: Some stated space bounds can exceed the information-theoretic lower bound when n is very close to m.The paper notes that the o(n) term may dominate B(n, m) in this regime, and constant-time rank or select would imply fullrank support with similar space.
  • Techniques used: MSB bucketing preserves ordering information while omitting shared most-significant bits, using succinct prefix sums instead of explicit bucket pointers.This distinguishes the approach from quotienting and earlier bucketing schemes that store explicit pointers.

2 Preliminaries

The preliminaries connect fully indexable dictionaries to searchable prefix sums and establish succinct bit-vector and dictionary building blocks. They also state a general hashing-based lemma for constant-time rank and select.

  • Fully indexable dictionaries: An FID supports rank and select on both a set S and its complement in constant time.FID operations are functionally equivalent to rank and select on both bits of a characteristic vector.
  • Searchable prefix sums: An FID using f(n, m+n) bits yields a searchable prefix-sum structure using the same space for n non-negative values summing to m.The reduction encodes each value as zeros followed by a one and maps the resulting bit string to a set.
  • Fully indexable dictionaries: m + o(m) bits suffice for an FID on a subset of [m] with constant-time operations.The construction uses a characteristic vector supporting rank_b and select_b for b ∈ {0, 1}.
  • Searchable prefix sums: m + n + o(m+n) bits represent a sequence of n non-negative numbers summing to m with constant-time sum and predecessor queries.This is the direct prefix-sum consequence of the FID construction.
  • Indexable dictionaries: The hash-based lemma represents S using |S|(lg m* + lg |S| + O(1)) bits while supporting rank and select in constant time.It assumes constant-time evaluable functions h_S and q_S that uniquely reconstruct keys and satisfy the stated universe-reduction conditions.
  • Indexable dictionaries: Shared hash-function descriptions for multiple sets can be represented in o(n*) + O(lg lg m*) bits while remaining accessible in constant time.The lemma applies to a sequence of sets whose total size is at most n*.

3 Saving n lg n bits using MSB bucketing

This section develops an MSB-bucketing representation that supports rank and select in constant time while using at most n⌈lg m⌉+o(n)+O(lg lg m) bits.

  • Theorem 3.1 gives an indexable dictionary using at most n⌈lg m⌉+o(n)+O(lg lg m) bits.
  • MSB bucketing partitions keys by leading bits, omits repeated bucket prefixes, and recursively processes large buckets.Small buckets are stored explicitly; large buckets are partitioned again.
  • The representation stores bucket-size information and concatenated bucket representations, with padding controlling each level’s space.The construction bounds the total representation by n(t+8+c) bits and then by n⌈lg m⌉ bits.
  • Rank computes the relevant bucket from the key’s leading bits, uses prefix sums of bucket sizes, and recurses only when necessary.The same strategy supports select in constant time.
  • Theorem 3.1’s auxiliary tables and function representations add only o(n)+O(lg lg m) bits.
  • A collection of independent sets totaling n elements can share the function representation while supporting rank and select on every set in constant time.The shared representation requires a constant-time oracle for prefix sums of the set cardinalities.

4 Obtaining a sublinear lower-order term

This section refines MSB bucketing and develops more space-efficient fully indexable dictionaries to reduce the lower-order term to o(n) in the sparse-universe regime.

  • Theorem 4.1 gives an indexable dictionary using at most B(n,m)+o(n)+O(lg lg m) bits.
  • An additional MSB-bucketing level reduces the earlier representation to n(⌈lg m⌉−⌊lg n⌋+2)+o(n)+O(lg lg m) bits.
  • The construction uses Θ(n√lg n) buckets, motivating a more space-efficient FID for representing bucket sizes.
  • Lemma 4.1 provides an FID using B(n,m)+O(m lg lg m/lg m) bits.The FID supports rank and select on a set and its complement through sparse and dense segment representations.
  • Sparse segments use sorted lists, while dense segments use constant-depth trees storing child-subtree counts to support navigation.Auxiliary rank and prefix-sum structures locate segment and block representations in constant time.
  • The resulting FID also yields a bit-vector representation using m+O(m lg lg m/lg m) bits with constant-time rank and select for both bit values.
  • For sufficiently sparse universes, Corollary 4.1 removes the additive O(lg lg m) term and achieves B(n,m)+o(n) bits.The supplied passage states the condition only partially as m is O(n√lg n).

5 An indexable dictionary in the cell probe model

The cell-probe construction removes the additive O(lg lg m) term while retaining constant-time rank and select operations. It uses a compact representation based on storing hashed projections and verification information.

  • The construction first gives a general representation using n(lg m + lg n + O(1)) bits.Keys are stored in sorted order, while a minimal perfect hash function and an index table support rank verification.
  • Keys are projected onto selected bit parts so that their projected values remain distinct, with additional information retained for verification.The selected parts are determined by a set R, and the representation stores h(x_i, R) and q(x_i, R) for each key.
  • Rank queries compute the projection of x, locate a matching stored projection, verify it using q-values, and return the corresponding rank or −1.Select is also supported in constant time using the same representation.
  • The RAM-model computation of h(x, R) and q(x, R) appears difficult in O(1) time.
  • The cell-probe result requires a constant-time oracle for prefix sums of the set sizes in the multiple-dictionary lemma.
  • B(n, m) + o(n) bits suffice for an indexable dictionary in the cell probe model.

6 Extensions and applications

The indexable dictionary is extended to multiple dictionaries, k-ary trees, multisets, and integer sequences. These representations preserve near-information-theoretic space while supporting constant-time queries.

  • 6.1 Multiple Indexable Dictionaries: The multiple-dictionary construction maps each pair ⟨i, j⟩ to i · m + j and represents the resulting set with one indexable dictionary.Ranks at dictionary boundaries are used to recover per-dictionary sizes, ranks, and selects.
  • 6.1 Multiple Indexable Dictionaries: B(n, ms) + o(n) + O(lg lg m) bits represent s = O(n) dictionaries over [m], supporting constant-time rank, select, and size queries.The first term is the minimum number of bits needed for the sequence of sets.
  • 6.1 Multiple Indexable Dictionaries: B(n, ms) + o(n) + O(lg lg m) bits are information-theoretically optimal for the represented sequence of dictionaries.The construction handles the increased universe size using a rounded m′, with only lower-order space increase.
  • 6.2 Representing k-ary Cardinal Trees: C(n, k) + o(n) + O(lg lg k) bits represent a k-ary tree while supporting parent, child, degree, and sibling-position operations in constant time.The tree is encoded as a sequence of sets containing outgoing edge labels.
  • 6.3 Multisets: B(n, m + n) + o(n) + O(lg lg m) bits represent a multiset of n elements from [m] with constant-time fullrank_m and select_m operations.The bound is information-theoretically minimal for multisets, and the dense case also has a representation without the O(lg lg m) term.
  • 6.3 Multisets: B(n, m + n) + o(n) bits represent a multiset with constant-time select_m, and represent a non-negative integer sequence summing to m with constant-time prefix sums.

7 Optimality considerations

The section shows that constant-time rank, select, and sum queries cannot generally be supported with space only polynomial in the information-theoretic bound in the cell probe model. These lower bounds follow by reducing the queries to fullrank, which has a superconstant worst-case lower bound.

  • Reduction framework: The fullrank reduction connects lower bounds for rank, select, and sum queries across sets, complements, bit vectors, and sequences.The section explicitly identifies these three query problems as reductions from fullrank.
  • Fullrank lower bound: Ω(lg n / lg lg n) worst-case time is required for fullrank queries using n^O(1) words in the cell probe model.The word size is (lg m)^O(1).
  • Rank and select: Constant-time rank queries cannot be supported for all n using B(n,m)^O(1) bits in the cell probe model.Otherwise, rank structures for a set and its complement would yield a forbidden constant-time fullrank structure.
  • Rank and select: Constant-time select queries cannot be supported for all n using B(n,m)^O(1) bits in the cell probe model.The reduction encodes a set as a bit vector and uses select on its complement to answer fullrank.
  • Prefix sums: Constant-time sum queries cannot be supported for all m,n using B(n,m+n)^O(1) bits in the cell probe model.A sequence encoding a set makes fullrank(j,S) equal to sum(j,X), contradicting the fullrank lower bound.

8 Conclusions

The paper concludes with succinct indexable dictionaries and applications that achieve near-optimal space with constant-time static queries. It also identifies preprocessing and dynamization as important practical boundaries and leaves tighter RAM-model bounds as open problems.

  • Indexable dictionaries: B(n,m)+o(n)+O(lg lg m) bits support constant-time rank and select for an n-element subset of an m-element universe.B(n,m) is the information-theoretic optimum for representing the subset.
  • Applications: C(n,k)+o(n)+O(lg lg k) bits represent a k-ary tree and support all navigational operations except subtree size in constant time.C(n,k) is the information-theoretically optimum tree representation size.
  • Applications: B(n,m)+o(m) bits support constant-time rank and select on a set and its complement through a fully indexable dictionary.The structure is functionally equivalent to rank0/1 and select0/1 on a bit vector.
  • Applications: Information-theoretically optimal representations support constant-time prefix sums for sequences of non-negative integers.The paper presents this as a principal application of the fully indexable dictionary.
  • Scope and open problems: Preprocessing and dynamization receive limited treatment; randomized hashing yields linear expected preprocessing for sorted input, while updates incur an Ω(lg n / lg lg n) lower bound.The update lower bound applies when insertions or deletions are allowed.
  • Scope and open problems: Open problems include achieving B(n,m)+o(n) bits in the RAM model and adding constant-time subtree size to the k-ary-tree representation.Both questions are stated explicitly in the conclusion.
Loading 0705.0552v1…