PaperlayerView exact revision on arXiv

Source-linked AI summary

Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries

Gabriel Marques Domingues

arXiv:2610.01853v1cs.DS

TL;DR

Dynamic rank/select dictionaries seek low redundancy while supporting optimal-time operations. This paper constructs such dictionaries in the standard Word-RAM and extends a dynamic-dictionary lower bound to super-polynomial universes. For polynomial-size sets, the upper bound is optimal at the stated redundancy, and the structure also supports queries on the complement.

  • Problem

    Dynamic rank/select dictionaries aim to use few bits while retaining optimal operation time, but prior constructions commonly use Ω(n) redundancy and dynamic redundancy lower bounds were limited.

    Source: §1 · p. 2

  • Method

    The paper advances a dynamic rank/select construction, extends it to complement queries, and adapts a prior lower-bound approach to super-polynomial universes.

    Source: §1 · p. 2

  • Results

    For n=w^O(1), the construction uses O(n log^(k) w) redundancy with O(k) operation time, and this upper bound is optimal.

    Source: §1 · pp. 2–3, §2.1 · p. 3

  • Takeaways & Limitations

    For polynomial-size sets, the standard Word-RAM suffices for the optimal time-space trade-off at the stated redundancy.

    Source: §1 · p. 3

    Deterministic dynamic dictionaries with o(n) redundancy and worst-case times remain an open problem.

    Source: §6 · p. 12

Abstract

from arXiv · show

In this paper, we study the number of bits required to construct a dynamic dictionary with optimal time for $\texttt{rank}/\texttt{select}$ operations. Using the standard (multiplication) Word-RAM model with $w$-bit words, we construct a data-structure for a dynamic $\texttt{rank}/\texttt{select}$ dictionary for a set $S\subseteq\{0,1,\cdots,u-1\}$ of $n$ elements that, given a parameter $1\leq k\leq \log^*w$, uses $$\operatorname{lg}\binom{u}{n}+\mathcal{O}(n\log^{(k)}w)\text{ bits}$$ taking optimal $\mathcal{O}(k+\log_w n)$ time (worst-case) for all operations. We show optimality for $n=w^{\mathcal{O}(1)}$ by extending the lower bound of Li, Liang, Yu, and Zhou [FOCS 2023] to super-polynomial universes: any dynamic dictionary for $n\leq \sqrt{u}$ elements that uses $\operatorname{lg}\binom{u}{n}+\mathcal{O}(n\log^{(k)}n)$ bits requires $\Omega(k)$ time for operations. Lastly, we extend the data-structure to a dynamic fully indexable dictionary (that also supports $\texttt{rank}/\texttt{select}$ on the complement of $S$).

1 Introduction

The paper studies space-efficient dynamic rank/select dictionaries in the Word-RAM, where prior constructions and lower bounds leave open questions about redundancy. It presents a construction and lower bound for small sets, and extends the structure to support queries on the complement.

1 Introduction

  • Rank counts set elements less than or equal to x, while select returns the i-th smallest element; the dynamic setting also supports insertions and deletions.The operations also yield predecessor and membership queries.Source: §1 · p. 2
  • Prior dynamic rank/select structures with optimal operation time generally use Ω(n) redundancy, while known redundancy lower bounds for dynamic dictionaries were limited.The cited [LLYZ23b] lower bound applied only to polynomial universes, and earlier rank/select bounds were stronger in that setting.Source: §1 · p. 2
  • For n=w^O(1), the construction achieves O(n log^(k) w) redundancy with O(k) operation time, and its upper bound is optimal.It also supports rank/select on the complement of S.Source: §1 · pp. 2–3
  • For n≤√u, any dynamic dictionary using O(n log^(k) w) redundancy requires Ω(k) time, even for membership queries alone.The lower-bound proof adapts [LLYZ23b] to super-polynomial universes.Source: §1 · p. 2
  • For k=log* w, the construction is the first deterministic one with O(n) redundancy and O(log* w) time for sets of poly(w) elements.The paper identifies achieving o(n) redundancy with the optimal time-space trade-off as an open question.Source: §1 · p. 3

2 Contributions and Techniques

For polynomial-size sets, the paper gives deterministic dynamic rank/select dictionaries with O(n log^(k) w) redundancy and O(k) operation time, then extends the construction to fully indexable dictionaries and arbitrary set sizes. A lower bound for small sets establishes the time trade-off’s optimality in the polynomial-size regime.

