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
h1ed269a3cf1366ab
Venue
PODS
Year
2004
Pagerank
0.00019081867
Overall Rank
404 | 97.29%
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
469 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.0001775622
584 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00015954725
1,008 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00012551244
1,020 m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets 2007 SIGMOD 0.00012443542
1,323 Minimality Attack in Privacy Preserving Data Publishing 2007 VLDB 0.00011028542
1,705 Injecting Utility into Anonymized Datasets 2006 SIGMOD 9.831451e-05
1,768 The New Casper: Query Processing for Location Services without Compromising Privacy 2006 VLDB 9.6873901e-05
1,869 On k-Anonymity and the Curse of Dimensionality 2005 VLDB 9.4714801e-05
2,175 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 8.9159708e-05
2,453 Personalized Privacy Preservation 2006 SIGMOD 8.4435151e-05
3,165 Achieving Anonymity via Clustering 2006 PODS 7.5767906e-05
3,293 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.4490004e-05
3,926 Checking for k-Anonymity Violation by Views 2005 VLDB 6.9196266e-05
4,430 Anonymization of Set-Valued Data via Top-Down, Local Generalization 2009 VLDB 6.6024228e-05
4,802 Fast Data Anonymization with Low Information Loss 2007 VLDB 6.4095862e-05
6,678 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.710693e-05
8,041 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.4015242e-05
8,685 Measuring Re-identification Risk 2023 SIGMOD 5.2905577e-05
8,712 Personalized Privacy Protection in Social Networks 2011 VLDB 5.2905577e-05
8,827 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.268646e-05
9,164 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.2151493e-05
9,261 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.2056825e-05
9,667 Preservation of Proximity Privacy in Publishing Numerical Sensitive Data 2008 SIGMOD 5.1453267e-05
11,949 Privacy: From Database Reconstruction to Legal Theorems 2021 PODS 4.9793485e-05
12,617 Publishing Microdata with a Robust Privacy Guarantee 2012 VLDB 4.9793485e-05
12,715 Non-homogeneous Generalization in Privacy Preserving Data Publishing 2010 SIGMOD 4.9793485e-05
12,835 Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss 2009 VLDB 4.9793485e-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
68 Privacy-Preserving Data Mining 2000 SIGMOD 0.00037958605
122 Revealing Information while Preserving Privacy 2003 PODS 0.00030770793
226 Limiting Privacy Breaches in Privacy Preserving Data Mining 2003 PODS 0.00023984903
254 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00023020039
347 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00020325683
411 Hippocratic Databases 2002 VLDB 0.00018699914
2,050 Auditing Boolean Attributes 2000 PODS 9.1201864e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,041 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS
2 9,260 Privacy Preservation by Disassociation 2012 VLDB
3 1,008 Towards Identity Anonymization on Graphs 2008 SIGMOD
4 469 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD
5 3,926 Checking for k-Anonymity Violation by Views 2005 VLDB
6 3,165 Achieving Anonymity via Clustering 2006 PODS
7 347 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS
8 3,293 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB
9 4,802 Fast Data Anonymization with Low Information Loss 2007 VLDB
10 6,678 Approximate Algorithms for k-Anonymity 2007 SIGMOD