A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem

Seth Pettie, Dingyu Wang

In the $d$-dimensional turnstile streaming model, a frequency vector $\mathbf{x}=(\mathbf{x}(1),\dots ,\mathbf{x}(n))\in ({\mathbb{R}}^d{)}^n$ is updated entry-wisely over a stream. We…