PaperlayerView exact revision on arXiv

Source-linked AI summary

Streaming Algorithms from Precision Sampling

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

arXiv:1011.1263v2cs.DScs.CG

TL;DR

The paper seeks a simpler, unified alternative for data-stream algorithms built around the Indyk–Woodruff design. It introduces Precision Sampling and applies it across streaming applications, including cascaded norms for all positive p and q, while improving or simplifying bounds for some problems.

  • Problem

    The paper seeks a simpler alternative design for several data-stream applications associated with the Indyk–Woodruff technique.

    Source: §1 · p. 2

  • Method

    Precision Sampling estimates sums from weak estimates, and the streaming algorithms scale coordinates randomly before applying heavy-hitter estimation.

    Source: §1 · p. 2, §1.2 · p. 5

  • Results

    The framework simplifies and unifies a family of data-stream algorithms, with new or improved bounds for some applications, including cascaded-norm algorithms for all p,q>0.

    Source: §1 · p. 2, §1.1 · p. 3

  • Takeaways & Limitations

    A shared random-scaling and heavy-hitter template applies across moment estimation, norm estimation, and sampling problems.

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

    The optimal total-precision bound for PSL remains open; the stated lower bound matches its bound only up to a factor of 1/ε.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

A technique introduced by Indyk and Woodruff [STOC 2005] has inspired several recent advances in data-stream algorithms. We show that a number of these results follow easily from the application of a single probabilistic method called Precision Sampling. Using this method, we obtain simple data-stream algorithms that maintain a randomized sketch of an input vector $x=(x_1,...x_n)$, which is useful for the following applications. 1) Estimating the $F_k$-moment of $x$, for $k>2$. 2) Estimating the $\ell_p$-norm of $x$, for $p\in[1,2]$, with small update time. 3) Estimating cascaded norms $\ell_p(\ell_q)$ for all $p,q>0$. 4) $\ell_1$ sampling, where the goal is to produce an element $i$ with probability (approximately) $|x_i|/\|x\|_1$. It extends to similarly defined $\ell_p$-sampling, for $p\in [1,2]$. For all these applications the algorithm is essentially the same: scale the vector x entry-wise by a well-chosen random vector, and run a heavy-hitter estimation algorithm on the resulting vector. Our sketch is a linear function of x, thereby allowing general updates to the vector x. Precision Sampling itself addresses the problem of estimating a sum $\sum_{i=1}^n a_i$ from weak estimates of each real $a_i\in[0,1]$. More precisely, the estimator first chooses a desired precision $u_i\in(0,1]$ for each $i\in[n]$, and then it receives an estimate of every $a_i$ within additive $u_i$. Its goal is to provide a good approximation to $\sum a_i$ while keeping a tab on the "approximation cost" $\sum_i (1/u_i)$. Here we refine previous work [Andoni, Krauthgamer, and Onak, FOCS 2010] which shows that as long as $\sum a_i=\Omega(1)$, a good multiplicative approximation can be achieved using total precision of only $O(n\log n)$.

1 Introduction

The paper presents Precision Sampling as a simpler, unified approach to data-stream algorithms, using random scaling and heavy-hitter estimation. It applies this framework to moment and norm estimation, sampling, and sum estimation from weak estimates under a precision-cost constraint.

1 Introduction

  • The paper offers a generic approach that simplifies and unifies a family of data-stream algorithms, with new or improved bounds for some applications.Its algorithms scale the stream by well-chosen random numbers and then solve a heavy-hitters problem.Source: §1 · p. 2

1.1 Streaming Applications

  • The F_k-moment algorithm improves space usage over prior bounds, with a further improvement later reported for some parameter regimes.The later improvement is credited to.Source: §1.1 · p. 3
  • For ℓ_p-norm estimation, the algorithm improves update time over for p∈(1,2] while using comparable space, but its p=1 space bound is worse than.The stated space is O(ε^-2-p log^2 n).Source: §1.1 · p. 3
  • For every p,q>0, the cascaded-norm algorithms have bounds tight up to (ε^-1 log n)^O(1) factors and give the first efficient algorithm for q>p>2.Their space complexity is controlled by a metric property generalizing the p-type constant of ℓ_q.Source: §1.1 · p. 3
  • For ℓ_p-sampling with p∈[1,2], the algorithm uses O(ε^-p log^3 n) space.The sampling goal is to return an index according to an approximation of the distribution proportional to |x_i|^p/∥x∥_p^p.Source: §1.1 · pp. 3–4

1.2 Precision Sampling

  • Precision Sampling estimates a sum from weak estimates of a_i∈[0,1], choosing precisions before seeing the values and accounting for the total precision cost.The lemma gives a (ρ, f·e^ε)-approximator to the sum with probability at least 2/3.Source: §1.2 · pp. 4–5
  • For k=O(1/(ρε^2)), the precision distribution has conditional expected cost O(k log n) on a high-probability event, and E[w^α]=O(k^α) for fixed α∈(0,1).The distribution W depends only on k.Source: §1.2 · p. 5

