Effiziente Algorithmen

Dieses Projekt wird schnelle Algorithmen für verschiedene Fragestellungen entwickeln. Genauer gesagt werden die folgenden zwei Fragestellungen untersucht werden: Algorithmen zum Schutz der Privatsphäre und Algorithmen zur Zusammenfassung von Daten. Für beide Fragestellungen werden wir Algorithmen für sich dynamisch verändernde Eingabedaten entwickeln. Datensammlungen, die geschützte Daten über Personen und ihre Eigenschaften und Beziehungen enthalten, sind oft wertvolle Informationsquellen. Ein Beispiel dafür sind Datenmengen über die Wirksamkeit eines neuen Medikamentes. Es ist jedoch bisweilen nicht einfach, nützliche Statistiken zu veröffentlichen ohne Informationen über die Daten preiszugeben. Eine Klasse von Algorithmen, die es erlaubt, die Menge und die Wahrscheinlichkeit von unerwünschten Informationsflüssen über die Eingabedaten zu quantifizieren, heißt differentially private (DP) Algorithmen. DP-Algorithmen besitzen Eingabeparameter, die es erlauben, den unerwünschten Informationsfluss und seine Wahrscheinlichkeit zu quantifizieren. In den letzten 10 Jahren wurden DP-Algorithmen für viele Fragestellungen entwickelt und eingesetzt, zum Beispiel, um den Anteil der Handybenutzer, die an Gesundheitsinformationen interessiert sind, zu bestimmen. Die grundlegende Idee ist dabei, dass die DP-Algorithmen bei den verschiedensten Schritten, die Rechenergebnisse durch das Hinzufügen von Zufallszahlen verrauschen, d.h. mit Zufallszahlen verändern, um zu erreichen, dass (a) jeder unerwünschte Informationsfluss innerhalb der vorgegebenen Eingabeparameter liegt und dass (b) die Ergebnisse nützliche Informationen enthalten, d.h. dass der Fehler, der durch die Verrauschung hinzugefügt wurde, möglichst klein ist. Die meisten existierenden DP-Algorithmen wurden für statische Datenmengen entwickelt, d.h. alle Daten stehen dem Algorithmus von Anfang an zur Verfügung. In vielen Anwendungen ist das aber nicht der Fall, denn weitere Daten werden hinzugefügt oder schon existierende werden modifiziert. Die Entwicklung von DP-Algorithmen für dynamische Datenmengen ist allerdings noch ganz im Anfangsstadium. Daher ist das erste Ziel dieses Projekts, DP-Algorithmen für verschiedene dynamische Eingabedaten zu entwickeln, wie z.B. Punktmengen in hoch-dimensionalen Räumen, die häufig beim maschinellen Lernen benützt werden. Unsere Algorithmen sollen aber nicht nur diese Bedingungen erfüllen, sondern auch noch möglichst effizient sein, um Ressourcen zu schonen. Das zweite Ziel des Projekts ist es, Daten aus hoch-dimensionalen Räumen in Gruppen einzuteilen, sodass Daten, die örtlich nahe liegen, zusammengruppiert werden. Derartige Gruppen werden Cluster genannt und die dazugehörigen Algorithmen heißen Clusteringalgorithmen. Die existierenden Clusteringalgorithmen können aber großteils nur auf statische Daten angewandt werden. In diesem Projekt werden wir effiziente Clusteringalgorithmen für Daten, die verändert werden können, entwickeln.