Multidimensional K-Anonymity

File(s)
Date
2005Author
LeFevre, Kristen
DeWitt, David J.
Ramakrishnan, Raghu
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
K-Anonymity has been proposed as a mechanism for privacy protection in microdata publishing, and numerous recoding ?models? have been considered for achieving kanonymity. This paper proposes a new multidimensional model, which provides an additional degree of flexibility not seen in previous (single-dimensional) approaches. Often this flexibility leads to higher-quality anonymizations, as measured both by general-purpose metrics, as well as more specific notions of query answerability.
In this paper, we prove that optimal multidimensional anonymization is NP-hard (like previous k-anonymity models). However, we introduce a simple, scalable, greedy algorithm that produces anonymizations that are a constantfactor approximation of optimal. Experimental results show that this greedy algorithm frequently leads to more desirable anonymizations than two optimal exhaustive-search algorithms for single-dimensional models.
Permanent Link
http://digital.library.wisc.edu/1793/60428Citation
TR1521