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 insensitive 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.