Finding Heavy-Hitters with Optimal State Changes
Summary: Streaming algorithm for ε-ℓ_k heavy-hitters with drastically reduced state-change complexity: O(ε^{-1} n^{1-1/k} · poly(log log n) · log(1/ε)) state changes and O(1/ε^k · polylog n) space for k∈[1,2] (extension to k≥2 incurs n^{1-2/k} extra space). Shows a matching lower bound up to log log n factors and credits the improvement to a new, very simple insertion-only heavy-hitters subroutine. (summarized by gpt-5-mini on Feb 11 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 43 | Models and Issues in Data Stream Systems | 2002 | PODS | 0.00072723062 |
| 2,884 | BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory | 2017 | PODS | 7.9620506e-05 |
| 5,550 | Optimal Bounds for Approximate Counting | 2022 | PODS | 5.4422275e-05 |
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,145 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS | 4.8179617e-05 |
| 4,249 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS | 6.3245666e-05 |
| 11,855 | Range Thresholding on Streams | 2016 | SIGMOD | 4.1945683e-05 |
| 11,440 | Frequent Elements with Witnesses in Data Streams | 2021 | PODS | 4.1945683e-05 |
| 11,321 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1945683e-05 |
| 1,629 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00011085267 |
| 3,660 | Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams | 2005 | PODS | 6.8691367e-05 |
| 2,884 | BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory | 2017 | PODS | 7.9620506e-05 |
| 6,418 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.0696932e-05 |
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |