TU Berlin

Talk 04.05.2011

isti-logo

Page Content

to Navigation

The Effect of Homogeneity on the Complexity of Anonymizing Data

André Nichterlein (TU Berlin)

Motivated by data privacy applications [3], the NP-hard k-Anonymity problem asks, given an n × m matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. A matrix M is said to be k-anonymous if for each row r in M there are at least k − 1 other rows in M which are identical to r. Complementing previous work [1, 2], we introduce two new “data-driven” parameterizations for k-Anonymity—the number in of different input rows and the number out of different output rows—for modeling aspects of data homogeneity. We show that k-Anonymity is fixed-parameter tractable for the parameter in, and it is NP-hard even for out = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that k-Anonymity can be solved in linear  time when in is a constant. Our results also extend to some interesting generalizations of k-Anonymity such as ℓ-diversity and anonymization using the so-called “domain generalization hierarchies”.

date
speaker
location
language
04.05.2011 14:15
André Nichterlein
FR 6510
german/
english*

* Language is depending on the audience.

Back to overview.

References
[1]
P. Bonizzoni, G. D. Vedova, R. Dondi, and Y. Pirola. Parameterized complexity of k-anonymity: Hardness and tractability. In Proc. 21st IWOCA, volume 6460 of LNCS, pages 242–255. Springer, 2010.
[2]
P. A. Evans, T. Wareham, and R. Chaytor. Fixed-parameter tractability of anonymizing data by suppressing entries. J. Comb. Optim., 18(4):362–375, 2009.
[3]
L. Sweeney. Uniqueness of simple demographics in the U.S. population. Technical report, Carnegie Mellon University, School of Computer Science, Laboratory for International Data Privacy, 2000.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe