Efficient microaggregation techniques for large numerical data volumes

• Published in: International journal of information security 2012-08, Vol.11 (4), p.253-267
• Main Authors: Solé, Marc, Muntés-Mulero, Victor, Nin, Jordi
• Format: Article
• Language: English
• Subjects: Algorithms; Coding and Information Theory; Communications Engineering; Computer Communication Networks; Computer information security; Computer Science; Control algorithms; Cryptology; Data analysis; Data processing; Datasets; Heuristic; Information retrieval; Management of Computing and Information Systems; Networks; Operating Systems; Privacy; Proposals; Regular Contribution; Searching; Strategy; Studies; Tradeoffs
• ISSN: 1615-5262; 1615-5270
• DOI: 10.1007/s10207-012-0158-5

The contradictory requirements of data privacy and data analysis have fostered the development of statistical disclosure control techniques. In this context, microaggregation is one of the most frequently used methods since it offers a good trade-off between simplicity and quality. Unfortunately, most of the currently available microaggregation algorithms have been devised to work with small datasets, while the size of current databases is constantly increasing. The usual way to tackle this problem is to partition large data volumes into smaller fragments that can be processed in reasonable time by available algorithms. This solution is applied at the cost of losing quality. In this paper, we revisited the computational needs of microaggregation showing that it can be reduced to two steps: sorting the dataset with regard to a vantage point and a set of k -nearest neighbors searches. Considering this new point of view, we propose three new efficient quality-preserving microaggregation algorithms based on k -nearest neighbors search techniques. We present a comparison of our approaches with the most significant strategies presented in the literature using three real very large datasets. Experimental results show that our proposals overcome previous techniques by keeping a better balance between performance and the quality of the anonymized dataset.