Non-homogeneous generalization in privacy preserving data publishing

Most previous research on privacy-preserving data publishing, ba-sed on the k-anonymity model, has followed the simplistic ap-proach of homogeneously giving the same generalized value in all quasi-identifiers within a partition. We observe that the anonymiza-tion error can be reduced if we follow a non-homogeneous gen-eralization approach for groups of size larger than k. Such an approach would allow tuples within a partition to take different generalized quasi-identifier values. Anonymization following this model is not trivial, as its direct application can easily violate k-anonymity. In addition, non-homogeneous generalization allows for additional types of attack, which should be considered in the process. We provide a methodology for verifying whether a non-homogeneous generalization violates k-anonymity. Then, we pro-pose a technique that generates a non-homogeneous generalization for a partition and show that its result satisfies k-anonymity, how-ever by straightforwardly applying it, privacy can be compromised if the attacker knows the anonymization algorithm. Based on this, we propose a randomization method that prevents this type of at-tack and show that k-anonymity is not compromised by it. Non-homogeneous generalization can be used on top of any existing par-titioning approach to improve its utility. In addition, we show that a new partitioning technique tailored for non-homogeneous gen-eralization can further improve quality. A thorough experimental evaluation demonstrates that our methodology greatly improves the utility of anonymized data in practice