Incognito - Efficient Full-Domain K-Anonymity Kristen LeFevre, David J. DeWitt, and Raghu Ramakrishnan   View Paper (PDF)   Return to Anonymity and Nondisclosure (Research) Abstract A number of organizations publish microdata for purposes such as public health and demographic research. Although attributes that clearly identify individuals, such as Name and Social Security Number, are generally removed, these databases can sometimes be joined with other public databases on attributes such as Zipcode, Sex, and Birthdate to re- identify individuals who were supposed to remain anony- mous. \Joining" attacks are made easier by the availability of other, complementary, databases over the Internet. K-anonymization is a technique that prevents joining at- tacks by generalizing and/or suppressing portions of the released microdata so that no individual can be uniquely distinguished from a group of size k. In this paper, we pro- vide a practical framework for implementing one model of k- anonymization, called full-domain generalization. We intro- duce a set of algorithms for producing minimal full-domain generalizations, and show that these algorithms perform up to an order of magnitude faster than previous algorithms on two real-life databases. Besides full-domain generalization, numerous other mod- els have also been proposed for k-anonymization. The sec- ond contribution in this paper is a single taxonomy that categorizes previous models and introduces some promising new alternatives. ©2006 Association for Computing Machinery