The Boundary Between Privacy and Utility in Data Publishing

Summary: An almost crisp separation between privacy and utility is shown: unbounded attacker priors preclude useful anonymization. For bounded priors, a novel anonymization achieving private, utility-preserving counting-query accuracy exists, improving FRAPP. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9607
Venue: VLDB
Year: 2007
Pagerank: 0.00010641674
Overall Rank: 1,760 | 87.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
506	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021481335
713	Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption	2010	SIGMOD	0.00017691286
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.000113084
2,404	Attacks on Privacy and deFinetti's Theorem	2009	SIGMOD	8.8736984e-05
3,178	Bayesian Differential Privacy on Correlated Data	2015	SIGMOD	7.4350161e-05
3,769	Output Perturbation with Query Relaxation	2008	VLDB	6.7744696e-05
4,185	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS	6.3713506e-05
4,795	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB	5.9104664e-05
4,988	Structural Signatures for Tree Data Structures	2008	VLDB	5.77696e-05
6,692	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD	4.9568011e-05
7,965	Access Control over Uncertain Data	2008	VLDB	4.6089395e-05
8,429	Data Publishing against Realistic Adversaries	2009	VLDB	4.5089326e-05
8,791	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD	4.4459403e-05
9,341	Small Domain Randomization: Same Privacy, More Utility	2010	VLDB	4.351469e-05
9,343	Preservation of Proximity Privacy in Publishing Numerical Sensitive Data	2008	SIGMOD	4.351469e-05
10,046	Aegis: A Correlation-Based Data Masking Advisor for Data-Sharing Ecosystems	2026	SIGMOD	4.1905499e-05
12,138	Publishing Microdata with a Robust Privacy Guarantee	2012	VLDB	4.1905499e-05
12,360	Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss	2009	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
137	Revealing Information while Preserving Privacy	2003	PODS	0.00042381562
177	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00037858416
458	Incognito: Efficient Full-Domain K-Anonymity	2005	SIGMOD	0.00022698513
559	Maintaining Data Privacy in Association Rule Mining	2002	VLDB	0.0002012549
567	Practical Privacy: The SuLQ Framework	2005	PODS	0.00019940193
654	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00018594644
957	Privacy Preserving OLAP	2005	SIGMOD	0.00015065499
1,639	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00011049413
3,844	Privacy via Pseudorandom Sketches	2006	PODS	6.7044812e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,480	Differential Privacy in Data Publication and Analysis	2012	SIGMOD	5.0396886e-05
10,728	Balancing Privacy and Utility in Correlated Data: A Study of Bayesian Differential Privacy	2025	VLDB	4.1905499e-05
12,237	Non-homogeneous Generalization in Privacy Preserving Data Publishing	2010	SIGMOD	4.1905499e-05
1,382	Minimality Attack in Privacy Preserving Data Publishing	2007	VLDB	0.00012270633
11,474	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD	4.1905499e-05
3,103	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	7.5578714e-05
3,382	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB	7.1538038e-05
9,342	Minimizing Minimality and Maximizing Utility: Analyzing Method-based attacks on Anonymized Data	2010	VLDB	4.351469e-05
4,185	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS	6.3713506e-05
1,639	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00011049413