How to Approximate A Set Without Knowing Its Size In Advance

Rasmus Pagh; Gil Segev; Udi Wieder

Source-linked AI summary

How to Approximate A Set Without Knowing Its Size In Advance

Rasmus Pagh, Gil Segev, Udi Wieder

arXiv:1304.1188v2Apr 3, 2013cs.DS

TL;DR

The paper asks how to support dynamic approximate membership when the set size is unknown in advance, a setting where existing optimal structures are inadequate. It proves a super-linear space lower bound and gives matching constructions, including one with highly efficient operations. The main practical limitation is that the first construction has logarithmic query time, while the second incurs non-trivial hidden constants after de-amortization.

Problem
Most approximate membership structures require knowing n in advance, although practical applications may need unknown final sizes or compactness during growth.
Method
The paper proves a compression-based lower bound and develops two constructions using geometrically increasing structures and a carefully chosen superset stored in a dynamic dictionary.
Results
(1 −o(1))n log(1/ǫ) + Ω(n log log n) bits are necessary, and matching space is achieved; a construction supports constant-time membership queries with high probability.
Takeaways & Limitations
Unknown-size approximate membership inherently costs an additional Ω(n log log n) term, but this bound can be matched by efficient data structures.
Takeaways & Limitations
The first construction has O(log n) membership queries, while de-amortizing the second construction introduces non-trivial hidden constants.

Abstract

from arXiv · show

The dynamic approximate membership problem asks to represent a set S of size n, whose elements are provided in an on-line fashion, supporting membership queries without false negatives and with a false positive rate at most epsilon. That is, the membership algorithm must be correct on each x in S, and may err with probability at most epsilon on each x not in S. We study a well-motivated, yet insufficiently explored, variant of this problem where the size n of the set is not known in advance. Existing optimal approximate membership data structures require that the size is known in advance, but in many practical scenarios this is not a realistic assumption. Moreover, even if the eventual size n of the set is known in advance, it is desirable to have the smallest possible space usage also when the current number of inserted elements is smaller than n. Our contribution consists of the following results: - We show a super-linear gap between the space complexity when the size is known in advance and the space complexity when the size is not known in advance. - We show that our space lower bound is tight, and can even be matched by a highly efficient data structure.

1 Introduction

The paper studies approximate membership when set size is unknown in advance, establishing a super-linear space gap and matching upper bounds with efficient operations.

1 Introduction: Unknown set sizes are important because most existing structures require advance knowledge of n, while practical use may also need compactness before the final size is reached.The paper frames this as an insufficiently explored variant of dynamic approximate membership.
1.1 Our Contributions: A lower bound shows that unknown-size approximate membership requires (1 −o(1))n log(1/ǫ) + Ω(n log log n) bits after some n > u^δ insertions.This establishes a super-linear gap relative to the known-size setting.
1.3 Overview of Our Contributions: The lower-bound proof uses compression: after insertion, the represented superset must grow significantly rather than merely adding the newly inserted element.This growth requirement contrasts with exact dictionaries, whose internal representation can add only the new element.
1.3 Overview of Our Contributions: A first construction matches the lower bound up to lower-order terms using geometrically increasing dynamic structures, with expected amortized constant insertion time but Θ(log n) membership queries.The query time arises because a separate membership query is needed for each existing structure.
1.3 Overview of Our Contributions: A second construction matches the bound with constant-time worst-case membership queries with high probability and can de-amortize insertions to constant worst-case time with increased space.Its design stores a carefully chosen superset in one dynamic dictionary; the refinement limits each earlier subsequence’s contribution to O(2^i) stored values.
1.3 Overview of Our Contributions: The constructions also support deletions when no false positives are deleted.This deletion guarantee is explicitly conditional.

2 Preliminaries

The preliminaries establish the computational model, notation for sampling and indexing, and k-wise independence for hash-function collections.

For an integer n, [n] denotes {1, ..., n}; arrows denote sampling from a random variable or uniformly from a finite set.
The unit-cost RAM model stores universe elements in w = ⌈log u⌉-bit words and treats standard word operations as constant-time.
A function collection is k-wise independent when outputs on any k distinct inputs are jointly uniform over the target range.
More generally, k-wise δ-dependence requires the output distribution on k distinct inputs to be δ-close in statistical distance to uniform.

3 The Lower Bound: From Approximate Membership to Compression

The lower-bound proof converts approximate membership states into compressed encodings of insertion sequences. It first fixes randomness by averaging, then exploits growth in the stored positive-response superset to derive the space lower bound.

