The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Data Privacy through Optimal k-Anonymization
Abstract
Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k - 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a non-trivial dataset under a general model of the problem.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Self-citationMulti-Interval Discretization of Continuous-Valued Attributes for Classification Learning
Fayyad, U. M., & Irani, K. B. (1993) · International Joint Conference on Artificial Intelligence · Cited by 2,870
Protecting respondents identities in microdata release
Samarati, P. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.971193 · Cited by 2,324
ACHIEVING k-ANONYMITY PRIVACY PROTECTION USING GENERALIZATION AND SUPPRESSION
SWEENEY, L. (2002) · International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems · doi:10.1142/s021848850200165x · Cited by 1,976
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
Self-citationOn the complexity of optimal K-anonymity
Meyerson, A., & Williams, R. (2004) · Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1055558.1055591 · Cited by 821
Transforming data to satisfy privacy constraints
Iyengar, V. S. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775089 · Cited by 790
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
A Condensation Approach to Privacy Preserving Data Mining
Aggarwal, C. C., & Yu, P. S. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24741-8_12 · Cited by 364
Constraint-based rule mining in large, dense databases
Bayardo, R. J., Agrawal, R., & Gunopulos, D. (1999) · Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337) · doi:10.1109/icde.1999.754924 · Cited by 362
Self-citationSearch through systematic set enumeration
Rymon, R. (1992) · Cited by 346
OPUS: An Efficient Admissible Algorithm for Unordered Search
Webb, G. I. (1995) · Journal of Artificial Intelligence Research · doi:10.1613/jair.227 · Cited by 207
Datafly: a system for providing anonymity in medical data
Sweeney, L. (1998) · IFIP advances in information and communication technology · doi:10.1007/978-0-387-35285-5_22 · Cited by 145
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
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
Metadata
- Authors
- Bayardo, R. J., & Agrawal, R.
- Venue
- 21st International Conference on Data Engineering (ICDE'05)
- Publisher
- IEEE
- Published
- 2005-04-19
- Pages
- 217-228
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2161229593
- Cited by
- 1,131
- References
- 14
- FWCI
- 48.65
- 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.