(AINTEC) 2012

Development of Indexing for Permutation-based Privacy Preservation Approach

Juggapong Natwichai (Chiang Mai University)

Country: Thailand
Contact: juggapong@eng.cmu.ac.th

The emerging of the internet-based services poses a privacy threat to the individuals. Data transformation to meet a privacy standard becomes a requirement for typical data processing for the services. (k,e)-anonymization is one of the most promising data transformation

approaches, since it can provide high-accuracy aggregate query results. Though, the computational cost of the algorithm providing optimal solutions for such approach is not very high, i.e. O(n2). In certain environments, the data to be processed can be appended at any

time. In this paper, we address an efficiency issue of the incremental privacy preservation using (k, e)-anonymization approach. The impact of the increment is observed theoretically. We propose an incremental algorithm based on such observation. The algorithm can replace the

quadratic-complexity processing by a linear function on some part of the dataset, while the optimal results are guaranteed. Additionally, a few indexes are proposed to further improve the efficiency of the proposed algorithm. The experiments have been conducted to validate

our work. From the results, it can be seen that the proposed work is highly efficient comparing with the non- incremental algorithm and an approximation algorithm.