3 The Lower Bound: From Approximate Membership to Compression: (1−o(1))n log(1/ǫ) + Ω(n log log n) bits is necessary after some n > u^δ insertions for every arbitrarily small constant 0 < δ < 1.The bound follows by choosing n and γ = 2(log n)^η for a constant 0 < η < 1.
3 The Lower Bound: From Approximate Membership to Compression: The proof reduces randomized data structures to deterministic ones by fixing internal randomness through a standard averaging argument.The resulting deterministic structure measures false positives over a uniformly sampled element.
3.1 From Randomized to Deterministic Approximate Membership: No false negatives imply that every inserted sequence S is contained in the positive-response set ˆS_r for any fixed random string r.
3.1 From Randomized to Deterministic Approximate Membership: Lemma 3.2 guarantees a fixed random string r* for which at least half of all insertion sequences have positive-response sets of measure below 4ǫ.
3.2 A Compression Argument for Deterministic Approximate Membership: The compression argument partitions sequences into geometrically growing subsequences and selects a prefix interval where the positive-response measure increases substantially.
3.2 A Compression Argument for Deterministic Approximate Membership: Encoding the selected subsequence using its positions, the data-structure state, and remaining items yields a length constrained by the number of possible insertion sequences.The construction explicitly accounts for the state size b_i, uncompressed items, and positional information.

4 Construction 1 (Warm-Up): Geometrically-Increasing Data Structures

The warm-up construction uses approximate membership structures with geometrically increasing capacities. It achieves near-optimal space, but membership queries must inspect every structure created so far.

The construction allocates dynamic approximate membership structures B_i for consecutive insertion subsequences of geometrically increasing sizes 2^i.
The false positive rates ǫ_i are chosen so their infinite sum is at most ǫ by a union-bound argument.The construction uses Σ_i ǫ_i = Θ(ǫπ^2/6) before adjusting constants.
Using near-optimal known-size structures gives space (1 + o(1))n log(1/ǫ) + O(n log log n) bits after n insertions.
Insertions take expected amortized constant time, while membership queries take O(log n) time because the queried element may belong to any B_i.
The resulting structure maintains false positive rate at most ǫ while providing the stated space and operation bounds for unknown set sizes.

5 Construction 2: Constant-Time Operations

Construction 2 uses progressively sized, hashed dictionaries to match the unknown-size space bound while supporting constant-time membership queries and expected amortized constant-time insertions. Bucketing controls transition overhead, and extensions address worst-case insertion time and deletions.

Basic construction: Construction 2 maintains a dynamic dictionary for geometrically grouped subsequences, transitioning from D_i−1 to D_i when a new subsequence begins.Each stored pair uses h_i(x) as its key and g_i(x) as its associated value; membership queries test the current dictionary with h_i(x).
Optimal space via bucketing: Bucketing reduces transition overhead by hashing elements into u^δ/2 buckets and interleaving their memory words.For u^δ < n ≤ u, the buckets are nearly balanced except with polynomially small probability, and at most one bucket transitions at a time.
Performance analysis: Theorem 5.1 guarantees false positive rate ǫ + u^-c and space at most (1 + o(1))n log(1/ǫ) + O(n log log n) bits for n > u^δ.The construction also supports expected amortized constant-time insertions and worst-case constant-time membership queries.
Performance analysis: The construction achieves constant-time membership queries in the worst case and constant expected amortized insertion time, with space bounded by (1 + o(1))n log(1/ǫ) + O(n log log n).A separate de-amortization extension gives worst-case constant-time insertions at increased space O(n log(1/ǫ) + n log log n).
Extensions: Deletions require a secondary dictionary for identical signatures because a signature may be a false positive in one structure and a true positive in another.The approach stores problematic false positives separately rather than relying only on a multiset of signatures; the expected number of such false positives is O(n/log u).

6 Directions for Future Research

The paper identifies theoretical and practical directions for improving unknown-size approximate membership structures. Open goals include tightening the additive lower-bound constant, combining optimal space with worst-case operations, and reducing practical overhead.

Theoretical directions: A theoretical goal is to identify the leading constant in the additive Ω(n log log n) lower-bound term.
Theoretical directions: Another goal is a structure combining (1 + o(1))n log(1/ǫ) + O(n log log n) bits with constant-time worst-case operations with high probability.
Practical directions: The authors seek a more practical solution matching the space lower bound when no upper bound on the set size is known.The first construction has O(log n) membership queries, while the second has non-trivial hidden constants from de-amortization.