Streaming algorithms via precision sampling

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

s u m_{i = 1}^{n} a_{i}

from weak estimates of each real

a_{i} i n [0, 1]

. More precisely, the estimator first chooses a desired precision

u_{i} i n (0, 1]

for each

i i n [n]

, and then it receives an estimate of every

a_{i}

within additive

u_{i}

. Its goal is to provide a good approximation to

s u m a_{i}

while keeping a tab on the "approximation cost"

s u m_{i} (1 / u_{i})

. Here we refine previous work [Andoni, Krauthgamer, and Onak, FOCS 2010] which shows that as long as

s u m a_{i} = O m e g a (1)

, a good multiplicative approximation can be achieved using total precision of only

O (n l o g n)

.

Recommendations

Cited in

(24)

This page was built for publication: Streaming algorithms via precision sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494976)