Iterative constraint satisfaction method for microaggregation problem

In this paper, we propose a novel microaggregation algorithm to produce useful data in privacy preserving data publishing. Microaggregation is a clustering problem with known minimum and maximum group size constraints. We propose a local search algorithm that iteratively satisfies necessary constraints of an optimal solution of the problem. The algorithm solves the problem in O(n²) operations. Experimental results on real and synthetic data sets with different distributions confirm the effectiveness of the method.