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.00072660894 |
| 4,950 | Optimal Bounds for Approximate Counting | 2022 | PODS | 5.808904e-05 |
| 6,347 | BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory | 2017 | PODS | 5.0969206e-05 |
| 10,905 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,146 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS | 4.8133378e-05 |
| 11,863 | Range Thresholding on Streams | 2016 | SIGMOD | 4.1905499e-05 |
| 4,246 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS | 6.318484e-05 |
| 11,443 | Frequent Elements with Witnesses in Data Streams | 2021 | PODS | 4.1905499e-05 |
| 11,323 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1905499e-05 |
| 1,744 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00010694459 |
| 3,701 | Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams | 2005 | PODS | 6.825442e-05 |
| 6,347 | BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory | 2017 | PODS | 5.0969206e-05 |
| 6,415 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.064828e-05 |
| 10,905 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1905499e-05 |