About This Item

Ask the MINDS@UW Librarian

Multidimensional K-Anonymity

Show full item record


LeFevre, Kristen; DeWitt, David J.; Ramakrishnan, Raghu
University of Wisconsin-Madison Department of Computer Sciences
Mar 15, 2012
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
Export to RefWorks 

Part of

Show full item record

Search and browse


Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.