Streaming space limits clarified for precise frequency moment estimation
High Probability Streaming Lower Bounds for $F_2$ Estimation
Data Structures and Algorithms
Summary
Estimating how often items appear in large data streams is important but challenging with limited memory. The authors found the exact limits of how much memory is needed to approximate a certain measure of frequencies reliably, improving over previous work. They introduced a new way to handle errors in communication between parts of the process, helping them prove their results. They also developed better methods for streams with certain characteristics, like limited item frequencies or few distinct items.
What this means in practice
- •For data stream engineers: Better understand the minimum memory needed for accurate frequency moment tracking in streaming data systems.
- •For network traffic analysts: Use improved bounds to optimize algorithms estimating network flow properties with strict accuracy and failure guarantees.
A theory result. No direct application yet.
Authors
William Swartworth, David P. Woodruff, Samson Zhou
Abstract
Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log(1/δ)$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log(n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log\log m$ dependence on stream length.