**
Approximating Large Frequency Moments with Pick-and-Drop Sampling
**

*
Vladimir Braverman,
Rafail Ostrovsky
*

Given data Stream D={p1,p2,....,Pm} of size m of numbers from {1,...,n}, the frequency of i is defind as ƒi=|{j:pj=i}|b. The K-th frequency moment of D is defind as F^{k} = Σ_{n}^{I} = ƒ_{k}^{i}
We consider the problem of approximating frequency moments in insertion -only streams for K≥3.
For any constant c we show an Ο(n^{1-2/k}log(n)log^{(c)})(n)) upper bound on the space complexity of the problem. Here log_{(c)}(n) is the iterative log function.
Our main technical contribution is a non-uniform sampling method on matrices. We call our metod a pick-and-drop sampling;it samples a heavy element
(i.e., element i with frequency Ω(F _{k})) with probabilityΩ(1/n^{1-2/k}) and gives approximation ƒi≥(1-€)ƒi. In addition,
the estimations never exceed the real valus, that is ƒj≤ƒj for all j. For constant €, we reduce the space complexity of finding a heavy element to Ο(n^{1-2/k}log(n)log^{(c)})(n)) bits. we apply our method of recursive sketches and resolve the problem
with Ο(n^{1-2/k}log(n)log^{(c)})(n)) bits. We reduce the ratio between the upper and lower bounds from Ο(n^{1-2/k}log(n)log^{(c)})(n)). THus, we provide a (roughly) quadratic improvement of the result of Andoni, Krauthgamer and Onak(FOCS2011).

**comment:**

APPROX-RANDOM 2013: 42-57

Fetch PDF file of the paper

Back to Publications List |