Approximating Large Frequency Moments with Pick-and-Drop Sampling
Vladimir Braverman, Rafail Ostrovsky
Abstract:
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 Fk = ΣnI = ƒki We consider the problem of approximating frequency moments in insertion -only streams for K≥3. For any constant c we show an Ο(n1-2/klog(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/n1-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 Ο(n1-2/klog(n)log(c))(n)) bits. we apply our method of recursive sketches and resolve the problem with Ο(n1-2/klog(n)log(c))(n)) bits. We reduce the ratio between the upper and lower bounds from Ο(n1-2/klog(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 |