title: Approximation Algorithms for k-Anonymity
creator: Aggarwal, Gagan
creator: Feder, Tomas
creator: Kenthapadi, Krishnaram
creator: Motwani, Rajeev
creator: Panigrahy, Rina
creator: Thomas, Dilys
creator: Zhu, An
subject: Miscellaneous
description: We consider the problem of releasing a table containing personal records, while ensuring individual privacy and maintaining data integrity to the extent possible. One of the techniques proposed in the literature is k-anonymization. A release is considered k-anonymous if the information corresponding to any individual in the release cannot be distinguished from that of at least k-1 other individuals whose information also appears in the release. In order to achieve k-anonymization, some of the entries of the table are either suppressed or generalized (e.g. an Age value of 23 could be changed to the Age range 20-25). The goal is to lose as little information as possible while ensuring that the release is k-anonymous. This optimization problem is referred to as the k-Anonymity problem. We show that the k-Anonymity problem is NP-hard even when the attribute values are ternary and we are allowed only to suppress entries. On the positive side, we provide an O(k)-approximation algorithm for the problem. We also give improved positive results for the interesting cases with specific values of k --- in particular, we give a 1.5-approximation algorithm for the special case of 2-Anonymity, and a 2-approximation algorithm for 3-Anonymity. 
date: 2005-11-20
type: Conference or Workshop Item
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/645/1/2004-24.pdf
identifier: Aggarwal, Gagan and Feder, Tomas and Kenthapadi, Krishnaram and Motwani, Rajeev and Panigrahy, Rina and Thomas, Dilys and Zhu, An (2005) Approximation Algorithms for k-Anonymity. In: Proceedings of the International Conference on Database Theory (ICDT 2005), January 5-7, 2005, Edinburgh, UK, .
relation: http://ilpubs.stanford.edu:8090/645/