Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming

Summary: MDP-based frequency estimation for one-shot and streaming data across k parties. Optimal up to log factors; in epsilon-LDP, error ~ sqrt(k)/(e^{Theta(epsilon)}-1) with O(k max{epsilon, log(1/epsilon)}) communication and O(k log u) public randomness. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12702
Venue: VLDB
Year: 2022
Pagerank: 4.7397228e-05
Overall Rank: 7,401 | 48.52%
DOI: 10.14778/3547305.3547312

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,077	The Fast and the Private: Task-based Dataset Search	2024	CIDR	5.2229324e-05
6,502	Falcon: A Privacy-Preserving and Interpretable Vertical Federated Learning System	2023	VLDB	5.0361846e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
111	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00047073785
568	Practical Privacy: The SuLQ Framework	2005	PODS	0.00019949368
2,899	Privacy at Scale: Local Differential Privacy in Practice	2018	SIGMOD	7.9443198e-05
3,399	Answering Range Queries Under Local Differential Privacy	2019	VLDB	7.1408089e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
4,502	ϵktelo: A Framework for Defining Differentially-Private Computations	2018	SIGMOD	6.1366984e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,408	Estimating Numerical Distributions under Local Differential Privacy	2020	SIGMOD	8.8780076e-05
10,184	MTSP-LDP: A Framework for Multi-Task Streaming Data Publication under Local Differential Privacy	2026	SIGMOD	4.1945683e-05
2,082	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.5834599e-05
5,229	Improving Utility and Security of the Shuffler-based Differential Privacy	2020	VLDB	5.6154535e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
3,433	LDP-IDS: Local Differential Privacy for Infinite Data Streams	2022	SIGMOD	7.0998035e-05
11,227	On the Risks of Collecting Multidimensional Data Under Local Differential Privacy	2023	VLDB	4.1945683e-05
8,074	Set-valued Data Publication with Local Privacy: Tight Error Bounds and Efficient Mechanisms	2020	VLDB	4.5918992e-05
8,290	Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data	2022	PODS	4.5435639e-05
2,540	Frequency Estimation under Local Differential Privacy	2021	VLDB	8.5797299e-05