Local and Global Recoding Methods for Anonymizing Set-valued Data
The VLDB Journal, (to appear)
2010
Journal
- Contact person: Manolis Terrovitis
Abstract.
In this paper, we study the problem of protecting privacy in the publication of set-valued data. Consider a collection of
supermarket transactions that contains detailed information about items bought together by individuals. Even after removing
all personal characteristics of the buyer, which can serve as links to his identity, the publication of such data is still
subject to privacy attacks from adversaries who have partial knowledge about the set. Unlike most previous works, we do not
distinguish data as sensitive and non-sensitive, but we consider them both as potential quasi-identifiers and potential sensitive
data, depending on the knowledge of the adversary. We define a new version of the k-anonymity guarantee, the k
m
-anonymity, to limit the effects of the data dimensionality, and we propose efficient algorithms to transform the database.
Our anonymization model relies on generalization instead of suppression, which is the most common practice in related works
on such data. We develop an algorithm that finds the optimal solution, however, at a high cost that makes it inapplicable
for large, realistic problems. Then, we propose a greedy heuristic, which performs generalizations in an Apriori, level-wise
fashion. The heuristic scales much better and in most of the cases finds a solution close to the optimal. Finally, we investigate
the application of techniques that partition the database and perform anonymization locally, aiming at the reduction of the
memory consumption and further scalability. A thorough experimental evaluation with real datasets shows that a vertical partitioning
approach achieves excellent results in practice.