Fast Perfect L 2 Sampling

arXiv:2610.38860 · cs.DS · Submitted 2026-10-28 · Read on arXiv

cs.DS

Submitted: 2026-10-28

Updated: 2026-10-28

Comments: PODS 2027

License: http://creativecommons.org/licenses/by/4.0/

The gist: Perfect L 2 sampling is a powerful primitive for turnstile data streams, allowing algorithms to extract an index with probability proportional to its squared frequency…

Abstract

Perfect L 2 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 p=2 is also the largest p for which L p 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 L 2 sampler that achieves an expected polylog(n) update time while maintaining an optimal O tilde(cubed n) bits of space.

Related papers