Hasso-Plattner-Institut
Prof. Dr. Felix Naumann
 

Neue Entwicklungen im Bereich Informationssysteme

Im Rahmen dieses Forschungsseminars stellen Mitarbeiter und Studenten ihre Forschungsarbeiten auf diesem Gebiet vor. Studenten und Gäste sind herzlich eingeladen.

Allgemein

Wann: Dienstags, 11:00 - 12:30 Uhr

Wo: Raum A-1.1

Themen und Termine

TerminThema Vortragender
21.10.2008fällt aus
28.10.2008fällt aus
4.11.2008Bericht von der VLDB 2008, Auckland, Neuseeland
Alexander Albrecht
11.11.2088fällt aus
18.11.2008Journal Club: From Complete to Incomplete Information and Back, L. Antova, C. Koch, und D. Olteanu, SIGMOD 2007Jens Bleiholder
25.11.2008Journal Club: Indexing Dataspaces, X. Dong, und A. Halevy, SIGMOD 2007 Christoph Böhm
2.12.2008fällt aus
9.12.2008Masterarbeit: Parallelisierung von GraphduplikaterkennungMaik Taubert
16.12.2008Vorstellung Bachelor Projekt
Weihnachtsferien
6.1.2009Journal Club:  TopX 2.0 at the INEX 2008 Efficiency Track- A (Very) Fast Object-Store for Top-k-style XML Full-Text Search, INEX 2008.Mohammed AbuJarour

13.1.2009

Journal Club:On the Provenance of Non-Answers to Queries over Extracted Data, J. Huang, T. Chen, A. Doan, and J. Naughton, VLDB 2008Alexander Albrecht
20.1.2009Journal Club: Selected Papers from CIDR 2009 (planned)
27.1.2009t.b.d.
3.2.2009t.b.d.

Maik Taubert: Parallelisierung von Graphduplikaterkennung

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.