High Probability Frequency Moment Sketches

Sumit Ganguly, David P. Woodruff

We consider the problem of sketching the $p$-th frequency moment of a vector, $p>2$, with multiplicative error at most $1\pm \epsilon$ and \emph{with high confidence} $1-\delta$. Despite the l…