Record Linkage oder Entity Resolution ist der Prozess des Auffindens von Objekten in einer oder mehrerer Datenquellen, die dasselbe Realwelt-Objekt repräsentieren. Dafür werden die Datensätze anhand von Ähnlichkeitsfunktionen miteinander verglichen. Diese Funktionen berechnen zum Beispiel die Ähnlichkeit von zwei Eingabestrings.
Personenbezogenen Daten unterliegen im Allgemeinen strenge Datenschutzbestimmungen und können nur in anonymisierter Form verarbeitet oder an Dritten weitergegeben werden. „Privacy Preserving Record Linkage“ (PPRL), anders als das klassische Record Linkage, versucht die Daten zu anonymisieren/verschlüsseln bevor sie miteinander verglichen werden. Diese Erweiterung ist wichtig wenn z.B. Patientendaten zwischen medizinischen Forschungsgruppen ausgetauscht werden müssen. Eine der effizientesten Anonymisierungsmethode ist die Kodierung jedes Datensatzes in einem Bloom Filter mittels einer Menge von Hash-funktionen.
Da die Datenquellen sehr groß sein können und um die quadratische Komplexität des Problems zu entschärfen, werden so genannte Blocking-Verfahren verwendet. Dabei werden, basierend auf bestimmten Keys, Blöcke von (ähnlichen) Datensätzen generiert. Danach werden nur Datensätze innerhalb der Blöcke miteinander verglichen.
Die Verwendung von Metric Spaces ist eine andere Methode um die Daten zu indexieren oder partitionieren. Hier werden alle Datensätze als Objekte in einem mehrdimensionalen Raum betrachtet und die Ähnlichkeit wird mit dem Abstand zwischen ihnen bemessen. Für die Partitionierung des Raumes werden die Datensätze auf bestimmte ausgewählte Objekte (Pivot) verteilt. Anschließend wird die Dreieckungleichheit angewandt, um möglichst viele unähnliche Datensätze vom Vergleich auszuschließen.
Eine weitere Möglichkeit für skalierbare Lösungen ist die Verwendung von Parallelen Frameworks, Clusters (z.B. Flink oder Spark) oder Graphikkarten. Diese können mit den üblichen Blocking-Methoden kombiniert um den PPRL-Prozess zu beschleunigen.
Ziel der Abschlussarbeit ist die Untersuchung, Implementierung und Evaluierung des Metric Space Ansatzes in einer parallelen Umgebung (z.B. Flink). Hier stehen vor allem zwei Fragen im Fokus:
- Wie können (gute) Pivots parallel ausgewählt?
- Wie kann das parallele Matching-Verfahren effizient ausgeführt?
Kontakt:
Ziad Sehili (Mail: sehili@informatik.uni-leipzig.de)