Differentially Private Hierarchical Heavy Hitters
Summary: Formalizes differentially private hierarchical heavy hitters (DP-HHH) for both streaming and non-streaming data. Non-streaming: relative error for any prefix is independent of hierarchy height and the number of heavy hitters; streaming: absolute error is space-independent despite high sensitivity of streaming approximations, improving Ghazi et al.'s tree-counting bounds. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ari Biswas (University of Warwick)
- 2. Graham Cormode (Meta; University of Warwick)
- 3. Yaron Kanza (AT&T)
- 4. Divesh Srivastava (AT&T)
- 5. Zhengyi Zhou (AT&T)
BibTeX Citation
@inproceedings{biswas_pods24,
address = {New York, NY, USA},
series = {{PODS} '24},
title = {{Differentially Private Hierarchical Heavy Hitters}},
url = {https://dl.acm.org/doi/10.1145/3695826},
doi = {10.1145/3695826},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Biswas, Ari and Cormode, Graham and Kanza, Yaron and Srivastava, Divesh and Zhou, Zhengyi},
year = {2024}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,158 | Improved Lower Bounds for Privacy under Continual Release | 2026 | PODS | 5.093636e-05 |
| 10,647 | Private Synthetic Data Generation in Bounded Memory | 2025 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 451 | Mergeable Summaries | 2012 | PODS | 0.00018151445 |
| 2,012 | Understanding the Sparse Vector Technique for Differential Privacy | 2017 | VLDB | 9.3073552e-05 |
| 3,628 | Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams | 2005 | PODS | 7.2428869e-05 |
| 3,693 | Locating a Small Cluster Privately | 2016 | PODS | 7.1990589e-05 |
| 3,854 | Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch | 2023 | PODS | 7.0723123e-05 |
| 4,258 | Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data | 2004 | SIGMOD | 6.7994155e-05 |
| 5,036 | Finding Hierarchical Heavy Hitters in Data Streams | 2003 | VLDB | 6.3915389e-05 |
| 6,534 | Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy | 2023 | SIGMOD | 5.8486828e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,143 | Frequency Estimation under Local Differential Privacy | 2021 | VLDB |
| 2 | 1,308 | PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions | 2016 | SIGMOD |
| 3 | 1,600 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS |
| 4 | 567 | Understanding Hierarchical Methods for Differentially Private Histograms | 2013 | VLDB |
| 5 | 2,167 | Optimizing error of high-dimensional statistical queries under differential privacy | 2018 | VLDB |
| 6 | 5,746 | Federated Heavy Hitter Analytics with Local Differential Privacy | 2025 | SIGMOD |
| 7 | 7,548 | Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory | 2024 | SIGMOD |
| 8 | 8,426 | Differentially Private Hierarchical Count-of-Counts Histograms | 2018 | VLDB |
| 9 | 3,628 | Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams | 2005 | PODS |
| 10 | 5,036 | Finding Hierarchical Heavy Hitters in Data Streams | 2003 | VLDB |