English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  The Effect of Homogeneity on the Complexity of k-Anonymity

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.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bredereck, Robert1, Author
Nichterlein, André1, Author
Niedermeier, Rolf1, Author
Philip, Geevarghese1, Author           
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: BredereckNichterleinNiedermeierPhilip2011b
DOI: 10.1007/978-3-642-22953-4_5
 Degree: -

Event

show
hide
Title: FCT 2011
Place of Event: Oslo, Norway
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: Fundamentals of Computation Theory
  Abbreviation : FCT 2011
  Subtitle : 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Proceedings
Source Genre: Proceedings
 Creator(s):
Owe, Olaf1, Editor
Steffen, Martin1, Editor
Telle, Jan Arne1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 53 - 64 Identifier: ISBN: 978-3-642-22952-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6914 Sequence Number: - Start / End Page: - Identifier: -