1.3 Connection to Priority Sampling

  • The sampling schemes share a scaling-and-heavy-hitters structure, but this paper handles negative weights and updates, unlike Priority Sampling’s positive-weight setting.The paper uses CountSketch/CountMin for approximate heavy-hitter extraction and post-processes the result differently.Source: §1.3 · pp. 5–6

2 Proof of the Precision Sampling Lemma

The Precision Sampling Lemma is proved using a distribution built from random reciprocal precisions and a reconstruction procedure. The proof bounds the estimator’s error and shows that a deterministic reconstruction preserves the needed concentration guarantees.

2 Proof of the Precision Sampling Lemma

  • The present lemma improves on the earlier version with a better expected-precision bound, pairwise independence, and a simpler construction and analysis.The analysis uses the inverse variable u = 1/w.Source: §2 · p. 6
  • The lemma’s sampling distribution takes the maximum of k reciprocals of independent uniform samples, with k set by the error parameters.The proof also bounds moments of this distribution, including E[w^α] = O(k^α/(1−α)) for α in (0,1).Source: §2 · pp. 6–7
  • The reconstruction forms indicator variables from the sampled precisions and uses their sum to estimate the target sum.The proof bounds the expectations and variance of the estimate, accounting for estimates that may depend adversarially on the sampled precisions.Source: §2 · pp. 6–7
  • A deterministic reconstruction replaces the randomized reconstruction without increasing the variance, so the same concentration bounds apply.The proof makes this comparison through the law of total variance and the pairwise independence of the sampled precisions.Source: §2 · p. 8

3 Applications I: Warm-Up

The applications combine precision sampling with a linear sketch and heavy-hitter estimation. The resulting algorithms estimate F_k moments and the ℓ_1 norm, with stated space and success guarantees; the sketch update time is O(log n).

3 Applications I: Warm-Up

  • The generic algorithm scales vector coordinates using precisions from the Precision Sampling Lemma, sketches them with hash tables, and reconstructs an estimate from heavy-hitter approximations.The sketch is linear, and its parameters are fixed by the application.Source: §3 · pp. 8–9

3.1 Estimating Fk Moments for k > 2

  • S = O(n^(1−2/p) · p^2 · ǫ^(−2−4/p) · log n) gives a (1+ǫ)-factor estimate of ∥x∥_p^p with probability at least 0.51 for p > 2.The algorithm is a randomized linear sketch with a deterministic estimator.Source: §3.1 · p. 9
  • For F_k estimation, the method applies precision sampling to a_i = |x_i|^p after using hash-table estimates as approximators, yielding the stated space bound.The proof first establishes that the coordinate estimates approximate |x_i|^p with high probability.Source: §3.1 · p. 10

3.2 Estimating ℓ1 Norm

  • S = O(ǫ^−3 log^2 n) gives a (1+ǫ)-factor estimate of ∥x∥_1 with probability at least 0.51.The guarantee applies for n ≥ 8 and 8/n < ǫ < 1/8.Source: §3.2 · p. 11

3.3 The Running Times

  • The sketch update time is O(log n); the described reconstruction takes O(n log n), with a heavy-hitter sketch offered to reduce reconstruction time.The text notes a space and update-time cost for that reconstruction improvement but the supplied bound is incomplete.Source: §3.3 · p. 12

4 Applications II: Bounds via p-Type Constant

This section applies Precision Sampling to norm estimation, using p-type bounds to control sketch space. It gives linear sketches for ℓp norms and extends the approach to mixed and cascaded norms.

4.1 ℓp-norm for p ∈[1, 2]

  • For p ∈ [1, 2], a randomized linear sketch uses O(ǫ−2−p log2 n) space and estimates ∥x∥p within factor 1 + ǫ with probability at least 0.51.The estimator combines repeated trials and returns their median; the proof establishes the final approximation guarantee.Source: §4.1 · p. 13
  • For ℓp norm estimation, choosing α ≥ 32+pǫ1−p makes each coordinate estimate a (1/wi, eǫ)-approximator to |xi|p under the stated bound Fp ≤ ω.The per-coordinate estimates are combined through Precision Sampling to approximate the norm.Source: §4.1 · p. 13

