Fast method improves sampling from data streamed in real time
Fast Perfect $L_2$ Sampling
Data Structures and Algorithms
Summary
Selecting items from a large list based on how often they appear is useful for many computer tasks, but doing this quickly and perfectly is hard. The authors solved a puzzle about how to pick items with probability proportional to the square of their frequency using very little memory and very fast updates. Their new technique makes these perfect picks in a way that uses only a small amount of space and can update quickly as new data arrives. This breakthrough opens the door for more efficient data analysis in environments where data is changing rapidly.
What this means in practice
- •For database engineers: Implement fast, memory-efficient algorithms for estimating dynamic join sizes in streaming databases for query optimization.
- •For network monitoring teams: Enable real-time detection of heavy-hitter patterns from evolving data streams with very low memory and quick updates.
Authors
David P. Woodruff, Samson Zhou
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 $\text{polylog}(n)$ update time while maintaining an optimal $\tilde{\mathcal{O}}(\log^3 n)$ bits of space.