A novel local search method for microaggregation

Abstract

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 <em>n</em> records into groups of at least <em>k</em> and at most 2<em>k</em>_1 records, such that the sum of the within-group squared error (SSE) 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 <em>O (n²)</em> time. Experimental results on real and synthetic data sets with different distributions demonstrate the effectiveness of the method in producing useful protected data sets.