Optimal K-anonymity using Monotonicity Property

Abstract

The Electronic-Era has brought the major challenge to the individual’s privacy by collecting the individual’s information. This information is a threat to the privacy as it is published to the third party for the purpose of either research or study. Even though the identity is not published, based on some informative attributes and publicly available data, fraudulent can access the information which is supposed to be private. As a result, many researchers are attracted towards the challenge and as a result, various approaches are devised by the researchers to anonymize data. Anonymization process should preserve the utility of data after anonymization. Anonymization is basically a skilled work to preserve private data without hiding necessary details required for research and study. Also, it should take less time to process the data. The main goal of the process is hiding data without loss of utility of the data. The work done in this thesis focuses on generalization based approach for data anonymization. Generalization hierarchy in anonymization process is created using all possible transformations that can be applied to obtained anonymized data. This generalization hierarchy possesses a special property called ‘monotonicity’ which reduces the time for anonymity check by applying predictive tagging. Anonymization algorithms with generalization based approach proceeds in two ways. One is binary search and another is a greedy approach. Algorithms which uses binary search approach applies monotonicity property to reduce solution space and greedy approach proceeds rapidly to find a solution. Proposed algorithm uses a greedy approach with monotonicity property to find a globally optimal solution.