BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory
Summary: BPTree: an insertion-only ℓ2 heavy-hitters algorithm using O(ε^-2 log ε^-1) words and O(log ε^-1) update time, i.e., memory independent of n,m and optimal. Also provides O(ε^-2)-space ||f||_2 tracking; analysis via Dudley-style chaining for limited-independence Rademachers. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Vladimir Braverman
- 2. Stephen R. Chestnut
- 3. Nikita Ivkin
- 4. Jelani Nelson
- 5. Zhengyu Wang
- 6. David P. Woodruff
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,403 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2194225e-05 |
| 6,418 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.0696932e-05 |
| 7,145 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS | 4.8179617e-05 |
| 7,496 | Subspace Exploration: Bounds on Projected Frequency Estimation | 2021 | PODS | 4.7180617e-05 |
| 8,203 | SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model | 2022 | VLDB | 4.5596344e-05 |
| 10,005 | Finding Heavy-Hitters with Optimal State Changes | 2026 | PODS | 4.1945683e-05 |
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |
| 10,983 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 4.1945683e-05 |
| 11,562 | Timely Reporting of Heavy Hitters using External Memory | 2020 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 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 |
| 1,094 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS | 0.00014129658 |
| 1,629 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00011085267 |
| 4,618 | Approximate Frequency Counts over Data Streams | 2012 | VLDB | 6.0446717e-05 |
| 6,418 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.0696932e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,522 | Differentially Private Hierarchical Heavy Hitters | 2024 | PODS | 4.4937074e-05 |
| 11,321 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1945683e-05 |
| 10,556 | Efficient Concurrent Updates to Persistent Randomized Binary Search Trees | 2025 | VLDB | 4.1945683e-05 |
| 11,855 | Range Thresholding on Streams | 2016 | SIGMOD | 4.1945683e-05 |
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |
| 10,983 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 4.1945683e-05 |
| 11,440 | Frequent Elements with Witnesses in Data Streams | 2021 | PODS | 4.1945683e-05 |
| 1,629 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00011085267 |
| 10,005 | Finding Heavy-Hitters with Optimal State Changes | 2026 | PODS | 4.1945683e-05 |
| 6,418 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.0696932e-05 |