Set-valued Data Publication with Local Privacy: Tight Error Bounds and Efficient Mechanisms

Summary: Wheel mechanism enables utility-optimal LDP publication of high-dimensional set-valued data, with each user sending one numerical value. It achieves optimal Θ(md/(nε²)) error, O(min{m log m, me^ε}) computation, and O(log(me^ε)) communication. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12227
Venue: VLDB
Year: 2020
Pagerank: 5.3804383e-05
Overall Rank: 8,707 | 40.27%
DOI: 10.14778/3389133.3389140

Incoming Non-self Citations Over Time

Authors

1. Shaowei Wang (Tencent)
2. Yuqiu Qian (Tencent)
3. Jiachun Du (Tencent)
4. Wei Yang (University of Science and Technology Beijing)
5. Liusheng Huang (University of Science and Technology Beijing)
6. Hongli Xu (University of Science and Technology Beijing)

BibTeX Citation

@article{wang_vldb20,
        title = {{Set-valued Data Publication with Local Privacy: Tight Error Bounds and Efficient Mechanisms}},
        author = {Wang, Shaowei and Qian, Yuqiu and Du, Jiachun and Yang, Wei and Huang, Liusheng and Xu, Hongli},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {8},
        pages = {1234--1247},
        doi = {10.14778/3389133.3389140},
        url = {https://doi.org/10.14778/3389133.3389140},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,132	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.8832571e-05
5,595	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB	6.1548101e-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
1,421	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB	0.00010828328
1,837	Marginal Release Under Local Differential Privacy	2018	SIGMOD	9.6443703e-05
2,366	On Differentially Private Frequent Itemset Mining	2013	VLDB	8.6866148e-05
2,856	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	8.0321774e-05
3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.6179491e-05
4,344	Anonymization of Set-Valued Data via Top-Down, Local Generalization	2009	VLDB	6.7522581e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,074	Differentially Private Event Sequences over Infinite Streams	2014	VLDB
2	7,898	A workload-adaptive mechanism for linear queries under local differential privacy	2020	VLDB
3	10,473	MTSP-LDP: A Framework for Multi-Task Streaming Data Publication under Local Differential Privacy	2026	SIGMOD
4	3,166	LDP-IDS: Local Differential Privacy for Infinite Data Streams	2022	SIGMOD
5	11,428	On the Risks of Collecting Multidimensional Data Under Local Differential Privacy	2023	VLDB
6	2,856	Publishing Set-Valued Data via Differential Privacy	2011	VLDB
7	3,143	Frequency Estimation under Local Differential Privacy	2021	VLDB
8	10,838	Privacy for Free: Leveraging Local Differential Privacy Perturbed Data from Multiple Services	2025	VLDB
9	2,749	Estimating Numerical Distributions under Local Differential Privacy	2020	SIGMOD
10	7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB