Iterative Constraint Satisfaction method for Microaggregation Problem

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 records into groups of at least and at most records, such that the sum of the within-group squared error () is minimized. We propose a local search algorithm which iteratively satisfies the constraints of the optimal solution of the problem. The algorithm solves the problem in time. Experimental results on real and synthetic data sets with different distributions demonstrate the effectiveness of the method in producing more useful data sets for the same levels of privacy requirements.