Groupe d’études et de recherche en analyse des décisions

A Column Generation Heuristic for Microdata Protection

Daniel Aloise Professeur adjoint, Département de génie informatique, Universidade Federal do Rio Grande do Norte, Brésil

The biggest challenge when disclosing private data is to share information contained in databases while protecting people from being individually identified. Microaggregation is a family of methods for statistical disclosure control. The principle of microaggregation is that confidentiality rules permit the publication of individual records if they are partitioned into groups of \(g\) or more data, where none is more representative than the others in the same group.

The application of such rules leads to replacing individual values by those computed from small groups (microaggregates), before data publication.

This work proposes a column generation heuristic for numerical microdata.

Computational experiments show that the proposed method finds the best results for a set of benchmark instances in the literature.