ParSeMiS - die Parallele und Sequenzielle Mining Suite

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.

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.