(α, k)-anonymity

TLDR

Privacy preservation is critical in data mining, and while k‑anonymity protects individual identification, recent work shows it is insufficient to safeguard associations between individuals and sensitive attributes. This paper introduces an (α, k)-anonymity model that simultaneously protects individual identities and their associations with sensitive data. The authors analyze the properties of (α, k)-anonymity, present an optimal global‑recoding solution, and propose a scalable local‑recoding algorithm that reduces data distortion, also outlining extensions to broader scenarios. They prove the (α, k)-anonymity optimization problem is NP‑hard and demonstrate that their algorithms achieve efficient, effective anonymization in experimental evaluations.

Abstract

Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentamos optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case.