2005 DataPrivacyThroughOptimalKAnon
- (Bayardo & Agrawal, 2005) ⇒ Roberto J. Bayardo, Rakesh Agrawal. (2005). “Data Privacy through Optimal k-Anonymization.” In: Proceedings of the 21st International Conference on Data Engineering (ICDE 2005) doi:10.1109/ICDE.2005.42
Subject Headings: Anonymization Algorithm.
Notes
Cited By
Quotes
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 nontrivial dataset under a general model of the problem.
References
,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 2005 DataPrivacyThroughOptimalKAnon | Roberto J. Bayardo Rakesh Agrawal | Data Privacy through Optimal k-Anonymization | Proceedings of the 21st International Conference on Data Engineering | http://scholar.google.com/scholar?cites=1532368786520293374 | 10.1109/ICDE.2005.42 | 2005 |