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, .
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.
|Item Type:||Conference or Workshop Item (Paper)|
|Related URLs:||Project Homepage||http://crypto.stanford.edu/portia/|
|Deposited By:||Import Account|
|Deposited On:||04 Apr 2004 17:00|
|Last Modified:||19 Dec 2008 10:51|
Repository Staff Only: item control page