Streaming Algorithms from Precision Sampling

Original · EN

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₁,...xₙ), which is useful for the following applications. 1) Estimating the Fₖ-moment of x, for k>2. 2) Estimating the ℓₚ-norm of x, for p∈[1,2], with small update time. 3) Estimating cascaded norms ℓₚ(ℓq) for all p,q>0. 4) ℓ₁ sampling, where the goal is to produce an element i with probability (approximately) |xᵢ|/x₁. It extends to similarly defined ℓₚ-sampling, for p∈ [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 ∑ᵢ₌₁ⁿ aᵢ from weak estimates of each real aᵢ∈[0,1]. More precisely, the estimator first chooses a desired precision uᵢ∈(0,1] for each i∈[n], and then it receives an estimate of every aᵢ within additive uᵢ. Its goal is to provide a good approximation to ∑ aᵢ while keeping a tab on the "approximation cost" ∑ᵢ (1/uᵢ). Here we refine previous work [Andoni, Krauthgamer, and Onak, FOCS 2010] which shows that as long as ∑ aᵢ=Ω(1), a good multiplicative approximation can be achieved using total precision of only O(n n).