Heavy Hitters and the Structure of Local Privacy

Summary: Achieves heavy-hitters error optimal in users, domain, privacy, and failure probability under local DP, using a new structural lower bound. It also proves √k group-privacy degradation and a pure/approximate local-privacy equivalence for noninteractive protocols. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 1760
Venue: PODS
Year: 2018
Pagerank: 0.00010032135
Overall Rank: 1,678 | 88.49%
DOI: 10.1145/3196959.3196981

Incoming Non-self Citations Over Time

Authors

1. Mark Bun (Princeton University)
2. Jelani Nelson (Harvard University)
3. Uri Stemmer (Weizmann Institute of Science)

BibTeX Citation

@inproceedings{bun_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Heavy Hitters and the Structure of Local Privacy}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196981},
        doi = {10.1145/3196959.3196981},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bun, Mark and Nelson, Jelani and Stemmer, Uri},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,279	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD	8.8155688e-05
2,542	Privacy at Scale: Local Differential Privacy in Practice	2018	SIGMOD	8.4460386e-05
3,113	CGM: An Enhanced Mechanism for Streaming Data Collection with Local Differential Privacy	2021	VLDB	7.7415187e-05
3,854	Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch	2023	PODS	7.0723123e-05
4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.8832571e-05
8,521	Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data	2022	PODS	5.4119882e-05
9,545	PrivRM: A Framework for Range Mean Estimation under Local Differential Privacy	2025	SIGMOD	5.2528121e-05
10,164	Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time	2026	PODS	5.093636e-05
11,230	AAA: an Adaptive Mechanism for Locally Differentially Private Mean Estimation	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,862	Privacy via Pseudorandom Sketches	2006	PODS	8.0209471e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,150	Concurrent Composition for Differentially Private Continual Mechanisms	2026	PODS
2	4,732	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB
3	7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB
4	4,531	Distributed Privacy Preserving Information Sharing	2005	VLDB
5	5,439	Improving Utility and Security of the Shuffler-based Differential Privacy	2020	VLDB
6	7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB
7	7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS
8	7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD
9	5,746	Federated Heavy Hitter Analytics with Local Differential Privacy	2025	SIGMOD
10	3,143	Frequency Estimation under Local Differential Privacy	2021	VLDB