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: 9936
Venue: VLDB
Year: 2009
Pagerank: 5.9104664e-05
Overall Rank: 4,795 | 66.68%
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.0001018452
2,798	iReduct: Differential Privacy with Reduced Relative Errors	2011	SIGMOD	8.1092023e-05
8,971	Universally Optimal Privacy Mechanisms for Minimax Agents	2010	PODS	4.4154104e-05
9,341	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	4.351469e-05
9,513	Answering Private Linear Queries Adaptively using the Common Mechanism	2023	VLDB	4.3294349e-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.00074213516
111	Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release	2007	PODS	0.00047047599
177	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00037858416
458	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00022698513
506	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021481335
559	Maintaining Data Privacy in Association Rule Mining	2002	VLDB	0.0002012549
633	m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets	2007	SIGMOD	0.00018881387
654	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00018594644
957	Privacy Preserving OLAP	2005	SIGMOD	0.00015065499
1,382	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00012270633
1,639	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00011049413
1,760	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB	0.00010641674
2,404	Attacks on Privacy and deFinetti's Theorem	2009	SIGMOD	8.8736984e-05
4,905	Deriving Private Information from Randomized Data	2005	SIGMOD	5.8382391e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,981	Fast Data Anonymization with Low Information Loss	2007	VLDB	5.7823243e-05
3,844	Privacy via Pseudorandom Sketches	2006	PODS	6.7044812e-05
1,382	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00012270633
7,865	Differentially Private Data Release over Multiple Tables	2023	PODS	4.6282846e-05
3,103	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	7.5578714e-05
9,341	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	4.351469e-05
137	Revealing Information while Preserving Privacy	2003	PODS	0.00042381562
7,484	Privacy Amplification via Shuffling: Unified, Simplified, and Tightened	2024	VLDB	4.7135369e-05
3,382	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.1538038e-05
177	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00037858416