Database Paper Browser

Back to papers

On the Complexity of Optimal K-Anonymity

Summary: Proves NP-hardness of two general formulations of optimal k-anonymity, including suppression (minimize deleted entries). Gives poly-time approximation algorithms: an O(k log k)-approx for constant k (runtime exponential in k) and an O(k log m)-approx removing that dependence on k. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1325
Venue
PODS
Year
2004
Pagerank
0.00028290121
Overall Rank
304 | 97.89%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank Citing Paper Year Venue Pagerank
455 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.00022717354
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
803 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00016478924
1,382 Minimality Attack in Privacy Preserving Data Publishing 2007 VLDB 0.00012281313
1,580 The New Casper: Query Processing for Location Services without Compromising Privacy 2006 VLDB 0.00011270239
1,633 Injecting Utility into Anonymized Datasets 2006 SIGMOD 0.00011060784
1,735 On k-Anonymity and the Curse of Dimensionality 2005 VLDB 0.00010723402
2,119 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 9.5090272e-05
2,682 Personalized Privacy Preservation 2006 SIGMOD 8.3202837e-05
2,815 Achieving Anonymity via Clustering 2006 PODS 8.0702535e-05
3,381 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.1604078e-05
3,785 Checking for k-Anonymity Violation by Views 2005 VLDB 6.7690512e-05
4,524 Anonymization of Set-Valued Data via Top-Down, Local Generalization 2009 VLDB 6.1133444e-05
4,979 Fast Data Anonymization with Low Information Loss 2007 VLDB 5.7878768e-05
6,482 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.045711e-05
7,541 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 4.7157092e-05
8,283 Measuring Re-identification Risk 2023 SIGMOD 4.5435639e-05
8,309 Personalized Privacy Protection in Social Networks 2011 VLDB 4.5435639e-05
8,353 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 4.5386781e-05
8,794 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 4.4502028e-05
8,931 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 4.427232e-05
9,338 Preservation of Proximity Privacy in Publishing Numerical Sensitive Data 2008 SIGMOD 4.3556432e-05
11,444 Privacy: From Database Reconstruction to Legal Theorems 2021 PODS 4.1945683e-05
12,130 Publishing Microdata with a Robust Privacy Guarantee 2012 VLDB 4.1945683e-05
12,229 Non-homogeneous Generalization in Privacy Preserving Data Publishing 2010 SIGMOD 4.1945683e-05
12,352 Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss 2009 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
136 Revealing Information while Preserving Privacy 2003 PODS 0.0004241101
147 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00041235556
177 Limiting Privacy Breaches in Privacy Preserving Data Mining 2003 PODS 0.0003788711
225 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00032707646
355 Hippocratic Databases 2002 VLDB 0.00026087195
1,506 Auditing Boolean Attributes 2000 PODS 0.00011618118
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,541 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 4.7157092e-05
8,930 Privacy Preservation by Disassociation 2012 VLDB 4.427232e-05
803 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00016478924
455 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.00022717354
3,785 Checking for k-Anonymity Violation by Views 2005 VLDB 6.7690512e-05
2,815 Achieving Anonymity via Clustering 2006 PODS 8.0702535e-05
225 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00032707646
3,381 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.1604078e-05
4,979 Fast Data Anonymization with Low Information Loss 2007 VLDB 5.7878768e-05
6,482 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.045711e-05