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.00028264843
Overall Rank
305 | 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
458 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.00022698513
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
800 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00016463554
1,382 Minimality Attack in Privacy Preserving Data Publishing 2007 VLDB 0.00012270633
1,582 The New Casper: Query Processing for Location Services without Compromising Privacy 2006 VLDB 0.00011262294
1,639 Injecting Utility into Anonymized Datasets 2006 SIGMOD 0.00011049413
1,733 On k-Anonymity and the Curse of Dimensionality 2005 VLDB 0.00010715774
2,116 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 9.5135165e-05
2,656 Personalized Privacy Preservation 2006 SIGMOD 8.3636527e-05
2,822 Achieving Anonymity via Clustering 2006 PODS 8.0624025e-05
3,382 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.1538038e-05
3,786 Checking for k-Anonymity Violation by Views 2005 VLDB 6.7652896e-05
4,527 Anonymization of Set-Valued Data via Top-Down, Local Generalization 2009 VLDB 6.1076171e-05
4,981 Fast Data Anonymization with Low Information Loss 2007 VLDB 5.7823243e-05
6,476 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.040879e-05
7,475 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 4.714352e-05
8,277 Measuring Re-identification Risk 2023 SIGMOD 4.5392079e-05
8,303 Personalized Privacy Protection in Social Networks 2011 VLDB 4.5392079e-05
8,349 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 4.5343355e-05
8,791 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 4.4459403e-05
8,935 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 4.4229886e-05
9,343 Preservation of Proximity Privacy in Publishing Numerical Sensitive Data 2008 SIGMOD 4.351469e-05
11,447 Privacy: From Database Reconstruction to Legal Theorems 2021 PODS 4.1905499e-05
12,138 Publishing Microdata with a Robust Privacy Guarantee 2012 VLDB 4.1905499e-05
12,237 Non-homogeneous Generalization in Privacy Preserving Data Publishing 2010 SIGMOD 4.1905499e-05
12,360 Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss 2009 VLDB 4.1905499e-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.00074213516
137 Revealing Information while Preserving Privacy 2003 PODS 0.00042381562
148 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00041196325
177 Limiting Privacy Breaches in Privacy Preserving Data Mining 2003 PODS 0.00037858416
225 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.0003266103
357 Hippocratic Databases 2002 VLDB 0.00026062775
1,504 Auditing Boolean Attributes 2000 PODS 0.00011607327
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,475 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 4.714352e-05
8,934 Privacy Preservation by Disassociation 2012 VLDB 4.4229886e-05
800 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00016463554
458 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.00022698513
3,786 Checking for k-Anonymity Violation by Views 2005 VLDB 6.7652896e-05
2,822 Achieving Anonymity via Clustering 2006 PODS 8.0624025e-05
225 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.0003266103
3,382 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.1538038e-05
4,981 Fast Data Anonymization with Low Information Loss 2007 VLDB 5.7823243e-05
6,476 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.040879e-05