direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Benutzergeführtes Anonymisieren von Daten mit Pattern Clustering: Algorithmen und Komplexität

Thomas Köhler (FSU Jena)

Eine Matrix M ist k-anonym, wenn jede Zeile aus M zu mindestens k−1 anderen Zeilen in M identisch ist. Um eine beliebige Matrix in eine k-anonyme Matrix zu überführen, werden einige Zeichen in M durch *-Symbole ersetzt, das heißt sie werden gelöscht. Eine Matrix durch eine minimale Anzahl an Löschungen in eine k-anonyme Matrix zu überführen, ist ein gut untersuchtes NP-schweres Problem. Die Idee einer k-anonymen Ausgabematrix wurde von Bredereck et al. erweitert, sodass der Benutzer Einfluss auf den Vorgang des Löschens nehmen kann. Der Benutzer erhält hierbei die Möglichkeit Muster vorzugeben, mit welchen sich bestimmen lässt, welche Stellen in der Matrix gel¨oscht werden dürfen. Das Problem, ob sich aus einem gegebenen Muster und einer Eingabematrix eine k-anonyme Matrix bilden lässt, ist als NP-schwer bekannt, selbst für Spezialfälle. In dieser Arbeit wird ebenfalls die NP-Schwere gezeigt, allerdings mit einer einfacheren Reduktion und für eingeschränktere Spezialfälle. Für NP-schwere Spezialfälle wird fixed-parameter-tractability gezeigt: Zum einen wird dies bezüglich der Anzahl an Mustern und zum anderen bezüglich dem kombinierten Parameter aus der Anzahl Löschungen und der Anzahl verschiedener Muster gezeigt. Des Weiteren werden verschiedene Kostenfunktionen vorgestellt, sodass der Benutzer mit der Wahl der Kostenfunktion weiteren Einfluss auf die Gestalt der kanonymen Ausgabematrix nehmen kann.

date
speaker
location
language
05.01.2012 16:15
Thomas Köhler
FR 6510
german

Back to the research colloquium site.

Zusatzinformationen / Extras