A Novel Local Search Method for Microaggregation

In this paper, we propose an effective microaggregation algorithm to produce a more useful protected data for publishing. Microaggregation is mapped to a clustering problem with known minimum and maximum group size constraints. In this scheme, the goal is to cluster n records into groups of at least k and at most 2k-1 records, such that the sum of the within-group squared error (SSE) is minimized. We propose a local search algorithm which iteratively satis es the constraints of the optimal solution of the problem. The algorithm solves the problem in O(n²) time. Experimental results on real and synthetic data sets with di erent distributions demonstrate the e ectiveness of the method in producing useful protected data sets.