REVIEW 4 major objections 3 minor 22 references
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
T0 review · 4 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read Sliding-window $F_p$ moment estimation is settled up to $\log\log n$ and $\log(1/\varepsilon)$ factors, with heavy hitters following as a consequence.
desk verdict Strong new upper-bound technique for sliding-window F_p estimation, but the stated lower bound is false as written and the main algorithm mixes ℓ_p and F_p estimates. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the Strong Estimator (Definition 2.2): a p-stable random matrix whose median-of-absolute-entries estimate $f_p(x_{(a,b)})$ is guaranteed, with probability $1-\delta$, to be within $(1\pm\epsilon_1)\ell_{p}^{(a,b)}\pm\epsilon_2 \ell_p^{(l,r)}$ for every sub-window $[a,b]$ of a window $[l,r]$ simultaneously. This simultaneity is what eliminates the union bound over sketches that had cost previous sliding-window algorithms a $\log n$ factor. The second mechanism is the Difference Estimator of [WZ22], which estimates $F_p(u+v)-F_p(v)$ additively so that StitchSW can subtract the contribution lying outside the query window; the third is a recursive randomized rounding scheme from [JW23] that compresses each sketch entry to few bits; and the fourth is a 'rotating random sets' queue that bounds the number of active timestamps without a global union bound.
What would settle it
Set $p=2$ and take the query window $W$ to contain a single distinct item once, so $F_2^W=1$. Let the stream before the window contain many copies of another item, so the suffix from the first retained timestamp has a much larger $F_2$ value. Interpret the base sketch output $X$ literally as the $\ell_2$-norm estimate the pseudocode defines; then $Z=X-\sum_j Y_j$ is an $\ell_2$-norm quantity minus $F_2$-difference estimates, which will not be close to $1$. Running Algorithm 2 on this small stream and inspecting $Z$ decides whether the proof's unstated replacement of an $\ell_2$ estimate by an $F_2$ estimate is merely notational.
Extended reading notes
Core claim
In the authors' own terms, the central result is Theorem 4.14: for $p\in[1,2]$, for any fixed window $W$, with probability at least $2/3$, Algorithm 2 returns an $\varepsilon$-approximation of $F_p^W$ using $O((\varepsilon^{-p}\log^2 n + \varepsilon^{-2}\log n\log^4(1/\varepsilon))(\log(1/\varepsilon)+(\log\log n)^2)) = \tilde O(\varepsilon^{-p}\log^2 n+\varepsilon^{-2}\log n)$ bits. Theorem 1.3 complements this with a lower bound of $\Omega(\varepsilon^{-p}\log^2(\varepsilon U)+\varepsilon^{-2}\log(\varepsilon^{1/p}U))$, so the algorithm is tight up to $\log\log n$ and $\log(1/\varepsilon)$ factors. The same $F_2$ estimator, combined with the heavy-hitter reduction of a prior work, yields an $O(\varepsilon^{-p}\log^2 n(\log(1/\varepsilon)+\log\log n))$-bit algorithm for $\ell_p$ heavy-hitters on an arbitrary window (Theorem 1.2).
Load-bearing premise
The argument assumes the sketch output used as the base of the stitching procedure approximates the $p$-th frequency moment $F_p$ (the sum of $p$-th powers of frequencies), while the pseudocode defines that same output as an approximation of the $\ell_p$ norm (the $p$-th root of that sum); the proof silently switches between the two.
Editorial extensions
If this is right
- For $1<p\le 2$, $F_p$ moment estimation on any fixed sliding window now requires only $\tilde O(\varepsilon^{-p}\log^2 n+\varepsilon^{-2}\log n)$ bits, matching the $\Omega(\varepsilon^{-p}\log^2 n)$ lower bound up to $\log\log n$ and $\log(1/\varepsilon)$ factors.
- The $\ell_p$ heavy-hitters problem on an arbitrary window can be solved in $O(\varepsilon^{-p}\log^2 n(\log(1/\varepsilon)+\log\log n))$ bits, closing the $\log n$ gap between the previous upper bound and the known lower bound.
- Because the algorithm runs in the more general model where the window length $n$ is supplied at query time, the same bounds cover queries such as 'the past hour, day, or week'.
- Running $O(\log m)$ independent copies and taking a median converts the per-query $2/3$ success guarantee into a guarantee for all times, at an extra $O(\log m)$ factor.
Reading between the lines
- The same stitching architecture—a strong per-sub-window estimator plus difference estimators subtracted at multiple resolutions—may transfer to other sliding-window statistics that admit difference estimators, such as distinct elements or entropy-like measures, potentially carrying the same near-tight space bounds.
- The lower bound works by forcing the algorithm to remember the locations of $\Omega(\varepsilon^{-p}\log n)$ mini-blocks, each costing $\log n$ bits; a plausible testable extension is whether the remaining $\log\log n$ and $\log(1/\varepsilon)$ gaps disappear under a stronger communication game or a refined rounding analysis.
- The rotating-random-sets technique, which reuses independent sketch matrices through a queue to bound the number of live timestamps without a global union bound, is a general device and could reduce logarithmic factors in other histogram-based sliding-window algorithms.
- If the mismatch between the $\ell_p$-norm estimate and the $F_p$-moment estimate in StitchSW is only notational and the intended value is the $p$-th power of the sketch output, then the space analysis is unchanged but the correctness proof needs a small correction; if the mismatch is real, the $F_p$ guarantee as written would fail on simple streams.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the sliding-window model for insertion-only streams and gives new bounds for two problems: F_p moment estimation (1 < p ≤ 2) and ℓ_p heavy hitters (0 < p ≤ 2). The main algorithmic contribution is an F_p moment estimation algorithm with space Õ(ε^{-p} log^2 n + ε^{-2} log n) bits for any fixed window, improving on the previous Õ(ε^{-2} log^3 n) bound. The main theoretical tool is a 'Strong Estimator' that gives uniform accuracy guarantees over all sub-windows, thereby avoiding the union-bound overhead that caused an extra logarithmic factor in prior work. The authors also claim a lower bound Ω(ε^{-p} log^2 n + ε^{-2} log n) for F_p estimation, up to log log n and log(1/ε) factors, via a reduction from an IndexGreater communication game. Finally, they combine their F_2 estimator with known heavy-hitters reductions to obtain a near-optimal ℓ_p heavy-hitters algorithm on sliding windows.
Significance. If the technical issues are repaired, the paper's results are significant: they close a logarithmic gap in sliding-window F_p moment estimation, introduce a reusable Strong Estimator concept, and give the first near-tight heavy-hitters algorithm in this model. The paper is unusually complete in its appendix proofs and carefully separates single-query guarantees from all-times tracking. The claimed space bounds depend on known prior work (WZ22, JW23, BGL+18, BDN17) used as black boxes, but the new tools—Strong Estimator, rotating random sets, and the windowed rounding procedures—are the paper's own contributions. The lower-bound reduction is a clean application of a standard communication game and, once the statement is corrected, should provide a useful template for future sliding-window lower bounds.
major comments (4)
- [Sec. 4.4, StitchSW and Lemma 4.22] Algorithm 2's StitchSW function sets X ← g(t1,t), where g is defined in Algorithm 1 as the Indyk p-stable sketch's estimate of the ℓ_p norm ‖x(t1,t)‖_p, while each Y_j is a sum of difference estimators that estimate F_p moments (additive approximations to F_p(t1,j,k-1,t) − F_p(t1,j,k,t)). The output Z = X − Σ_j Y_j therefore mixes ℓ_p and F_p quantities, and the proof of Lemma 4.22 silently treats X as an estimate of the F_p moment of the prefix u. This is a load-bearing inconsistency in the central upper-bound theorem (Theorem 4.14). The fix is straightforward—define X as (g(t1,t))^p, or equivalently redefine g to output the F_p moment—and the constants in the analysis would need to be adjusted accordingly, but as written the algorithm and its correctness proof do not match.
- [Theorem 1.3 and Theorem 5.4] The 'in particular' lower bound Ω(ε^{-p} log^2(ε U) + ε^{-2} log(ε^{1/p} U)) for n ≥ U is internally inconsistent with the trivial exact algorithm that stores the current window (O(n log U) bits). Taking p=2, U=n, and ε=n^{-1/2} gives the claimed bound Ω(n log^2 n), which exceeds O(n log n) by a log n factor. The reduction in the proof supports only the weaker expression with log^2(ε U^{1/p}) (or, with the parameter choices in Lemma 5.3, k r log N = Θ(n (ε n^{1/p})^{-(p+1)/2} log(ε n^{1/p}))), so the theorem statement as written is false. The statement needs to be corrected to match the proof, and the apparent contradiction with the trivial upper bound should be resolved explicitly.
- [Sec. 3.2, proof of Theorem 3.6] The proof states: 'We use Algorithm 1 to obtain a 1/2 approximation over ℓ^W_p, the rest of the proof follows by Lemma 2.5 and Lemma 2.6.' Lemma 2.5 requires a constant-factor approximation of the ℓ_2 norm within the window, not the ℓ_p norm. To make the argument valid, one must run Algorithm 1 with parameter p=2 to obtain an ℓ_2 approximation (which costs O(log^2 n) bits for constant accuracy), then invoke Lemma 2.5 with accuracy parameter ε^{p/2} before applying Lemma 2.6. As written, the cited lemmas do not combine to give the claimed conclusion for general p.
- [Sec. 4.3, proof of Lemma 4.13] The proof of the rounding-error bound for the Difference Estimator uses the inequality Π_{j=q(i−1)+1}^{qi}(|(Av)_j| + ε′‖v‖_p)^{p/q} ≤ Π_j |(Av)_j|^{p/q} + (ε′‖v‖_p)^{p/q}. This inequality does not follow from the stated bound |(Av)_j| ≤ λ‖v‖_p: expanding the product produces cross terms of the form (ε′‖v‖_p)^{c}(product of original entries)^{p/q−c}, and the assumption ε′ < 1/λ^2 does not by itself control these terms. Since Lemma 4.13 is used to justify the compressed storage of the Difference Estimators, the proof needs a more careful expansion or a different bound before the space claim in Lemma 4.23 is established.
minor comments (3)
- [Sec. 4.3, Lemma 4.13 statement] The phrase 'u, v be 2 frequent vector' should be corrected to 'two frequency vectors'.
- [Sec. 1.1 and Sec. 4.4] The window is defined as [t−n+1, t] in Section 1.1, but Lemma 4.15 and Theorem 4.14 use W = [r−n, r]; the off-by-one convention should be made consistent throughout.
- [Sec. 4.4, Lemma 4.15 proof] The proof writes that the algorithm uses an (ε^p/64, ε^p/64, δSE) Strong Estimator 'for ε = 1/2'; the top-level partition uses the parameter ε0 = 1/2, so the notation should be clarified to avoid confusion with the final approximation parameter ε.
Circularity Check
Upper-bound timestamp count is proven by an event whose own probability proof assumes that count.
-
other
[Section 4.4, Lemma 4.11 proof, Lemma 4.20, Lemma 4.19, and Lemma 4.22 proof]
"Suppose there are s timestamps on the top level. From Lemma 4.20, there are at most 2^{j+23}·s = C′·2^j log n good sketches on level j. Choosing C > 2C′, we can infer that qj will not be empty."
Lemma 4.20 is stated conditionally: 'conditioned on the Geometric Lower bounds on splitting times to hold (Lemma 4.19), we have ... k≤2^{j+23}'. Lemma 4.19 is in turn stated as 'conditioned on E', where E is defined in Lemma 4.22's proof as the event that 'all the O(ε^{-p} log n) instances of Strong Estimator satisfy' the required property on window W′. The proof of E then union-bounds over exactly those O(ε^{-p} log n) instances, which is precisely the instance count that Lemma 4.11 is meant to establish. Thus the active-timestamp bound used in Lemma 4.23 and Theorem 4.14 is fed into its own proof via E: the number of instances is assumed in order to prove the number of instances. This makes the space-bound derivation self-referential rather than self-contained.
full rationale
The clearest circular step is in the upper-bound timestamp-counting argument: Lemma 4.11 derives the O(2^j log n) active-timestamp bound from Lemma 4.20, Lemma 4.20 is conditioned on Lemma 4.19, Lemma 4.19 is conditioned on the event E, and the probability bound for E union-bounds over 'all the O(ε^{-p} log n) instances'—the very quantity Lemma 4.11 is proving. The space bound of Theorem 4.14 therefore rests on a self-referential instance count. This is a genuine circularity in the proof as written, even though the underlying algorithmic idea may be repairable with a more careful induction or a different accounting of the random matrices. The paper otherwise relies on prior work (WZ22, JW23, BGL+18, BDN17) as external black-box theorems, including several coauthored papers; that reliance is not itself circular because the cited lemmas have stated assumptions that do not include the target result and are used as components rather than as the source of the final bound. I additionally flag two non-circular correctness concerns that I do not count in the score: first, Algorithm 2's StitchSW sets X to g(t1,t), where g is defined in Algorithm 1 as an estimate of ||x||_p, while the Y_j terms are F_p-difference estimates, so the subtraction Z = X − ΣY_j is dimensionally inconsistent unless g is silently reinterpreted as an F_p estimate; the proof of Lemma 4.22 does not bridge this gap. Second, the lower-bound parameterization in Theorem 5.4 appears to produce bounds that can exceed the information content of the stream, which would contradict the trivial exact O(n log U)-bit algorithm; this is an information-theoretic/correctness issue, not a circular derivation. For the circularity score, the found step is partial but load-bearing because it is used to justify the claimed space complexity, so I assign 6 rather than a lower score.
Assumptions & free parameters
assumptions (7)
- standard math p-stable distributions exist and can be generated with bounded precision (Definitions 2.1 and Lemma 3.3).
- standard math Lemma 2.3 Chernoff-type concentration bound for k-wise independent random variables [BR94].
- domain assumption Lemma 2.4 tail bound on the supremum of inner products between a p-stable random vector and a growing frequency vector [BDN17].
- domain assumption Difference Estimator construction and error guarantees from [WZ22] (Lemma 4.2).
- domain assumption Recursive randomized rounding guarantees from [JW23] (Lemmas 4.5 and 4.7).
- domain assumption Heavy-hitter reductions from [BGL+18] Lemma 2.5 and [JST11] Lemma 2.6.
- domain assumption Insertion-only F_p moment estimation lower bound from [BZ24], Theorem 11.
Cite this review
Pith. "Pith review of Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model." pith.science (2026). https://pith.science/paper/KPSPZCQS
@misc{pith2026250421175,
author = {Pith},
title = {Pith review of: Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model},
year = {2026},
howpublished = {\url{https://pith.science/paper/KPSPZCQS}},
note = {Machine review of arXiv:2504.21175}
}
abstract
We consider the heavy-hitters and $F_p$ moment estimation problems in the sliding window model. For $F_p$ moment estimation with $1<p\leq 2$, we show that it is possible to give a $(1\pm \epsilon)$ multiplicative approximation to the $F_p$ moment with $2/3$ probability on any given window of size $n$ using $\tilde{O}(\frac{1}{\epsilon^p}\log^2 n + \frac{1}{\epsilon^2}\log n)$ bits of space. We complement this result with a lower bound showing that our algorithm gives tight bounds up to factors of $\log\log n$ and $\log\frac{1}{\epsilon}.$ As a consequence of our $F_2$ moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using $O(\frac{1}{\epsilon^2}\log^2 n)$ space which is tight.
Reference graph
Works this paper leans on
-
[1]
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 20--29, 1996
1996
-
[2]
Bptree: An _2 heavy hitters algorithm using constant memory
Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P Woodruff. Bptree: An _2 heavy hitters algorithm using constant memory. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages 361--376, 2017
work page 2017
-
[3]
Continuous monitoring of _p norms in data streams
Jaros aw B asiok, Jian Ding, and Jelani Nelson. Continuous monitoring of _p norms in data streams. arXiv preprint arXiv:1704.06710 , 2017
arXiv 2017
-
[4]
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. arXiv preprint arXiv:1805.00212 , 2018
work page Pith review arXiv 2018
-
[5]
Smooth histograms for sliding windows
Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages 283--293, 2007
work page 2007
-
[6]
Smooth histograms for sliding windows
Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages 283--293. IEEE, 2007
work page 2007
-
[7]
Effective computations on sliding windows
Vladimir Braverman and Rafail Ostrovsky. Effective computations on sliding windows. SIAM Journal on Computing , 39(6):2113--2131, 2010
work page 2010
-
[8]
Randomness-efficient oblivious sampling
Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In Proceedings 35th Annual Symposium on Foundations of Computer Science , pages 276--287. IEEE, 1994
work page 1994
Show all 22 references
-
[9]
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences , 68(4):702--732, 2004
2004
-
[10]
Optimality of frequency moment estimation
Mark Braverman and Or Zamir. Optimality of frequency moment estimation. arXiv preprint arXiv:2411.02148 , 2024
2024 arXiv
-
[11]
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming , pages 693--703. Springer, 2002
2002
-
[12]
Maintaining stream statistics over sliding windows
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM journal on computing , 31(6):1794--1813, 2002
2002
-
[13]
Frequency estimation of internet packet streams with limited space
Erik D Demaine, Alejandro L \'o pez-Ortiz, and J Ian Munro. Frequency estimation of internet packet streams with limited space. In European Symposium on Algorithms , pages 348--360. Springer, 2002
2002
-
[14]
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM) , 53(3):307--323, 2006
2006
-
[15]
Optimal approximations of the frequency moments of data streams
Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing , pages 202--208, 2005
2005
-
[16]
Tight bounds for L_p samplers, finding duplicates in streams, and related problems
Hossein Jowhari, Mert Sa g lam, and G\' a bor Tardos. Tight bounds for L_p samplers, finding duplicates in streams, and related problems. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS '11, pages 49--58, New York, NY...
2011
-
[17]
Woodruff
Rajesh Jayaram and David P. Woodruff. Towards optimal moment estimation in streaming and distributed models. ACM Trans. Algorithms , 19(3), June 2023
2023
-
[18]
On the exact space complexity of sketching and streaming small norms
Daniel M Kane, Jelani Nelson, and David P Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages 1161--1178. SIAM, 2010
2010
-
[19]
James L. Jr. Nolan. Stable distributions. models for heavy tailed data. 2001
2001
-
[20]
Analyzing peer-to-peer traffic across large networks
Subhabrata Sen and Jia Wang. Analyzing peer-to-peer traffic across large networks. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment , pages 137--150, 2002
2002
-
[21]
Tight bounds for adversarially robust streams and sliding windows via difference estimators
David P Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1183--1196. IEEE, 2022
2021
-
[22]
One-dimensional stable distributions , volume 65
Vladimir M Zolotarev. One-dimensional stable distributions , volume 65. American Mathematical Soc., 1986
1986
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.