Optimal Random Perturbation at Multiple Privacy Levels

Summary: Introduces multi-level random perturbation with collusion resistance: combining releases reveals no more than the least-private view. Each version remains equivalent to uniform perturbation, with optimal O(n+m) space and O(n+log m) expected generation time. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hdc76ee4d29e04d87
Venue: VLDB
Year: 2009
Pagerank: 6.4124756e-05
Overall Rank: 4,794 | 67.77%
DOI: 10.14778/1687627.1687719

Incoming Non-self Citations Over Time

Authors

1. Xiaokui Xiao (Nanyang Technological University)
2. Yufei Tao (Chinese University of Hong Kong)
3. Minghua Chen (Chinese University of Hong Kong)

BibTeX Citation

@article{xiao_vldb09,
        title = {{Optimal Random Perturbation at Multiple Privacy Levels}},
        author = {Xiao, Xiaokui and Tao, Yufei and Chen, Minghua},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687719},
        url = {https://doi.org/10.14778/1687627.1687719},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,362	Towards Model-based Pricing for Machine Learning in a Data Marketplace	2019	SIGMOD	0.0001091784
2,855	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	7.9391282e-05
9,308	Universally Optimal Privacy Mechanisms for Minimax Agents	2010	PODS	5.1973494e-05
9,665	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	5.1453267e-05
9,778	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	5.1309523e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
68	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037958605
133	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.0003006035
226	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00023984903
469	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.0001775622
584	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00015954725
879	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00013299637
1,020	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00012443542
1,097	Privacy Preserving OLAP	2005	SIGMOD	0.00012041002
1,239	Maintaining Data Privacy in Association Rule Mining	2002	VLDB	0.00011384824
1,323	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00011028542
1,705	Injecting Utility into Anonymized Datasets	2006	SIGMOD	9.831451e-05
1,782	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.652327e-05
2,296	Attacks on Privacy and deFinetti's Theorem	2009	SIGMOD	8.6789249e-05
4,651	Deriving Private Information from Randomized Data	2005	SIGMOD	6.4857639e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,929	Privacy via Pseudorandom Sketches	2006	PODS
2	10,852	Fast and Private Max-Sum Diversification	2026	VLDB
3	1,323	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB
4	8,008	Differentially Private Data Release over Multiple Tables	2023	PODS
5	2,912	Publishing Set-Valued Data via Differential Privacy	2011	VLDB
6	9,665	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB
7	122	Revealing Information while Preserving Privacy	2003	PODS
8	5,726	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB
9	3,293	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
10	226	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS