A polynomial algorithm for optimal univariate microaggregation

Microaggregation is a technique used by statistical agencies to limit disclosure of sensitive microdata. Noting that no polynomial algorithms are known to microaggregate optimally, Domingo-Ferrer and Mateo-Sanz have presented heuristic microaggregation methods. This paper is the first to present an efficient polynomial algorithm for optimal univariate microaggregation. Optimal partitions are shown to correspond to shortest paths in a network.

1 Introduction

Statistical agencies use disclosure control methods to protect sensitive microdata (see [1] and [8] for a survey of such methods). Microaggregation is a widely used disclosure control technique. Under microaggregation, instead of releasing sensitive values for individual records, records are aggregated into groups and the mean of the group to which an observation belongs is released. Confidentiality of individual data subjects is protected by ensuring that each group has at least a minimum number of observations, k. Domingo-Ferrer and Mateo-Sanz [4] have presented heuristic methods based on hierarchical clustering and genetic algorithms to partition data into groups that minimize information loss due to aggregation.