Mondrian Multidimensional K-Anonymity

TLDR

K‑Anonymity protects privacy in microdata publishing, but optimal multidimensional anonymization is NP‑hard, as with previous single‑dimensional models. The paper proposes a new multidimensional model that offers greater flexibility than prior single‑dimensional approaches. The authors present a simple greedy approximation algorithm that often yields better anonymizations than exhaustive optimal methods for two single‑dimensional models. Experimental results demonstrate that the greedy algorithm produces higher‑quality anonymizations, outperforming exhaustive optimal methods on two single‑dimensional models, and that the added flexibility yields better metrics and query answerability.

Abstract

K-Anonymity has been proposed as a mechanism for protecting privacy in microdata publishing, and numerous recoding "models" have been considered for achieving ��anonymity. 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 and more specific notions of query answerability. Optimal multidimensional anonymization is NP-hard (like previous optimal ��-anonymity problems). However, we introduce a simple greedy approximation algorithm, and experimental results show that this greedy algorithm frequently leads to more desirable anonymizations than exhaustive optimal algorithms for two single-dimensional models.