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,399 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2134435e-05 |
| 6,415 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.064828e-05 |
| 7,146 | Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model | 2019 | PODS | 4.8133378e-05 |
| 7,495 | Subspace Exploration: Bounds on Projected Frequency Estimation | 2021 | PODS | 4.7135369e-05 |
| 8,203 | SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model | 2022 | VLDB | 4.5552628e-05 |
| 10,004 | Finding Heavy-Hitters with Optimal State Changes | 2026 | PODS | 4.1905499e-05 |
| 10,905 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1905499e-05 |
| 10,986 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 4.1905499e-05 |
| 11,566 | Timely Reporting of Heavy Hitters using External Memory | 2020 | SIGMOD | 4.1905499e-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.00072660894 |
| 1,117 | Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems | 2011 | PODS | 0.0001386123 |
| 1,744 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00010694459 |
| 5,082 | Approximate Frequency Counts over Data Streams | 2012 | VLDB | 5.7066369e-05 |
| 6,415 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.064828e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,520 | Differentially Private Hierarchical Heavy Hitters | 2024 | PODS | 4.4893996e-05 |
| 11,323 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1905499e-05 |
| 10,565 | Efficient Concurrent Updates to Persistent Randomized Binary Search Trees | 2025 | VLDB | 4.1905499e-05 |
| 11,863 | Range Thresholding on Streams | 2016 | SIGMOD | 4.1905499e-05 |
| 10,905 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1905499e-05 |
| 10,986 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 4.1905499e-05 |
| 11,443 | Frequent Elements with Witnesses in Data Streams | 2021 | PODS | 4.1905499e-05 |
| 1,744 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00010694459 |
| 10,004 | Finding Heavy-Hitters with Optimal State Changes | 2026 | PODS | 4.1905499e-05 |
| 6,415 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems | 2016 | PODS | 5.064828e-05 |