Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch

Summary: (ε,δ)-DP mechanism for Misra‑Gries sketches on streams that adds noise independent of sketch size, achieving error matching best non‑streaming bounds up to constants. Also a simple post‑processing variant yields <2× non‑streaming noise for ε‑DP, improving prior linear‑in‑k noise. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1924
Venue: PODS
Year: 2023
Pagerank: 7.0723123e-05
Overall Rank: 3,854 | 73.56%
DOI: 10.1145/3584372.3588673

Incoming Non-self Citations Over Time

Authors

1. Christian Janos Lebeda (Basic Algorithms Research Copenhagen; IT University of Copenhagen)
2. Jakub Tětek (Basic Algorithms Research Copenhagen; University of Copenhagen)

BibTeX Citation

@inproceedings{lebeda_pods23,
        address = {New York, NY, USA},
        series = {{PODS} '23},
        title = {{Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch}},
        url = {https://dl.acm.org/doi/10.1145/3584372.3588673},
        doi = {10.1145/3584372.3588673},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Lebeda, Christian Janos and Tětek, Jakub},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,500	Approximate DBSCAN under Differential Privacy	2025	SIGMOD	5.6029996e-05
7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.5357919e-05
10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	5.093636e-05
10,164	Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time	2026	PODS	5.093636e-05
10,647	Private Synthetic Data Generation in Bounded Memory	2025	PODS	5.093636e-05
11,123	Streaming Algorithms with Few State Changes	2024	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
1,678	Heavy Hitters and the Structure of Local Privacy	2018	PODS	0.00010032135
2,992	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.8836024e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB
2	10,647	Private Synthetic Data Generation in Bounded Memory	2025	PODS
3	5,555	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB
4	1,308	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD
5	7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD
6	7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS
7	2,992	Pan-private Algorithms Via Statistics on Sketches	2011	PODS
8	2,862	Privacy via Pseudorandom Sketches	2006	PODS
9	11,164	An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities	2024	SIGMOD
10	121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB