Optimizing Privacy While Limiting Information Loss in Distributed Data Anonymization

k-anonymity [1], [2], aims to ensure that individual data cannot be distinguished from that of at least (k−1) others in the same database, regardless of additional knowledge. However, this process involves modifying data, resulting in information loss (IL). Finding the optimal solution to minimize this loss is NP-Hard [3], [4], prompting the development of heuristics. While some of these solutions are quadratic, they are impractical for large databases, leading to proposals for distributed memory environments. In these environments, some methods utilize horizontal partitioning of the database to speed up execution time, with each processor handling multiple records simultaneously. However, as the number of processors increases, the size of subsets handled by each processor decreases, leading to increased information loss, especially as k increases. This paper addresses the problem of minimizing information loss when anonymizing large databases. We propose an approach that exploits parallelism for cluster-computing using horizontal partitioning with overlaps (i.e., where partitions have common rows) to enhance information loss for the anonymization of databases. After anonymization, anonymous subsets are aggregated to create a global anonymized database by removing duplicate records. Our proposed algorithm employs parallel hierarchical aggregation that chooses a better version of an anonymized record among the different versions where it overlaps. Experimental results show that our approach is approximately 80× faster and incurs less information loss than the centralized GkAA [5], [6] algorithm.