Multidimensional K-Anonymity
Show full item record
File(s):
- Author(s)
-
LeFevre, Kristen; DeWitt, David J.; Ramakrishnan, Raghu
- Publisher
- University of Wisconsin-Madison Department of Computer Sciences
- Date
- Mar 15, 2012
- Abstract
- 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/60428
- Export
-
Export to RefWorks
Part of
Show full item record
