Research On Utility-Based Anonymization

Privacy becomes a more and more serious concern in many data applications. On the one hand, the advances in database and internet technologies have enabled people to get access to more and more data, which may contain private information. For example, databases in hospitals that maintain medical cases may contain disease information of particular individuals. On the other hand, people are willing to make use of these data so as to make possible certain applications such as mining association rules from medical cases.Anonymization is an effective approach to prevent privacy leakage. By altering (generalizing or suppressing) the original data, they cannot be used to identify any individual even with external information. Efficient anonymization has attracted much research work, most of which, however, did not consider the ultimate usage of the anonymized data, leading to poor data-utility. Thus, how to protect privacy while achieving favorable data-utility has become an emergent research topic.This thesis studies the problem of utility-based anonymization, a brand new research topic in the field of privacy preserving. The contributions of this thesis are:1. Proposes a simple framework for utility-based anonymization. A novel quality metric is presented to specify the utility of anonymized data, based on which the problem of utility-based anonymization is defined.2. Proves the NP-Hardness of the proposed utility-based anonymization problem and gives two efficient heuristic algorithms. Comprehensive experimental evaluations on both real and synthetic data sets show that the proposed algorithms can achieve much better data-utility compared to existing methods.3. Analyzes the potential risk when there are incremental updates to the data to be anonymized. A simple yet efficient algorithm based on the property of monotonic incremental anonymization is proposed. The algorithm is able to optimize data-utility while preserving privacy against incremental updates.4. Discusses the essence of the anonymization problem. The significance of the idea of utility-based anonymization is also shown by applying it to other anonymization principles.