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

Vladimir Braverman, Jonathan Katzman, Charles Seidell +1

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 freq…