Stanford InfoLab Publication Server

Approximation Algorithms for k-Anonymity

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)
Projects:PORTIA (DB-Privacy)
Related URLs:Project Homepage
ID Code:645
Deposited By:Import Account
Deposited On:04 Apr 2004 17:00
Last Modified:19 Dec 2008 10:51

Download statistics

Repository Staff Only: item control page