2.1 Dynamic Rank/Select Dictionaries

  • For n = w^O(1), Theorem 1 achieves O(n log^(k) w) redundancy and O(k) time for rank, select, and updates.The construction recursively handles select at depth k, uses Elias–Fano encoding for the stored sequence, and adds a rank mechanism with O(n) redundancy and O(1) time.Source: §2.1 · p. 3
  • For every 1 ≤ k ≤ log* w, a dynamic fully indexable dictionary for n = w^{O(1)} elements supports rank and select on S and its complement, using O(n log^(k) w) redundancy and O(k) time.Source: §2.1 · pp. 3–4
  • For arbitrary n, Theorem 3 gives a fully indexable dictionary with O(n log^(k) w) redundancy and O(log_w n + k) time for all operations.The extension applies cardinality reduction to the polynomial-size construction.Source: §2.1 · p. 4
  • For k = O(1), the construction is the first deterministic dynamic FID with o(n log w) bits and O(log_w n) operation time; at k = log* w, it uses O(n) redundancy.The paper notes Elias–Fano encoding and de-amortized cardinality reduction each incur Ω(n) bits in this construction.Source: §2.1 · p. 4

2.2 Lower Bound

  • With log u = Θ(w), any dictionary for n ≤ √u using O(n log^(k) n) redundancy needs Ω(k) time for membership queries or updates.The proof uses a hard sequence of insertions, queries, and deletions; its expected probe cost is Ω(nk) across the meta-operations.Source: §2.2 · p. 4
  • Together with the Ω(log_w n) lower bound of, this shows that our construction in Theorem 1 is optimal for the regime n = w^O(1).The remaining challenge is to consider regimes that can achieve o(n) redundancy.Source: §2.2 · p. 4

3 Preliminaries

The paper uses a Word-RAM with w-bit words and a memory-accounting model based on the highest address used. Its construction builds on rank indices, searchable partial sums, and cardinality reduction from prior work.

3 Preliminaries

  • The Word-RAM permits constant-time single-word reads and writes and standard w-bit operations, including multiplication; lookup tables may use polylogarithmically many words if computable in linear time.The allowed standard operations include addition, bitwise operations, and shifts.Source: §3 · p. 4
  • In the MB memory model, space is measured by the highest memory address used, so unused intermediate cells still count toward memory usage.Concatenating structures of s1 and s2 bits can use s1 + O(s2) bits.Source: §3 · p. 5
  • Lazy updates de-amortize segment resizing by moving O(1) elements between segments on each access or update, with the constant chosen to finish before another resize is needed.The resizing arises when segment sizes halve or double.Source: §3 · p. 5

3.1 Previous constructions

  • The construction separates storage and select/update support into a select dictionary, while a rank index accesses that dictionary to support rank and updates.The cited compressed rank index for n = w^O(1) elements uses O(nw^epsilon) bits and supports rank and update in constant time.Source: §3.1 · p. 5
  • Searchable partial sums support prefix sums, search, and updates; equivalently, the paper describes them as access, rank, and suffix-increment operations on a sorted array.For arrays of n = w^O(1) elements with O(log w)-bit entries, a cited structure uses O(n log w) bits and supports all operations in O(1) time.Source: §3.1 · p. 5
  • Cardinality reduction converts an arbitrary-size dynamic FID problem to one on O(w^2) elements, adding O(n) redundancy and O(log_w n) operation time.The paper applies this reduction to its polynomial-size FID construction.Source: §3.1 · p. 6

4 Upper bound

The upper-bound section builds low-redundancy dynamic rank/select dictionaries, then extends them to support operations on the complement. Its constructions use structured sequence storage, a special small-universe design, and rank information stored within the select structure.

4 Upper bound

  • The section’s upper-bound constructions are presented as the basis for results shown to be tight in the following section.The section covers dynamic rank/select dictionaries and their extension to fully indexable dictionaries.Source: §4 · p. 6

4.1 Achieving low redundancy

  • Theorem 7 stores a dynamic sequence in n lg u + O(n log^(k) w) bits with O(k)-time access and updates, using a structured layout of superblocks, blocks, and buffers.Recursive indexing reduces the redundancy, while the buffer region supports updates and lazy operations de-amortize restructuring.Source: §4.1 · pp. 6–7

4.2 Small universe

  • When log u = O(√w), a dynamic rank/select dictionary for n = w^O(1) elements uses O(n) redundancy and supports rank, select, and updates in O(1) time.The construction keeps blocks sorted and uses intervening separator elements to direct rank queries.Source: §4.2 · pp. 8–9

4.3 Supporting rank

  • For n = w^O(1), the construction supports rank/select and updates in O(k) time with O(n log^(k) w) redundancy, including for fully indexable dictionaries.The select structure uses Elias–Fano encoding; the rank extension reuses redundant bits in the element sequence to store its rank index.Source: §4.1 · pp. 7–8, §4.3 · p. 10, §4.4 · p. 11

