Approximating Large Frequency Moments with O(n 1-2/k ) Bits.

摘要: In this paper we consider the problem of approximating frequency moments in streaming model. Given a stream $D = \{p_1,p_2,\dots,p_m\}$ numbers from $\{1,\dots, n\}$, $i$ is defined as $f_i |\{j: p_j i\}|$. The $k$-th \emph{frequency moment} $D$ $F_k \sum_{i=1}^n f_i^k$. In give an upper bound on space required to find moment $O(n^{1-2/k})$ bits that matches, up constant factor, lower Woodruff and Zhang (STOC 12) for $\epsilon$ $k$. Our algorithm makes single pass over works any $k > 3$.