Streaming algorithms via precision sampling

DOI10.1109/FOCS.2011.82zbMATH Open1292.68186arXiv1011.1263MaRDI QIDQ5494976FDOQ5494976

Authors: Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Abstract: 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

e l l_{p}

-norm of

x

, for

p i n [1, 2]

, with small update time. 3) Estimating cascaded norms

e l l_{p} (e l l_{q})

for all

p, q > 0

. 4)

e l l_{1}

sampling, where the goal is to produce an element

i

with probability (approximately)

| x_{i} | / | x |_{1}

. It extends to similarly defined

e l l_{p}

-sampling, for

p i n [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