An incremental privacy-preservation algorithm for the (k, e)-Anonymous model

摘要

An important issue to be addressed when data are to be published is data privacy. In this paper, the problem of data privacy based on a prominent privacy model, (k, e)-Anonymous, is addressed. Our scenario is that when a new dataset is to be released, there may be, at the same time, datasets that were released elsewhere. A problem arises because some attackers might obtain multiple versions of the same dataset and compare them with the newly released dataset. Although the privacy of all of the datasets has been well-preserved individually, such a comparison can lead to a privacy breach, which is a so-called "incremental privacy breach". To address this problem effectively, we first study the characteristics the effects of multiple dataset releases with a theoretical approach. It has been found that a privacy breach that is subjected to an increment occurs when there is overlap between any parts of the new dataset with any parts of an existing dataset. Based on our proposed studies, a polynomial-time algorithm is proposed. This algorithm needs to consider only one previous version of the dataset, and it can also skip computing the overlapping partitions. Thus, the computational complexity of the proposed algorithm is reduced from O(n(m)) to only 0(pn(3)) where p is the number of partitions, n is the number of tuples, and m is the number of released datasets. At the same time, the privacy of all of the released datasets as well as the optimal solution can be always guaranteed. In addition, experiment results that illustrate the efficiency of our algorithm on real-world datasets are presented. (C) 2014 Elsevier Ltd. All rights reserved.