# Truly Perfect Samplers for Data Streams and Sliding Windows

arXiv: https://arxiv.org/abs/2108.12017 · HTML: https://mlsanity.com/paper/2108.12017/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2021.

## Built on by (most cited first, 5 of 5)

- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Adaptive Sketches for Robust Regression with Importance Sampling](https://mlsanity.com/paper/2207.07822/) (2022)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)

## Abstract (arXiv)

In the G-sampling problem, the goal is to output an index i of a vector f ∈ℝn, such that for all coordinates j ∈ [n], [Pr[i=j] = (1 ± ε) fracG(fj)sumk∈[n] G(fk) + γ,] where G:ℝ → ℝ≥ 0 is some non-negative function. If ε = 0 and γ = 1/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 Lp samplers in turnstile streams, where G(x)=|x|p, using polylog(n) space for p∈(0,2]. However, to date all known sampling algorithms are not truly perfect, since their output distribution is only point-wise γ = 1/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 ε = γ = 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.