Approximating Large Frequency Moments with Pick-and-Drop Sampling

Vladimir Braverman, Rafail Ostrovsky

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 \emph{frequency mome…