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=1)~n f_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 Ω(1/n~(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 ∈, 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).
展开▼
