ParSeMiS - the Parallel and Sequential Graph Mining Suite (ParSeMiS)
Internally funded project
Acronym: ParSeMiS
Start date : 01.05.2006
End date : 31.12.2010
Project details
Scientific Abstract
Die Arbeitsgruppe ParSeMiS (Parallele und Sequenzielle Graph Mining Suite) beschäftigt sich mit der Suche nach häufigen interessanten Strukturen in Graphdatenbanken; ein Forschungsgebiet, das in den letzten Jahren sehr reges Interesse findet. Da viele Forschungs- und Wirtschaftsdaten in strukturierter Form erfasst werden können, bietet sich die Speicherung komplexer Zusammenhänge in Form von allgemeinen oder speziellen Graphen an.
Diese meist unüberschaubaren Datenmengen sind nur schwer mit Hand und Auge zu erfassen, so dass Algorithmen zur Entdeckung interessanter Korrelationen unabdingbar sind. Da deren Entdeckung in Graphen im Allgemeinen aufwändig ist (NP-vollständig), ist die Suche nach parallelen und spezialisierten Algorithmen und Heuristiken notwendig, die den benötigen Rechenzeit- und Speicheranforderungen auch bei immer größer werdenden Datenmengen gewachsen sind.
Das Ziel dieses Projektes ist es, ein effizientes und flexibles Werkzeug zur Suche in beliebigen Graphdaten bereitzustellen, um sowohl die Einbindung in neue Anwendungsgebiete als auch die Entwicklung neuer Suchverfahren zu beschleunigen und zu vereinfachen.
Aufbauend auf den Ergebnissen des Projekts ParMol2 wurden 2006/2007 folgende Ziele erreicht:
- Restrukturierung und Neudesign der gewachsenen ParMol-Strukturen zu einer flexiblen Graphbibiliothek.
- Ergänzung des objekt-orientierten Graphdesigns zu kompakteren, zur Parallelisierung besser geeigneten Datenstrukturen.
- Überführung und Zerlegung der Algorithmen gSpan und Gaston in die neuen Strukturen und Einbau von Erweiterungen für das aktuelle Anwendungsgebiet ”Prozedurale Abstraktion”.
- Entwurf und Implementierung eines neuen Algorithmus zur Suche in gerichteten azyklischen Graphen (DAGs) als Spezialisierung für die Prozedurale Abstraktion.
- Implementierung einer angepassten grafischen Anzeige für DAGs.
Im Jahr 2008 wurden folgende Ziele erreicht:
- Dokumentation und Veröffentlichung der Sourcen zur Verbreitung des Projekts,
- Implementierung einer angepassten graphischen Anzeige für DAGs,
- Begin der Erneuerung der graphischen Oberfläche und
- Erweiterung der Cluster-Verteilung zur Nutzung aller Kerne bei Bündeln aus Mehrkernrechnern.
Im Jahr 2009 wurden folgende Ziele angegangen:
- Beschleunigung der Suche mit einbettungs-bassierter Häufigkeit: Indem auf die zum Pruning benötigten Eigenschaften des Maximalen-Cliquen-Test intensiver eingegangen wurde, konnte gerade in dem für Anwendungen interessanten Bereich von niedrigen Häufigkeiten eine hohe Beschleunigung erreicht werden. Dies wird durch eine frühzeitige Erkennung im NP-vollständigen Test ermöglicht, die feststellt, ob ein überhaupt noch Fragment noch häufig vorhanden sein kann.
- Verbesserte Verteilung für Mehrkern-Cluster-Architekturen: Hier wurde und wird untersucht, wie sich die gemeinsame Positionierung verschiedener Threads im selben realen Speicher zur Beschleunigung der parallelen Suche ausnutzen lässt.
Im Jahr 2010 wurden die verteilten Stack-Implementierungen auch für andere Algorithmen und Daten getestet.
Involved:
Michael Philippsen
Project Leader
Marc Wörlein
Project Member
Alexander Dreweke
Project Member
Tobias Werth
Project Member