Optimal Random Perturbation at Multiple Privacy Levels

Summary: Multi-level random perturbation for releasing multiple privacy-tuned datasets; resilience to collusion ensures no extra knowledge beyond the most trusted recipient. Each version is analyzable as uniform perturbation; space O(n+m) and update time O(n+log m) — optimal for n>>m. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9935
Venue: VLDB
Year: 2009
Pagerank: 5.9161511e-05
Overall Rank: 4,794 | 66.66%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,891	Towards Model-based Pricing for Machine Learning in a Data Marketplace	2019	SIGMOD	0.00010194092
2,776	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1326122e-05
8,965	Universally Optimal Privacy Mechanisms for Minimax Agents	2010	PODS	4.4196402e-05
9,336	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	4.3556432e-05
9,512	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	4.3335882e-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
40	Privacy-Preserving Data Mining	2000	SIGMOD	0.00074232718
111	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00047073785
177	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.0003788711
455	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00022717354
505	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021491332
559	Maintaining Data Privacy in Association Rule Mining	2002	VLDB	0.00020147576
634	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00018895628
654	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00018613167
955	Privacy Preserving OLAP	2005	SIGMOD	0.00015075131
1,382	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00012281313
1,633	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00011060784
1,761	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	0.00010651764
2,406	Attacks on Privacy and deFinetti's Theorem	2009	SIGMOD	8.8811954e-05
4,899	Deriving Private Information from Randomized Data	2005	SIGMOD	5.8439867e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,979	Fast Data Anonymization with Low Information Loss	2007	VLDB	5.7878768e-05
3,843	Privacy via Pseudorandom Sketches	2006	PODS	6.7077542e-05
1,382	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00012281313
7,864	Differentially Private Data Release over Multiple Tables	2023	PODS	4.6327272e-05
3,097	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	7.5647028e-05
9,336	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	4.3556432e-05
136	Revealing Information while Preserving Privacy	2003	PODS	0.0004241101
7,484	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB	4.7180617e-05
3,381	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.1604078e-05
177	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.0003788711