Pith. sign in

REVIEW 31 references

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Near-optimal one- and two-round protocols for ℓp heavy hitters and Fp estimation in the coordinator and distributed tracking models, including the first near-optimal algorithms for tracking Fp.

arxiv 2505.14250 v1 pith:MKQZOAJH submitted 2025-05-20 cs.DS

Zengfeng Huang , Zhongzheng Xiong , Xiaoyi Zhu , Zhewei Wei This is my paper · ORCID
classification cs.DS
keywords algorithmdistributedmodelheavyhitterscommunicationfirstnear-optimal
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Many modern data systems collect information across thousands of machines, and the central question is how many bits the machines must send to a coordinator to answer basic statistical questions. This paper studies two classic tasks: finding heavy hitters (items whose total count is large) and estimating frequency moments (sums of counts raised to a power p, with p greater than or equal to 2). Two settings are considered: a static coordinator model where each machine holds a fixed dataset, and a dynamic tracking model where data keeps arriving and the coordinator must maintain an answer at all times.

The algorithms are built on a simple sampling idea. Each machine sends a data point with probability proportional to the square of its local frequency, which gives an unbiased estimate of each global frequency with a small variance. Because the sampling probability is quadratic, adapting it to the dynamic setting is nontrivial; the authors replace it with a piecewise linear approximation and split time into phases and intervals with fresh random thresholds. A second contribution is a relaxed notion of weak cover that lets the standard recursive sketching technique be tracked in a communication-efficient way. The communication costs match known lower bounds up to logarithmic factors, and for tracking Fp even for p equals 2, no previous algorithm was close to optimal.

Extended reading notes

Core claim

The abstract states: 'we provide the first near-optimal algorithm for Fp in the distributed tracking model, with a communication cost of O~(k^{p-1}/ε^2) for all p≥2.' If the paper is correct, tracking Fp (including F2) is solved up to logarithmic factors, and one-round coordinator heavy hitters for p>2 are also optimal up to logs.

Load-bearing premise

The Fp tracking result relies on the exact thresholded sum tracking algorithm of Cormode et al. [10] (used in Algorithm 9) achieving O~(k) communication per instance while following a moving threshold over time. The paper does not re-derive this bound; any hidden assumption in [10] about the form of the threshold function or about monotonic streams would invalidate the O~(k^{p-1}/ε^2) tracking bound.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's upper bounds are derived from first principles via standard inequalities; the only inputs are standard model assumptions and black-box prior results. No free parameters are fitted, and no new entities (particles, forces, dimensions) are introduced. The central claims are therefore not circular.

assumptions (5)
  • domain assumption m = poly(n) (equivalently log m = O(log n))
    Stated in Section 2; used to bound the number of tracking rounds and the number of guesses in one-round protocols by O(log n).
  • domain assumption Public randomness is available to all sites and the coordinator.
    Used in recursive sketching (random binary vectors) and in thresholded sampling (Algorithms 4 and 9). Standard model assumption in distributed streaming.
  • domain assumption Recursive sketching theorem (Theorem 1) from Braverman et al. [5] is correct.
    Used as a black box to reduce Fp estimation to computing (α,ε)-covers; the paper relies on the proof structure to justify the weak-cover relaxation.
  • domain assumption Exact thresholded sum tracking from Cormode et al. [10] achieves O~(k) communication.
    Used in Algorithm 9 to detect threshold crossings of v_j(t); the Fp tracking communication bound depends on this cost.
  • domain assumption The lower bounds in Woodruff-Zhang [25] and Esfandiari et al. [14] are valid.
    Used only to claim near-optimality; not needed for the correctness of the proposed algorithms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models." pith.science (2026). https://pith.science/paper/MKQZOAJH

@misc{pith2026250514250,
  author       = {Pith},
  title        = {Pith review of: Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MKQZOAJH}},
  note         = {Machine review of arXiv:2505.14250}
}
abstract

We consider the problems of distributed heavy hitters and frequency moments in both the coordinator model and the distributed tracking model (also known as the distributed functional monitoring model). We present simple and optimal (up to logarithmic factors) algorithms for $\ell_p$ heavy hitters and $F_p$ estimation ($p \geq 2$) in these distributed models. For $\ell_p$ heavy hitters in the coordinator model, our algorithm requires only one round and uses $\tilde{O}(k^{p-1}/\eps^p)$ bits of communication. For $p > 2$, this is the first near-optimal result. By combining our algorithm with the standard recursive sketching technique, we obtain a near-optimal two-round algorithm for $F_p$ in the coordinator model, matching a significant result from recent work by Esfandiari et al.\ (STOC 2024). Our algorithm and analysis are much simpler and have better costs with respect to logarithmic factors. Furthermore, our technique provides a one-round algorithm for $F_p$, which is a significant improvement over a result of Woodruff and Zhang (STOC 2012). Thanks to the simplicity of our heavy hitter algorithms, we manage to adapt them to the distributed tracking model with only a $\polylog(n)$ increase in communication. For $\ell_p$ heavy hitters, our algorithm has a communication cost of $\tilde{O}(k^{p-1}/\eps^p)$, representing the first near-optimal algorithm for all $p \geq 2$. By applying the recursive sketching technique, we also provide the first near-optimal algorithm for $F_p$ in the distributed tracking model, with a communication cost of $\tilde{O}(k^{p-1}/\eps^2)$ for all $p \geq 2$. Even for $F_2$, our result improves upon the bounds established by Cormode, Muthukrishnan, and Yi (SODA 2008) and Woodruff and Zhang (STOC 2012), nearly matching the existing lower bound for the first time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    N. Alon, Y . Matias, and M. Szegedy. The space complexity of approximating the frequency moments. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20–29, 1996

    work page 1996

  2. [2]

    Arackaparambil, J

    C. Arackaparambil, J. Brody, and A. Chakrabarti. Functional monitoring without monotonicity. In Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I 36, pages 95–106. Springer, 2009

    work page 2009

  3. [3]

    Assadi, G

    S. Assadi, G. Kol, and Z. Zhang. Rounds vs communication tradeoffs for maximal independent sets. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1193–1204. IEEE, 2022

    work page 2022

  4. [4]

    Braverman and R

    M. Braverman and R. Oshman. A rounds vs. communication tradeoff for multi-party set disjointness. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 144–155. IEEE, 2017

    work page 2017

  5. [5]

    Braverman and R

    V . Braverman and R. Ostrovsky. Generalizing the layering method of indyk and woodruff: Recur- sive sketches for frequency-based vectors on streams. InInternational Workshop on Approximation Algorithms for Combinatorial Optimization, pages 58–70. Springer, 2013

    work page 2013

  6. [6]

    Chandramouli, S

    B. Chandramouli, S. Nath, and W. Zhou. Supporting distributed feed-following apps over edge devices. Proceedings of the VLDB Endowment, 6(13):1570–1581, 2013

    work page 2013

  7. [7]

    Charikar, K

    M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. InInternational Colloquium on Automata, Languages, and Programming, pages 693–703. Springer, 2002

    work page 2002

  8. [8]

    Chen and Q

    J. Chen and Q. Zhang. Improved algorithms for distributed entropy monitoring.Algorithmica, 78:1041– 1066, 2017

    work page 2017

Show all 31 references
  1. [9]

    Cormode, M

    G. Cormode, M. Garofalakis, S. Muthukrishnan, and R. Rastogi. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. InProceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 25–36, 2005

    2005

  2. [10]

    Cormode, S

    G. Cormode, S. Muthukrishnan, and K. Yi. Algorithms for distributed functional monitoring. In19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1076–1085, 2008

    2008

  3. [11]

    Cormode, S

    G. Cormode, S. Muthukrishnan, K. Yi, and Q. Zhang. Continuous sampling from distributed streams. Journal of the ACM (JACM), 59(2):1–25, 2012

    2012

  4. [12]

    Dilman and D

    M. Dilman and D. Raz. Efficient reactive monitoring. InProceedings IEEE INFOCOM 2001., volume 2, pages 1012–1019. IEEE, 2001

    2001

  5. [13]

    Dolev and T

    D. Dolev and T. Feder. Multiparty communication complexity. In30th Annual Symposium on Founda- tions of Computer Science, pages 428–433. IEEE, 1989

    1989

  6. [14]

    Esfandiari, P

    H. Esfandiari, P. Kacham, V . Mirrokni, D. P. Woodruff, and P. Zhong. Optimal communication for classic functions in the coordinator model and beyond.arXiv preprint arXiv:2403.20307, 2024

    2024 arXiv

  7. [15]

    Huang, X

    Z. Huang, X. Lin, W. Zhang, and Y . Zhang. Communication-efficient distributed covariance sketch, with application to distributed pca.Journal of Machine Learning Research, 22(80):1–38, 2021. 16

    2021

  8. [16]

    Huang and K

    Z. Huang and K. Yi. The communication complexity of distributed epsilon-approximations.SIAM Journal on Computing, 46(4):1370–1394, 2017

    2017

  9. [17]

    Huang, K

    Z. Huang, K. Yi, and Q. Zhang. Randomized algorithms for tracking distributed count, frequencies, and ranks. InProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 295–306, 2012

    2012

  10. [18]

    Indyk and D

    P. Indyk and D. 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

  11. [19]

    Keralapura, G

    R. Keralapura, G. Cormode, and J. Ramamirtham. Communication-efficient distributed monitoring of thresholded counts. InProceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 289–300, 2006

    2006

  12. [20]

    S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tinydb: an acquisitional query processing system for sensor networks.ACM Transactions on database systems (TODS), 30(1):122–173, 2005

    2005

  13. [21]

    J. M. Phillips, E. Verbin, and Q. Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. InProceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 486–501. SIAM, 2012

    2012

  14. [22]

    Schiller and A

    J. Schiller and A. V oisard.Location-based services. Elsevier, 2004

    2004

  15. [23]

    Tirthapura and D

    S. Tirthapura and D. P. Woodruff. Optimal random sampling from distributed streams revisited. In Distributed Computing: 25th International Symposium, DISC 2011, Rome, Italy, September 20-22,

    2011

  16. [24]

    E. Viola. The communication complexity of addition.Combinatorica, 35:703–747, 2015

    2015

  17. [25]

    D. P. Woodruff and Q. Zhang. Tight bounds for distributed functional monitoring. InProceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 941–960, 2012

    2012

  18. [26]

    D. P. Woodruff and Q. Zhang. When distributed computation does not help.CoRR, abs/1304.4636, 5, 2013

    2013 arXiv

  19. [27]

    D. P. Woodruff and Q. Zhang. An optimal lower bound for distinct elements in the message passing model. InProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 718–733. SIAM, 2014

    2014

  20. [28]

    H. Wu, J. Gan, and R. Zhang. Learning based distributed tracking. InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2040–2050, 2020

    2020

  21. [29]

    Xiong, X

    Z. Xiong, X. Zhu, and Z. Huang. Adversarially robust distributed count tracking via partial differential privacy.Advances in Neural Information Processing Systems, 36, 2024

    2024

  22. [30]

    X i=k vij pij ·1(Siteisendsv ij) # = X i=k vij pij ·E[1(Siteisendsv ij)] = kX i=1 vij =v j. Next, we bound the variance ofˆvj. Var[ˆvj] =Var

    K. Yi and Q. Zhang. Optimal tracking of distributed heavy hitters and quantiles. InProceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 167–174, 2009. 17 A Appendix for Section 3 Proof of Theorem 2.Fix somej∈[n]. Firstly,...

    2009

  23. [2011]

    Springer, 2011

    Proceedings 25, pages 283–297. Springer, 2011

    2011

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.