de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

The Effect of Homogeneity on the Complexity of k-Anonymity

MPS-Authors
There are no MPG-Authors available
Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Bredereck, R., Nichterlein, A., Niedermeier, R., & Philip, G. (2011). The Effect of Homogeneity on the Complexity of k-Anonymity. In O. Owe, M. Steffen, & J. A. Telle (Eds.), Fundamentals of Computation Theory (pp. 53-64). Berlin: Springer. doi:10.1007/978-3-642-22953-4_5.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC22-6
Abstract
The NP-hard \textsck-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, we introduce two new ``data-driven'' parameterizations for \textsc{k-Anonymity}---the number~\tin of different input rows and the number~→ut of different output rows---both modeling aspects of data homogeneity. We show that \textsc{k-Anonymity} is fixed-parameter tractable for the parameter~\tin, and it is NP-hard even for~→ut = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that \textsc{k-Anonymity} can be solved in \emph{linear time} when~\tin is a constant. Our results also extend to some interesting generalizations of \textsc{k-Anonymity.