The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
On the complexity of optimal K-anonymity
Abstract
The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4, However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k log m)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
SWEENEY, L. (2002) · International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems · doi:10.1142/s0218488502001648 · Cited by 8,571
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335438 · Cited by 2,961
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335438 · Cited by 1,719
On the design and quantification of privacy preserving data mining algorithms
Agrawal, D., & Aggarwal, C. C. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375602 · Cited by 1,006
Revealing information while preserving privacy
Dinur, I., & Nissim, K. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773173 · Cited by 980
Limiting privacy breaches in privacy preserving data mining
Evfimievski, A., Gehrke, J., & Srikant, R. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773174 · Cited by 815
Generalizing data to provide anonymity when disclosing information (abstract)
Samarati, P., & Sweeney, L. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275508 · Cited by 779
Agrawal, R., Kiernan, J., Srikant, R., & Xu, Y. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50021-4 · Cited by 723
Kleinberg, J. M., Papadimitriou, C. H., & Raghavan, P. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(02)00036-3 · Cited by 76
Cited by
L -diversity: Privacy beyond k -anonymity
Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217302 · Cited by 3,617
t-Closeness: Privacy Beyond k-Anonymity and l-Diversity
Li, N., Li, T., & Venkatasubramanian, S. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.367856 · Cited by 3,451
L-diversity: privacy beyond k-anonymity
Machanavajjhala, A., Gehrke, J., Kifer, D., & Venkitasubramaniam, M. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.1 · Cited by 2,362
Privacy-preserving data publishing: A survey of recent developments
Fung, B. C. M., Wang, K., Chen, R., & Yu, P. S. (2010) · ACM Computing Surveys · doi:10.1145/1749603.1749605 · Cited by 1,704
Data Privacy through Optimal k-Anonymization
Bayardo, R. J., & Agrawal, R. (2005) · 21st International Conference on Data Engineering (ICDE'05) · doi:10.1109/icde.2005.42 · Cited by 1,131
Mondrian Multidimensional K-Anonymity
LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.101 · Cited by 1,124
Incognito: efficient full-domain K-anonymity
LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066164 · Cited by 1,070
The new Casper: query processing for location services without compromising privacy
Mokbel, M. F., Chow, C.-Y., & Aref, W. G. (2006) · doi:10.5555/1182635.1164193 · Cited by 999
Protecting Location Privacy with Personalized k-Anonymity: Architecture and Algorithms
Gedik, B., & Liu, L. (2008) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2007.1062 · Cited by 837
Estimating the success of re-identifications in incomplete datasets using generative models
Rocher, L., Hendrickx, J. M., & de Montjoye, Y.-A. (2019) · Nature Communications · doi:10.1038/s41467-019-10933-3 · Cited by 816
Towards identity anonymization on graphs
Liu, K., & Terzi, E. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376629 · Cited by 773
Big healthcare data: preserving security and privacy
Abouelmehdi, K., Beni-Hessane, A., & Khaloufi, H. (2018) · Journal of Big Data · doi:10.1186/s40537-017-0110-7 · Cited by 738
Personalized privacy preservation
Xiao, X., & Tao, Y. (2006) · Proceedings of the 2006 ACM SIGMOD international conference on Management of data · doi:10.1145/1142473.1142500 · Cited by 670
Anatomy: simple and effective privacy preservation
Xiao, X., & Tao, Y. (2006) · Very Large Data Bases · doi:10.5555/1182635.1164141 · Cited by 642
(α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing
Wong, R. C.-W., Li, J., Fu, A. W.-C., & Wang, K. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150499 · Cited by 625
Preventing Location-Based Identity Inference in Anonymous Spatial Queries
Kalnis, P., Ghinita, G., Mouratidis, K., & Papadias, D. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.190662 · Cited by 620
Next place prediction using mobility Markov chains
Gambs, S., Killijian, M.-O., & del Prado Cortez, M. N. (2012) · Proceedings of the First Workshop on Measurement, Privacy, and Mobility · doi:10.1145/2181196.2181199 · Cited by 533
A peer-to-peer spatial cloaking algorithm for anonymous location-based service
Chow, C.-Y., Mokbel, M. F., & Liu, X. (2006) · Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems · doi:10.1145/1183471.1183500 · Cited by 506
A General Survey of Privacy-Preserving Data Mining Models and Algorithms
Aggarwal, C. C., & Yu, P. S. (2008) · Advances in Database Systems · doi:10.1007/978-0-387-70992-5_2 · Cited by 469
M-invariance: towards privacy preserving re-publication of dynamic datasets
Xiao, X., & Tao, Y. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247556 · Cited by 466
Ordinal, Continuous and Heterogeneous k-Anonymity Through Microaggregation
Domingo-Ferrer, J., & Torra, V. (2005) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-0007-5 · Cited by 432
Utility-based anonymization using local recoding
Xu, J., Wang, W., Pei, J., Wang, X., Shi, B., & Fu, A. W.-C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150504 · Cited by 424
PRIVE: anonymous location-based queries in distributed mobile systems
Ghinita, G., Kalnis, P., & Skiadopoulos, S. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242623 · Cited by 402
Big data privacy: a technological perspective and review
Jain, P., Gyanchandani, M., & Khare, N. (2016) · Journal of Big Data · doi:10.1186/s40537-016-0059-y · Cited by 392
Aggregate Query Answering on Anonymized Tables
Zhang, Q., Koudas, N., Srivastava, D., & Yu, T. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.367857 · Cited by 357
Anonymizing Classification Data for Privacy Preservation
Fung, B. C. M., Wang, K., & Yu, P. S. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.1015 · Cited by 349
Efficient k-Anonymization Using Clustering Techniques
Byun, J.-W., Kamra, A., Bertino, E., & Li, N. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71703-4_18 · Cited by 329
Privacy-preserving anonymization of set-valued data
Terrovitis, M., Mamoulis, N., & Kalnis, P. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1453856.1453874 · Cited by 326
Injecting utility into anonymized datasets
Kifer, D., & Gehrke, J. (2006) · Proceedings of the 2006 ACM SIGMOD international conference on Management of data · doi:10.1145/1142473.1142499 · Cited by 296
Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., & Zhu, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30570-5_17 · Cited by 292
Privacy Preservation in the Publication of Trajectories
Terrovitis, M., & Mamoulis, N. (2008) · The Ninth International Conference on Mobile Data Management (mdm 2008) · doi:10.1109/mdm.2008.29 · Cited by 289
Achieving anonymity via clustering
Aggarwal, G., Feder, T., Kenthapadi, K., Khuller, S., Panigrahy, R., Thomas, D., & Zhu, A. (2006) · Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1142351.1142374 · Cited by 271
Anonymizing sequential releases
Wang, K., & Fung, B. C. M. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150449 · Cited by 253
Privacy in Internet of Things: From Principles to Technologies
Li, C., & Palanisamy, B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2864168 · Cited by 130
Metadata
- Authors
- Meyerson, A., & Williams, R.
- Venue
- Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
- Publisher
- ACM
- Published
- 2004-06-14
- Pages
- 223-228
- OpenAlex
- W2052806235
- Cited by
- 821
- References
- 11
- FWCI
- 21.69
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.