4.4 Extension to FIDs

  • The fully indexable dictionary extends the rank/select structure to support rank/select on the complement with O(n log^(k) w) redundancy and O(k) time.The extension uses a partial-sum structure and adapts the rank construction to the complement.Source: §4.4 · p. 11

5 Lower bound

The lower-bound argument adapts earlier techniques to universes as large as u ≥ n^2. Its hard instance and probe-counting lemmas yield an Ω(k) time lower bound for dictionaries with the specified redundancy.

5 Lower bound

  • The proof adapts [LLYZ23b] to handle u ≥ n^2 and simplifies the argument for R = Ω(n), avoiding the polynomial-universe requirement.It focuses on probes occurring in multiple segments, addressing a technical issue also resolved in [D’A26].Source: §5 · pp. 11–12
  • With enough meta-operations divided into λ segments, the expected number of cells probed in multiple segments is at least m/64 under the lemma’s stated conditions.The conditions include n ≤ √u, 1024 ≤ λ ≤ log n, and m ≥ 64 max{R/log λ, nλ/log u}.Source: §5 · p. 12
  • For log u = Θ(w), n ≤ √u, and redundancy R = O(n log^(k) n), the hard instance requires Ω(nk) expected cell probes across its meta-operations.The hard instance inserts a random set, then repeatedly queries and deletes a permuted element while inserting an element from a second disjoint set.Source: §5 · p. 12

6 Discussion and Open problems

The paper concludes that its operation times are optimal for the achieved redundancy when n ≤ w^O(1), while identifying unresolved trade-offs for smaller universes and sublinear redundancy.

6 Discussion and Open problems

  • For n ≤ w^O(1), the paper states that its dynamic rank/select operation time is optimal for the redundancy used.The conclusion attributes this tightness to a generalization of the dynamic-dictionary lower bound to super-polynomial universes.Source: §6 · p. 12
  • The trade-offs between universe size and redundancy remain open when log u = o(w), despite better upper bounds in some smaller-universe regimes.The paper notes better results for log u = O(√w) in the standard Word-RAM model and log u = w/polylog w in the cell-probe model.Source: §6 · p. 12
  • Worst-case time for dynamic ordered dictionaries with o(n) redundancy remains unresolved; the cited randomized result has optimal amortized time in expectation, while de-amortization adds O(n) redundancy.The paper states that lower bounds require at least Ω(log* w + log(n/R)) time when R < n.Source: §6 · p. 12

A Outer Lemma

The Outer Lemma proves that sufficiently many cells must be probed across multiple segments, using a communication-game contradiction. Its proof extends the approach of [LLYZ23b] beyond polynomial universes.

A Outer Lemma

  • The proof assumes few cross-segment probes and constructs a communication protocol that contradicts the lower bound on m.It follows [LLYZ23b] while removing the requirement that u = n^O(1); for R ≥ n, it considers only probes in different segments.Source: A Outer Lemma · pp. 15, 17
  • Alice divides insertions and deletions into λ segments and sends Bob memory-state information and messages encoding each segment’s insertion keys.The protocol uses a flag for segments with few multiply-probed cells and indexes into families of candidate sets.Source: A Outer Lemma · pp. 15–16
  • The Inner Lemma bounds how often two disjoint sets can yield nearby memory states, supporting the communication lower bound.Its stated setting has log u = w, n ≤ √u, and 64n/log u < µ < n/2.Source: A Outer Lemma · p. 16
  • At least m/64 cells are expected to be probed in multiple segments when m ≥ 64 max{R/log λ, nλ/log u} and 1024 ≤ λ ≤ log n.The lemma assumes log u = w and n ≤ √u, for sufficiently large n.Source: A Outer Lemma · p. 16

B Inner lemma

The Inner Lemma uses a communication game to bound the probability that two disjoint sets produce nearby memory states. Its proof follows [LLYZ23b] but simplifies the argument for large µ.

B Inner lemma

  • The proof follows [LLYZ23b] but uses a simplification for large µ to avoid randomized set separators.This drops some requirements, including bounds on the expected size of SD,A, and sidesteps the issue pointed out in [D’A26].Source: B Inner lemma · p. 17
  • For log u = w, n ≤ √u, and 64n/log u < µ < n/2, the lemma considers random K, disjoint A and B, and a sequence D drawn from K.K has n elements, A and B each have µ elements outside K, and D is a uniform sequence of µ elements of K.Source: B Inner lemma · p. 17
  • When the two resulting memory states are within µ/6 cells, Alice sends Bob a mixed memory state and probe-set information so he can recover CD,A and learn (K \ D) ∪ A.Bob already knows D; Alice then sends an index of A in (K \ D) ∪ A.Source: B Inner lemma · p. 18
Loading 2610.01853v1…