An efficient clustering method for k-anonymization

Published 29 March 2008

Jun-Lin Lin, Meng-Cheng Wei

Citations92

TL;DR

Experiments show that the proposed clustering-based k-anonymization method outperforms another method with respect to information loss and resilience to outliers, even though their method has a time complexity of O(n2).

Abstract

The k-anonymity model is a privacy-preserving approach that has been extensively studied for the past few years. To minimize the information loss due to anonymization, it is crucial to group similar data together and then anonymize each group individually. This work proposes a clustering-based k-anonymization method that runs in O(n2/k) time. We experimentally compare our method with another clustering-based k-anonymization method recently proposed by Byun et al. Even though their method has a time complexity of O(n2), the experiments show that our method outperforms their method with respect to information loss and resilience to outliers.

Keywords

Computer Science

International Journal of Uncertainty Fuzziness and Knowledge-Based Systemsk-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

8,492 Citations2002Latanya Sweeney

The solution provided in this paper includes a formal protection model named k-anonymity and a set of accompanying policies for deployment and examines re-identification attacks that can be realized on releases that adhere to k- anonymity unless accompanying policies are respected.

t-Closeness: Privacy Beyond k-Anonymity and l-Diversity

3,322 Citations2007Ninghui Li, Tiancheng Li +1 more

L-diversity: privacy beyond k-anonymity

2,376 Citations2006Ashwin Machanavajjhala, Johannes Gehrke +2 more

This paper shows with two simple attacks that a \kappa-anonymized dataset has some subtle, but severe privacy problems, and proposes a novel and powerful privacy definition called \ell-diversity, which is practical and can be implemented efficiently.

IEEE Transactions on Knowledge and Data EngineeringProtecting respondents identities in microdata release

2,302 Citations2001Pierangela Samarati

This paper addresses the problem of releasing microdata while safeguarding the anonymity of respondents to which the data refer and introduces the concept of minimal generalization that captures the property of the release process not distorting the data more than needed to achieve k-anonymity.

(α, k)-anonymity

625 Citations2006Raymond Chi-Wing Wong, Jiuyong Li +2 more

It is proved that the optimal (α, k)-anonymity problem is NP-hard, and a local-recoding algorithm is proposed which is more scalable and result in less data distortion.

Top-Down Specialization for Information and Privacy Preservation

574 Citations2005Benjamin C. M. Fung, Ke Wang +1 more

The results show that quality of classification can be preserved even for highly restrictive privacy requirements, and has great applicability to both public and private sectors that share information for mutual benefits and productivity.

Lecture notes in computer scienceEfficient k-Anonymization Using Clustering Techniques

329 Citations2007Ji-Won Byun, Ashish Kamra +2 more

An approach that uses the idea of clustering to minimize information loss and thus ensure good data quality is proposed, and a suitable metric to estimate the information loss introduced by generalizations is developed, which works for both numeric and categorical data.

Capturing data usefulness and privacy protection in K-anonymisation

72 Citations2007Grigorios Loukides, Jianhua Shao

A metric that attempts to quantify these two properties of privacy protection and data usefulness and introduces a clustering based algorithm that can achieve a balance between them in k-anonymisation is suggested.

Lecture notes in computer scienceA k-Anonymity Clustering Method for Effective Data Privacy Preservation

45 Citations2007Chuang-Cheng Chiu, Chieh-Yuan Tsai

A novel clustering method for conducting the k-anonymity model effectively is proposed, which keeps the benefit of scalability and computational efficiency when comparing to other popular clustering algorithms.