4.2 Mixed and cascaded norms

  • The generalized p-type is defined through randomized signs and sampling indicators, and bounds the space required by the resulting algorithms.The parameter uses κ-wise independent random-variable families and is applied to vectors in a finite-dimensional Banach space.Source: §4 · p. 12, §4.2 · pp. 14–15
  • For a Banach space X with a linear sketch, the construction yields a linear sketch for ∥x∥p,X using space controlled by the generalized p-type parameter.The stated space bound is SX(ǫ/2) · α(X, p, n, κ, O(pǫ−4 log n), 2/3) · O(log n).Source: §4.2 · p. 14
  • The mixed-norm construction represents each matrix row as a vector in X and stores sketches of those vectors in hash-table cells.The underlying Banach-space sketch estimates each cell to within 1 + ǫ/2.Source: §4.2 · p. 14
  • For mixed norms, repeated trials produce coordinate approximations, after which Precision Sampling gives a factor 1 + 2ǫ approximation with probability at least 0.51.The section bounds sketch space using the base sketch space and the generalized p-type parameter.Source: §4.2 · pp. 14–15
  • For ℓp,q norms, the section gives space bounds across parameter regimes that are tight up to (ǫ−1 log n)^O(1) factors.The bounds are stated separately for ranges including 0 < p ≤ q ≤ 2, q ≥ 2 with p < 2, and p, q ≥ 2.Source: §4.2 · p. 15

5 Applications III: Sampling from the Stream

The section extends the sketching approach to ℓp-sampling for p ∈ [1, 2]. Its algorithm returns an index with probability approximately proportional to |xi|p and an estimate of that coordinate’s pth-power magnitude.

5 Applications III: Sampling from the Stream

  • For p ∈ [1, 2], the linear sketch uses O(ǫ−p log3 n) space and returns an index whose distribution approximates |xi|p/∥x∥p p within factor 1 + ǫ.The returned value approximates |xi|p within factor 1 + ǫ.Source: §5 · p. 16
  • The sketch construction chooses precisions from a limited-independence family, giving update time O(ǫ−1 log n).It sets m = O(ǫ−1−p log2 n) and generates each wi as the maximum among k sampled precision values.Source: §5 · p. 16
  • The algorithm tests scaled coordinate estimates across hash tables and returns the unique index crossing threshold t = 4/ǫ in the first qualifying table.If no table has exactly one qualifying coordinate, it returns FAIL.Source: §5 · p. 16
  • Using k = O(ǫ−1 log n) independent trials makes the probability of finding a qualifying unique index high.The analysis states that each trial has probability at least Ω(ǫ) of finding exactly one qualifying index.Source: §5 · p. 17
  • Conditioning on j=j* with exactly one selected coordinate (Σ_i s_i,j=1), the selected index i* is drawn from a distribution D_x that (O(n^-2), 1+O(ε))-approximates |x_i|^p/||x||_p^p.Source: §5 · p. 17

6 Proofs of p-type inequalities

The proofs establish bounds used to control randomized sign-and-sampling expressions in the generalized p-type analysis. They split into parameter regimes and use moment, norm, and triangle-inequality arguments.

6 Proofs of p-type inequalities

  • For 0 < p ≤ q ≤ 2, the proof bounds the randomized expression using concavity, pairwise independence, and norm inequalities.It applies Markov’s bound to obtain an upper bound involving the sum of |xij|q.Source: §6 · p. 18
  • For q ≥ 2, the proof uses a higher moment of the randomized sum and bounds it through the sampled coordinates.The argument defines a moment κ = 2⌈q/2⌉ and proceeds by conditioning on the sampling indicators.Source: §6 · pp. 18–19
  • The remaining bounds use triangle inequalities and Markov’s inequality, with separate cases for p ≥ 1 and p ∈ (0, 1).The proof states corresponding sufficient bounds on α for each case.Source: §6 · p. 19

7 A lower bound on the total precision

This section proves lower bounds for estimating sums from weak per-item estimates. The argument connects precision choices to the number of underlying function values an estimator must effectively observe.

7 A lower bound on the total precision

  • The section’s lower-bound result applies under the stated conditions ǫ ∈ (0, 1/48) and α ≤ n/16.The displayed bound in that passage is truncated, so no numerical lower-bound expression is reported here.Source: §7 · p. 20
  • Any algorithm estimating the mean of a Boolean function within additive ǫ with probability at least 7/12 must make at least C/ǫ2 queries.The section also gives an expected-query lower bound of C/ǫ2 for an estimator succeeding with probability at least 2/3.Source: §7 · pp. 20, 22
  • The lower-bound argument shows that precision must account for roughly Θ(log n) possible magnitudes, requiring different weight scales to observe enough items at each magnitude.The text attributes an additional logarithmic factor in the lower bound to these distinct scales.Source: §7 · p. 22
  • The proof constructs inputs with many zero entries and a random subset of nonzero entries, so the estimator’s precision determines which Boolean values it can see.It relates the estimator to an additive approximation of the average of the underlying Boolean function.Source: §7 · p. 22
Loading 1011.1263v2…