Approximate Algorithms for k-Anonymity*

摘要

When a table containing individual data is published, disclosure of sensitive information should be prohibitive. A naive approach for the problem is to remove identifiers such as name and social security number. However, linking attacks which joins the published table with other tables on some attributes, called quasi-identifier, may reveal the sensitive information. To protect privacy against linking attack, the notion of k-anonymity which makes each record in the table be indistinguishable with k-1 other records has been proposed previously. It is shown to be NP-Hard to k-anonymize a table minimizing the number of suppressed cells. To alleviate this, O(k log k)-approximation and O(k)- approximation algorithms were proposed in previous works. In this paper, we propose several approximation algorithms that guarantee O(log k)-approximation ratio and perform significantly better than the traditional algorithms. We also provide O(βlog k)-approximate algorithms which gracefully adjust their running time according to the tolerance β(≥ 1) of the approximation ratios. Experimental results confirm that our approximation algorithms perform signifi- cantly better than traditional approximation algorithms.