pipette
ESEspañol

Fast Perfect Sampling

David P. Woodruff, Samson Zhou

Preprint

In the authors' words

Perfect sampling is a powerful primitive for turnstile data streams, allowing algorithms to extract an index with probability proportional to its squared frequency, with applications to dynamic join size estimation, query optimization, heavy-hitters, sampling from self-joins, and real-time monitoring of evolving datasets. The setting is also the largest for which sampling can be achieved in polylogarithmic space. However, existing space-optimal perfect samplers rely on explicit polynomial duplication, requiring inefficient polynomial update times per stream arrival. Resolving a open question left by Swartworth, Woodruff, and Zhou [FOCS 2025], we present a perfect sampler that achieves an expected update time while maintaining an optimal bits of space.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: PODS 2027