An Efficient Clustering Algorithm for k-Anonymisation

K-anonymisation isan approach to protecting individuals from being identified fromdata. Good k-anonymisations should retain data utility andpreserve privacy, but few methods have considered these twoconflicting requirements together. In this paper, we extend our previous workon a clustering-based method for balancing data utility and privacy protection,and propose a set of heuristics toimprove its effectiveness. We introduce new clustering criteriathat treat utility and privacy on equal terms and proposesampling-based techniques to optimally set up its parameters.Extensive experiments show that the extended method achieves goodaccuracy in query answering and is able to prevent linking attackseffectively.