Efficient and effective pruning strategies for health data de-identification

BMC Medical Informatics and Decision Making

Technical Advance

Fabian Prasser¹  Florian Kohlmayer¹  Klaus A. Kuhn¹ 

[1] Chair of Biomedical Informatics, Department of Medicine, Technical University of Munich (TUM), 81675, Munich, Germany;

关键词: Security;    Privacy;    De-identification;    Statistical disclosure control;    k;    Optimization;   

DOI  :  10.1186/s12911-016-0287-2

 received in 2015-10-17, accepted in 2016-04-21,  发布年份 2016

来源: Springer

【 摘 要 】

BackgroundPrivacy must be protected when sensitive biomedical data is shared, e.g. for research purposes. Data de-identification is an important safeguard, where datasets are transformed to meet two conflicting objectives: minimizing re-identification risks while maximizing data quality. Typically, de-identification methods search a solution space of possible data transformations to find a good solution to a given de-identification problem. In this process, parts of the search space must be excluded to maintain scalability.ObjectivesThe set of transformations which are solution candidates is typically narrowed down by storing the results obtained during the search process and then using them to predict properties of the output of other transformations in terms of privacy (first objective) and data quality (second objective). However, due to the exponential growth of the size of the search space, previous implementations of this method are not well-suited when datasets contain many attributes which need to be protected. As this is often the case with biomedical research data, e.g. as a result of longitudinal collection, we have developed a novel method.MethodsOur approach combines the mathematical concept of antichains with a data structure inspired by prefix trees to represent properties of a large number of data transformations while requiring only a minimal amount of information to be stored. To analyze the improvements which can be achieved by adopting our method, we have integrated it into an existing algorithm and we have also implemented a simple best-first branch and bound search (BFS) algorithm as a first step towards methods which fully exploit our approach. We have evaluated these implementations with several real-world datasets and the k-anonymity privacy model.ResultsWhen integrated into existing de-identification algorithms for low-dimensional data, our approach reduced memory requirements by up to one order of magnitude and execution times by up to 25 %. This allowed us to increase the size of solution spaces which could be processed by almost a factor of 10. When using the simple BFS method, we were able to further increase the size of the solution space by a factor of three. When used as a heuristic strategy for high-dimensional data, the BFS approach outperformed a state-of-the-art algorithm by up to 12 % in terms of the quality of output data.ConclusionsThis work shows that implementing methods of data de-identification for real-world applications is a challenging task. Our approach solves a problem often faced by data custodians: a lack of scalability of de-identification software when used with datasets having realistic schemas and volumes. The method described in this article has been implemented into ARX, an open source de-identification software for biomedical data.

【 授权许可】

CC BY   
© Prasser et al. 2016

【 图 表 】

12864_2017_4179_Article_IEq29.gif

12864_2017_3990_Article_IEq4.gif

12864_2017_4179_Article_IEq28.gif

12864_2017_3687_Article_IEq1.gif

12864_2017_4179_Article_IEq26.gif

12888_2016_877_Article_IEq13.gif

12864_2017_4179_Article_IEq24.gif

12888_2016_877_Article_IEq11.gif

12888_2016_877_Article_IEq9.gif

12870_2017_1059_Article_IEq7.gif

12888_2016_877_Article_IEq8.gif

12864_2016_3105_Article_IEq15.gif

12864_2017_3669_Article_IEq5.gif

12864_2015_2295_Article_IEq3.gif

12902_2017_191_Article_IEq3.gif

12864_2017_3669_Article_IEq2.gif

12906_2017_1593_Article_IEq20.gif

12864_2016_3353_Article_IEq8.gif

12906_2017_1593_Article_IEq16.gif

12864_2017_4186_Article_IEq14.gif

12887_2016_742_Article_IEq17.gif

12864_2017_4179_Article_IEq9.gif

12864_2017_4179_Article_IEq8.gif

12864_2017_4186_Article_IEq10.gif

12864_2017_3836_Article_IEq2.gif

12864_2017_3836_Article_IEq1.gif

12864_2017_3527_Article_IEq10.gif

12864_2017_3527_Article_IEq8.gif

12864_2017_3787_Article_IEq1.gif

12864_2017_3938_Article_IEq3.gif

12864_2017_3938_Article_IEq2.gif

12864_2016_2880_Article_IEq10.gif

12914_2017_112_Article_IEq1.gif

12864_2017_4025_Article_IEq11.gif