Sketching, Moment Estimation, and the L\'evy-Khintchine Representation
Theorem
Sketching, Moment Estimation, and the L\'evy-Khintchine Representation
Theorem
In the $d$-dimensional turnstile streaming model, a frequency vector $\mathbf{x}=(\mathbf{x}(1),\ldots,\mathbf{x}(n))\in (\mathbb{R}^d)^n$ is updated entry-wisely over a stream. We consider the problem of \emph{$f$-moment estimation} for which one wants to estimate $$f(\mathbf{x})=\sum_{v\in[n]}f(\mathbf{x}(v))$$ with a small-space sketch. In this work we present a simple and generic scheme to construct sketches with the …