Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC22-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC23-4
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bredereck, Robert1, Autor
Nichterlein, André1, Autor
Niedermeier, Rolf1, Autor
Philip, Geevarghese1, Autor           
Affiliations:
1External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20112011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: BredereckNichterleinNiedermeierPhilip2011b
DOI: 10.1007/978-3-642-22953-4_5
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: FCT 2011
Veranstaltungsort: Oslo, Norway
Start-/Enddatum: -

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Fundamentals of Computation Theory
  Kurztitel : FCT 2011
  Untertitel : 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Proceedings
Genre der Quelle: Konferenzband
 Urheber:
Owe, Olaf1, Herausgeber
Steffen, Martin1, Herausgeber
Telle, Jan Arne1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 53 - 64 Identifikator: ISBN: 978-3-642-22952-7

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6914 Artikelnummer: - Start- / Endseite: - Identifikator: -