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.00019072866
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
470 Incognito: Efficient Full-Domain K-Anonymity 2005 SIGMOD 0.00017747844
584 Anatomy: Simple and Effective Privacy Preservation 2006 VLDB 0.00015947172
1,008 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00012545302
1,020 m-Invariance: Towards Privacy Preserving Re-publication of Dynamic Datasets 2007 SIGMOD 0.00012437652
1,323 Minimality Attack in Privacy Preserving Data Publishing 2007 VLDB 0.00011023322
1,705 Injecting Utility into Anonymized Datasets 2006 SIGMOD 9.8267971e-05
1,769 The New Casper: Query Processing for Location Services without Compromising Privacy 2006 VLDB 9.6832743e-05
1,870 On k-Anonymity and the Curse of Dimensionality 2005 VLDB 9.4669965e-05
2,178 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 8.9117503e-05
2,453 Personalized Privacy Preservation 2006 SIGMOD 8.439518e-05
3,166 Achieving Anonymity via Clustering 2006 PODS 7.5732039e-05
3,294 Privacy-preserving Anonymization of Set-valued Data 2008 VLDB 7.4454742e-05
3,927 Checking for k-Anonymity Violation by Views 2005 VLDB 6.916351e-05
4,432 Anonymization of Set-Valued Data via Top-Down, Local Generalization 2009 VLDB 6.5992973e-05
4,805 Fast Data Anonymization with Low Information Loss 2007 VLDB 6.406552e-05
6,682 Approximate Algorithms for k-Anonymity 2007 SIGMOD 5.7079897e-05
8,048 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.3989672e-05
8,693 Measuring Re-identification Risk 2023 SIGMOD 5.2880532e-05
8,720 Personalized Privacy Protection in Social Networks 2011 VLDB 5.2880532e-05
8,836 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.2661518e-05
9,173 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.2126805e-05
9,271 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.2032182e-05
9,674 Preservation of Proximity Privacy in Publishing Numerical Sensitive Data 2008 SIGMOD 5.142891e-05
11,955 Privacy: From Database Reconstruction to Legal Theorems 2021 PODS 4.9769913e-05
12,623 Publishing Microdata with a Robust Privacy Guarantee 2012 VLDB 4.9769913e-05
12,721 Non-homogeneous Generalization in Privacy Preserving Data Publishing 2010 SIGMOD 4.9769913e-05
12,841 Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss 2009 VLDB 4.9769913e-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
69 Privacy-Preserving Data Mining 2000 SIGMOD 0.00037940729
122 Revealing Information while Preserving Privacy 2003 PODS 0.00030756232
226 Limiting Privacy Breaches in Privacy Preserving Data Mining 2003 PODS 0.00023973554
254 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00023009248
347 Generalizing Data to Provide Anonymity when Disclosing Information 1998 PODS 0.00020316249
412 Hippocratic Databases 2002 VLDB 0.00018691177
2,053 Auditing Boolean Attributes 2000 PODS 9.1158712e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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