Perturbed gibbs samplers for generating large-scale privacy-safe synthetic health data

This paper introduces a non-parametric data synthesizing algorithm to generate privacy-safe ''realistic but not real'' synthetic health data. Our goal is to provide a systematic mechanism that guarantees an adequate and controllable level of privacy while substantially improving on the utility of public use data, compared to current practices by CMS, OSHPD and other agencies. The proposed algorithm synthesizes artificial records while preserving the statistical characteristics of the original data to the extent possible. The risk from ''database linking attack'' is quantified by either an l-diversified or an differentially perturbed data generation process. Moreover its algorithmic performance is optimized using Locality-Sensitive Hashing and parallel computation techniques to yield a linear-time algorithm that is suitable for Big Data Health applications. We synthesize a public Medicare claim dataset using the proposed algorithm, and demonstrate multiple data mining applications and statistical analyses using the data. The synthetic dataset delivers results that are substantially identical to those obtained from the original dataset, without revealing the actual records.