Pattern-Guided Data Anonymization and Clustering

Bredereck, Robert; Nichterlein, André; Niedermeier, Rolf; Philip, Geevarghese

doi:10.1007/978-3-642-22993-0_19

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Pattern-Guided Data Anonymization and Clustering

MPS-Authors

There are no MPG-Authors in the publication available

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Bredereck, R., Nichterlein, A., Niedermeier, R., & Philip, G. (2011). Pattern-Guided Data Anonymization and Clustering. In F. Murlak, & P. Sankowski (Eds.), Mathematical Foundations of Computer Science 2011 (pp. 182-193). Berlin: Springer. doi:10.1007/978-3-642-22993-0_19.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-DC24-2

Abstract

A matrix~M over a fixed alphabet is k-anonymous if every row in~M has at least~k-1 identical copies in~M. Making a matrix k-anonymous by replacing a minimum number of entries with an additional *-symbol (called ``suppressing entries'') is known to be NP-hard. This task arises in the context of privacy-preserving publishing. We propose and analyze the computational complexity of an enhanced anonymization model where the user of the k-anonymized data may additionally ``guide'' the selection of the candidate matrix entries to be suppressed. The basic idea is to express this by means of ``pattern vectors'' which are part of the input. This can also be interpreted as a sort of clustering process. It is motivated by the observation that the ``value'' of matrix entries may significantly differ, and losing one (by suppression) may be more harmful than losing the other, which again may very much depend on the intended use of the anonymized data. We show that already very basic special cases of our new model lead to NP-hard problems while others allow for (fixed-parameter) tractability results.