Approximating Large Frequency Moments with $O(n^{1-2/k})$ Bits

Abstract

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

References in corpus (3)

• Recursive Sketching For Frequency Moments
• A Lower Bound for Estimating High Moments of a Data Stream
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information

Cited by in corpus (1)

• Universal sketches for the frequency negative moments and other decreasing streaming sums