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: 10126
Venue: VLDB
Year: 2009
Pagerank: 6.5343833e-05
Overall Rank: 4,732 | 67.54%
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,488	Towards Model-based Pricing for Machine Learning in a Data Marketplace	2019	SIGMOD	0.00010612416
2,799	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1125988e-05
9,135	Universally Optimal Privacy Mechanisms for Minimax Agents	2010	PODS	5.3166398e-05
9,485	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	5.2634238e-05
9,602	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	5.2487195e-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
70	Privacy-Preserving Data Mining	2000	SIGMOD	0.0003804755
130	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00030604781
218	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00024420564
450	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00018155142
572	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00016316092
855	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00013579513
1,010	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00012684067
1,074	Privacy Preserving OLAP	2005	SIGMOD	0.0001230007
1,217	Maintaining Data Privacy in Association Rule Mining	2002	VLDB	0.00011627624
1,295	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00011272398
1,669	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00010050522
1,746	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	9.8564338e-05
2,255	Attacks on Privacy and deFinetti's Theorem	2009	SIGMOD	8.8595313e-05
4,559	Deriving Private Information from Randomized Data	2005	SIGMOD	6.6318893e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,699	Fast Data Anonymization with Low Information Loss	2007	VLDB
2	2,862	Privacy via Pseudorandom Sketches	2006	PODS
3	1,295	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB
4	7,850	Differentially Private Data Release over Multiple Tables	2023	PODS
5	2,856	Publishing Set-Valued Data via Differential Privacy	2011	VLDB
6	9,485	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB
7	123	Revealing Information while Preserving Privacy	2003	PODS
8	5,595	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB
9	3,232	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
10	218	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS