Source-linked AI summary
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems
Hossein Jowhari, Mert Sağlam, Gábor Tardos
TL;DR
The paper addresses space-efficient sampling from vectors defined by streaming updates, especially when updates may be negative. It sharpens precision-sampling analyses and introduces a different L0 approach, obtaining improved sampler and duplicate-finding bounds alongside matching lower bounds.
Problem
Negative updates make it non-trivial to maintain samples from the Lp distribution in data streams, despite earlier approximate samplers and their applications.
Method
The paper combines precision sampling with sharper count-sketch error analysis and stronger randomness, uses sparse recovery for L0 sampling, and applies augmented-indexing reductions for lower bounds.
Results
The paper obtains O(ε^-p log^2 n) space for p ∈ (1,2), O(ε^-1 log^2 n) for p ∈ (0,1), O(log^2 n) L0 sampling and duplicate finding, plus Ω(log^2 n) lower bounds.
Takeaways & Limitations
For constant ε, the sampling algorithms are optimal up to constant factors, while duplicate finding and heavy hitters receive tight space bounds.
Takeaways & Limitations
The claimed approximation of |x_i|^p/||x||_p^p cannot hold for p < 2 because it would contradict an Ω(ε^-2) Hamming-distance estimation lower bound.
Abstract
from arXiv · showhide
In this paper, we present near-optimal space bounds for Lp-samplers. Given a stream of updates (additions and subtraction) to the coordinates of an underlying vector x \in R^n, a perfect Lp sampler outputs the i-th coordinate with probability |x_i|^p/||x||_p^p. In SODA 2010, Monemizadeh and Woodruff showed polylog space upper bounds for approximate Lp-samplers and demonstrated various applications of them. Very recently, Andoni, Krauthgamer and Onak improved the upper bounds and gave a O(ε^{-p} log^3 n) space εrelative error and constant failure rate Lp-sampler for p \in [1,2]. In this work, we give another such algorithm requiring only O(ε^{-p} log^2 n) space for p \in (1,2). For p \in (0,1), our space bound is O(ε^{-1} log^2 n), while for the $p=1$ case we have an O(log(1/ε)ε^{-1} log^2 n) space algorithm. We also give a O(log^2 n) bits zero relative error L0-sampler, improving the O(log^3 n) bits algorithm due to Frahling, Indyk and Sohler. As an application of our samplers, we give better upper bounds for the problem of finding duplicates in data streams. In case the length of the stream is longer than the alphabet size, L1 sampling gives us an O(log^2 n) space algorithm, thus improving the previous O(log^3 n) bound due to Gopalan and Radhakrishnan. In the second part of our work, we prove an Omega(log^2 n) lower bound for sampling from 0, \pm 1 vectors (in this special case, the parameter p is not relevant for Lp sampling). This matches the space of our sampling algorithms for constant ε> 0. We also prove tight space lower bounds for the finding duplicates and heavy hitters problems. We obtain these lower bounds using reductions from the communication complexity problem augmented indexing.
1 Introduction
The paper develops near-optimal space-efficient Lp-samplers for turnstile streams, improves L0 sampling and duplicate finding, and proves matching lower bounds for several streaming problems.
- Problem setting: Lp-samplers output coordinates according to their |x_i|^p weights, but negative updates make maintaining such samples non-trivial.The paper studies streams of additions and subtractions defining an underlying vector x.
- Lp-samplers: O(ε^-p log^2 n) space suffices for ε-relative-error Lp-sampling when p ∈ (1,2), improving the prior O(ε^-p log^3 n) bound.The sharper count-sketch error analysis removes a logarithmic factor while preserving the dependence on ε.
- Lp-samplers: O(ε^-1 log^2 n) space is achieved for p ∈ (0,1), and O(log(1/ε)ε^-1 log^2 n) space for p = 1.The construction follows the precision-sampling structure but uses stronger randomness and additional conditioning arguments.
- L0-sampling: O(log^2 n) space yields a zero-relative-error L0-sampler, improving the previous O(log^3 n) algorithm.The algorithm detects nonzero coordinates using random subsets, exact sparse recovery, and Nisan’s pseudorandom generator.
- Applications: O(log^2 n) space solves one-pass duplicate finding for streams longer than the alphabet, improving the previous O(log^3 n) bound.A sparse-recovery combination also gives O(log^2 n + s log n) space for streams of length n − s.
2 The Lp Sampler
The paper develops a one-pass approximate Lp-sampler for 0 < p < 2 using random scaling, count-sketch recovery, and norm estimation. It establishes sampling guarantees with Θ(ε) relative error and improves space bounds, while treating L0 sampling separately.
- Algorithm: O(log n) count-sketch repetitions estimate each coordinate while controlling approximation error through the residual after extracting the largest m coordinates.The count-sketch uses pairwise-independent hash and sign functions, and its output supports sparse recovery and error estimation.
- Algorithm: The sampler combines k-wise independent random scaling, a count-sketch, and two norm-estimation procedures in one streaming algorithm.The count-sketch processes the scaled vector z, while the estimators approximate ||x||_p and the residual error of the sparse approximation.
- Guarantees: Θ(ε) relative error and success probability are achieved because the output probability is (ε + O(ε^2))|x_i|^p/r^p, with coordinate estimation error at most ε.Here r is a high-probability constant-factor estimate of ||x||_p, and conditioning on a fixed scaling factor yields controlled abort probability.
- Space bounds: O(ε^-max(1,p) log^2 n log(1/δ)) space suffices for p ≠ 1, while p = 1 uses O(ε^-1 log(1/ε) log^2 n log(1/δ)) space.The algorithm applies for 0 < p < 2; its method does not appear to extend to p = 2.
- Lower bounds: Ω(log^2 n) space is necessary for sampling from 0, ±1 vectors, making the constant-error sampling bounds tight up to constant factors.The lower bound applies even when only overall distributional closeness is required, rather than coordinatewise relative-error sampling.
- L0 sampler: O(log^2 n log(1/δ)) bits suffice for a zero-relative-error L0 sampler that outputs a coordinate with probability at least 1 − δ.The L0 algorithm uses random subsets, exact sparse recovery, and Nisan’s pseudorandom generator rather than precision sampling.
3 Finding Duplicates
The paper develops one-pass algorithms for finding duplicates in streams, using L1 sampling and sparse recovery, with space bounds that are tight in key regimes. It also extends the problem to streams of varying lengths and establishes matching or near-matching lower bounds.
- Streams of length n + 1: O(log^2 n log(1/δ)) space suffices for a one-pass algorithm on streams of length n + 1, with failure probability at most δ.The algorithm outputs a duplicate with low error probability or FAIL.
- Streams of length n + 1: The construction subtracts one from every coordinate, increments coordinates for arriving items, and uses an L1 sampler to identify a positive coordinate.At stream end, duplicate items have positive coordinates, singleton items have zero coordinates, and absent items have negative coordinates.
- Streams of length n + 1: A perfect L1 sample is positive with more than half probability, yielding a duplicate with probability at least 1/4 after accounting for sampling error and failure.Repeating O(log(1/δ)) independent instances reduces the failure rate to δ while keeping the error rate low.
- Shorter streams: For streams of length n − s, the paper gives an O(s log n + log^2 n log(1/δ)) space algorithm that certifies NO-DUPLICATE when no duplicate exists.Otherwise it returns a duplicate with high probability or reports FAIL with probability at most δ.
- Longer streams: For streams of length n + s, a duplicate can be found using O(min{log^2 n, (n/s) log n}) bits with constant probability.The algorithm combines uniform random sampling when n/s is small with the length-n + 1 method when n/s ≥ log n.
4 Lower Bounds
The paper derives lower bounds for Lp-sampling, duplicate finding, and heavy hitters through reductions from augmented indexing and universal relation communication problems. These bounds match the paper’s upper bounds in key constant-error regimes.
- The lower bounds use augmented indexing, where Alice sends one message and Bob must recover a designated coordinate given earlier coordinates.A related universal relation problem asks the final recipient to output an index on which two promised-different strings disagree.
- Finding the same differing index for both communication players is harder than requiring only the last recipient to learn a differing index.The paper distinguishes these universal-relation variants when relating communication complexity to streaming lower bounds.
- Omega(log^2 n) space is necessary for one-pass duplicate finding, even when no stream element appears more than twice.The reduction uses universal relation communication and constructs streams whose duplicates reveal differing coordinates.
- Omega(log^2 n) bits are required for one-pass Lp-sampling, even when every coordinate is in {-1, 0, 1}.For constants δ < 1 and ε < 1, the same lower bound holds for ε relative-error samplers with failure probability δ.
- Omega(φ^-p log^2 n) space is required by any one-pass heavy hitter algorithm in the strict turnstile model.The lower bound is obtained by encoding augmented indexing into a heavy hitter instance.
A.1 Missing proofs
The missing proofs describe one- and two-round protocols for finding disagreements and a symmetrization argument that makes all differing indices equally likely to be reported.
- One-round protocol: An L0-sampling algorithm on x − y yields a one-round protocol that sends Alice’s memory after her updates to Bob.Bob’s sampled index is an almost uniformly random coordinate where x_i ≠ y_i.
- Two-round protocol: The algorithm tests O(log n) random sets and seeks a set containing at least one but not too many disagreement indices.A two-round protocol first identifies such a set, then concentrates on one set in the second round.
- Symmetrization: A shared random permutation and random coordinate flips symmetrize the inputs without communication, so every differing index is reported with equal probability.The reported index is mapped back through the inverse permutation.