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.