TY - JOUR
T1 - Achieving anonymity via clustering
JF - ACM Trans. Algorithms
Y1 - 2010
A1 - Aggarwal,Gagan
A1 - Panigrahy,Rina
A1 - Feder,Tomás
A1 - Thomas,Dilys
A1 - Kenthapadi,Krishnaram
A1 - Khuller, Samir
A1 - Zhu,An
KW - anonymity
KW - Approximation algorithms
KW - clustering
KW - privacy
AB - Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of deidentifying records is to remove identifying fields such as social security number, name, etc. However, recent research has shown that a large fraction of the U.S. population can be identified using nonkey attributes (called quasi-identifiers) such as date of birth, gender, and zip code. The k-anonymity model protects privacy via requiring that nonkey attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k−1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a prespecified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, that is, deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
VL - 6
SN - 1549-6325
UR - http://doi.acm.org/10.1145/1798596.1798602
CP - 3
M3 - 10.1145/1798596.1798602
ER -