Achieving P-sensitive K-anonymity via anatomy

Privacy-preserving data publishing is to protect sensitive information of individuals in published data while the distortion ratio of the data is minimized. One well-studied approach is the K-anonymity model. Recently, several authors have recognized that K-anonymity cannot prevent attribute disclosure. To address this privacy threat, one solution would be to employ P-sensitive K-anonymity, a novel paradigm in relational data privacy, which prevents sensitive attribute disclosure. P-sensitive K-anonymity partitions the data into groups of records such that each group has at least P distinct sensitive values. Existing approaches for achieving P-sensitive K-anonymity are mostly generalization-based. In this paper, we propose a novel permutation-based approach called anatomy to release the quasi-identifier and sensitive values directly in two separate tables. Combined with a grouping mechanism, this approach not only protects privacy, but captures a large amount of correlation in the microdata. We develop a top-down algorithm for computing anatomized tables that obey the P-sensitive K-anonymity privacy requirement, and minimize the error of reconstructing the microdata. Extensive experiments confirm that anatomy allows significantly more effective data analysis than the conventional publication methods based on generalization.