Objekte der realen Welt können mithilfe graphbasierter Datenstrukturen modelliert und maschinenlesbar gespeichert werden. Technisch wird dies zum Beispiel durch relationale Datenbanken unterstützt, die es erlauben, Eigenschaften eines Objektes und dessen Beziehungen zu anderen Objekten darzustellen. Um Duplikate auf derartigen Datenstrukturen identifizieren zu können, kommen beziehungsbasierte Duplikaterkennungsalgorithmen zum Einsatz. Es gibt bereits zahlreiche effektive oder über den Platz gut skalierende Algorithmen für beziehungsbasierte Duplikaterkennung. Allerdings ist nicht nur die Effektivität, sondern auch die Effizient eine wichtige Kenngröße praktikabler Duplikaterkennungsalgorithmen. Durch eine Parallelisierung von Algorithmen können signifikante Laufzeitersparnisse geschaffen werden ohne qualitative Einschränkungen der Ergebnisse akzeptieren zu müssen (wie z.B. beim Clustern der Daten). Eine Parallelisierung von beziehungsbasierten
Duplikaterkennungsalgorithmen ist allerdings ein nicht-triviales Problem, das besonderer Aufmerksamkeit bedarf. Der Grund dafür sind starke Abhängigkeiten der parallel durchzuführenden Berechnungen. Parallel-DDG (PDDG) ist ein Modell zur Parallelisierung von Duplikaterkennungsalgorithmen auf graphbasierten Datenstrukturen. Es macht Gebrauch von zwei Techniken, um geringe Laufzeiten zu erzielen: Stapelverarbeitung (Batching) und Parallelisierung.
Der Vortag gibt einen kurzen Überblick über die Problematik der Parallelisierung von beziehungsbasierten Duplikaterkennungsalgorithmen und deren Lösung mithilfe des PDDG-Modells. Es werden weiterhin Ergebnisse einer exemplarischen Implementierung vorgestellt und diskutiert.
