Approximating Large Frequency Moments with Pick-and-Drop Sampling

摘要

Given data stream D = {p_1,P_2,…, P_m } of size m of numbers from {1,..., n}, the frequency of i is defined as f_i = |{j : p_j = i}|. The k-th frequency moment of D is defined as F_k = Σ_i~n=_1f_i~k.We consider the problem of approximating frequency moments in insertion-only streams for k ≥ 3. For any constant c we show an O(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 method a pick-and-drop sampling; it samples a heavy element (i.e., element i with frequency Ω(F_k)) with probability Ω(l~(1-2/k)) and gives approximation f_i ≥ (1 — ε)f_i. In addition, the estimations never exceed the real values, that is f_j ≤ f_j for all j. For constant e, we reduce the space complexity of finding a heavy element to O(n~(1-2/k) log(n)) bits. We apply our method of recursive sketches and resolve the problem with O(n~(1-2/k) log(n) log~((c))(n)) bits. We reduce the ratio between the upper and lower bounds from O(log~2(n)) to O(log(n) log~((c)) (n)). Thus, we provide a (roughly) quadratic improvement of the result of Andoni, Krauthgamer and Onak (FOCS 2011).