Truly Perfect Samplers for Data Streams and Sliding Windows

Abstract

In the $G$-sampling problem, the goal is to output an index $i$ of a vector $f\in {\mathbb{R}}^n$, such that for all coordinates $j\in [n]$, \[\textbf{Pr}[i=j] = (1 \pm ε) \frac{G(f_j)}{\sum_{k\in[n]} G(f_k)} + γ,\] where $G:\mathbb{R}\to {\mathbb{R}}_{\ge 0}$ is some non-negative function. If $\epsilon =0$ and $\gamma =1/\text{poly}(n)$, the sampler is called perfect. In the data stream model, $f$ is defined implicitly by a sequence of updates to its coordinates, and the goal is to design such a sampler in small space. Jayaram and Woodruff (FOCS 2018) gave the first perfect $L_p$ samplers in turnstile streams, where $G(x)=|x{|}^p$, using $\text{polylog}(n)$ space for $p\in (0,2]$. However, to date all known sampling algorithms are not truly perfect, since their output distribution is only point-wise $\gamma =1/\text{poly}(n)$ close to the true distribution. This small error can be significant when samplers are run many times on successive portions of a stream, and leak potentially sensitive information about the data stream. In this work, we initiate the study of truly perfect samplers, with $\epsilon =\gamma =0$, and comprehensively investigate their complexity in the data stream and sliding window models. Abstract truncated due to arXiv limits; please see paper for full abstract.