Universal Perfect Samplers for Incremental Streams

Seth Pettie, Dingyu Wang

If $G:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+}$, the $G$-moment of a vector $\mathbf{x}\in {\mathbb{R}}_{+}^n$ is $G(\mathbf{x})={\sum }_{v\in [n]}G(\mathbf{x}(v))$ and the $G$-sampling problem i…