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: hd427efbaa68c3248
Venue: VLDB
Year: 2020
Pagerank: 5.2597458e-05
Overall Rank: 8,871 | 40.36%
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,214	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.7295366e-05
5,726	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB	6.0167127e-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,453	PrivBasis: Frequent Itemset Mining with Differential Privacy	2012	VLDB	0.0001060277
1,888	Marginal Release Under Local Differential Privacy	2018	SIGMOD	9.4287112e-05
2,416	On Differentially Private Frequent Itemset Mining	2013	VLDB	8.4962257e-05
2,912	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	7.8687198e-05
3,293	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.4490004e-05
4,430	Anonymization of Set-Valued Data via Top-Down, Local Generalization	2009	VLDB	6.6024228e-05

Semantically Similar Papers

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