DBScholar

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
1324
Venue
PODS
Year
2004
Pagerank
0.00019510305
Overall Rank
384 | 97.37%
DOI
10.1145/1055558.1055591

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{meyerson_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{On the Complexity of Optimal K-Anonymity}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055591},
        doi = {10.1145/1055558.1055591},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Meyerson, Adam and Williams, Ryan},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 27 of 27 citing papers.

Rank Citing Paper Year Venue Pagerank
450 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.00018155142
572 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00016316092
985 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00012818114
1,010 m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets 2007 SIGMOD 0.00012684067
1,295 Minimality Attack in Privacy Preserving Data Publishing 2007 VLDB 0.00011272398
1,669 Injecting Utility into Anonymized Datasets 2006 SIGMOD 0.00010050522
1,734 The New Casper: Query Processing for Location Services without Compromising Privacy 2006 VLDB 9.9009944e-05
1,817 On k-Anonymity and the Curse of Dimensionality 2005 VLDB 9.6832973e-05
2,133 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 9.1164075e-05
2,397 Personalized Privacy Preservation 2006 SIGMOD 8.6343421e-05
3,110 Achieving Anonymity via Clustering 2006 PODS 7.7477034e-05
3,232 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.6179491e-05
3,845 Checking for k-Anonymity Violation by Views 2005 VLDB 7.0779843e-05
4,344 Anonymization of Set-Valued Data via Top-Down, Local Generalization 2009 VLDB 6.7522581e-05
4,699 Fast Data Anonymization with Low Information Loss 2007 VLDB 6.5560796e-05
6,554 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.8416386e-05
7,875 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.5253531e-05
8,515 Measuring Re-identification Risk 2023 SIGMOD 5.4119882e-05
8,545 Personalized Privacy Protection in Social Networks 2011 VLDB 5.4119882e-05
8,662 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.3889537e-05
9,001 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.334788e-05
9,087 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.3251649e-05
9,487 Preservation of Proximity Privacy in Publishing Numerical Sensitive Data 2008 SIGMOD 5.2634238e-05
11,642 Privacy: From Database Reconstruction to Legal Theorems 2021 PODS 5.093636e-05
12,326 Publishing Microdata with a Robust Privacy Guarantee 2012 VLDB 5.093636e-05
12,424 Non-homogeneous Generalization in Privacy Preserving Data Publishing 2010 SIGMOD 5.093636e-05
12,545 Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss 2009 VLDB 5.093636e-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
70 Privacy-Preserving Data Mining 2000 SIGMOD 0.0003804755
123 Revealing Information while Preserving Privacy 2003 PODS 0.00031082693
218 Limiting Privacy Breaches in Privacy Preserving Data Mining 2003 PODS 0.00024420564
244 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00023476901
338 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00020731054
404 Hippocratic Databases 2002 VLDB 0.00019065022
2,017 Auditing Boolean Attributes 2000 PODS 9.3006188e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,875 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS
2 9,086 Privacy Preservation by Disassociation 2012 VLDB
3 985 Towards Identity Anonymization on Graphs 2008 SIGMOD
4 450 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD
5 3,845 Checking for k-Anonymity Violation by Views 2005 VLDB
6 3,110 Achieving Anonymity via Clustering 2006 PODS
7 338 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS
8 3,232 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB
9 4,699 Fast Data Anonymization with Low Information Loss 2007 VLDB
10 6,554 Approximate Algorithms for k-Anonymity 2007 SIGMOD