Streaming Algorithms via Precision Sampling

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

Authors

• Alexandr Andoni
• Robert Krauthgamer
• Krzysztof Onak

Keywords

• Vectors
• Estimation
• Reactive power
• Approximation algorithms
• Approximation methods
• Algorithm design and analysis
• Random variables
• Streaming Algorithm
• Linear Function
• Update Time
• Reconstruction Algorithm
• Hash Function
• Algorithm For Problem
• Moment Estimation
• Additional Error
• Proof Of The Lemma
• Space Usage
• Reconstruction Time
• Multiple Errors
• Problem In The Literature
• streaming
• sampling
• moments
• cascaded norms