Applying Genetic Algorithms on Multi-level Micro-Aggregation Techniques for Secure Statistical Databases

摘要

We consider the problem of micro-aggregation in secure statistical databases, by enhancing the primitive Micro-Aggregation Technique (MAT), which integrates proximity information. This problem is known to be NP-hard and has been tackled using many heuristic solutions. In this paper, we report a new two-stage multi-variate micro-aggregation technique so-called Enhanced Genetic Multi-variate Micro-Aggregation Technique (EGMMAT). It utilizes a genetic algorithm to aggregate the multi-variate micro-data. In the first stage, the micro-data file is split into a number of various domes under the flavour of Maximum Distance Average Vector (MDAV). Each dome has pre-defined size set by administrator. It is worth mentioning that the genetic operations (crossover & mutation) are continuously applied on each dome separately until the convergences condition is satisfied. The second stage of EGMMAT starts with combining all sub-groups in all domes into one huge dome, then the refinement process is achieved by applying the genetic operations in all micro-data to enhance the final results. Our experimental results, which are done on the benchmark data sets for real-life data, demonstrate that the newly proposed method is superior to the state-of-the-art by as much as 8.5%.