Erweiterung und Parallelisierung eines Graph-Mining-Algorithmus

Student:Marc Wörlein
Title:Erweiterung und Parallelisierung eines Graph-Mining-Algorithmus
Type:diploma thesis
Advisors:Fischer, I.; Meinl, T.; Philippsen, M.
State:submitted on March 31, 2006
Prerequisits:
Topic:

Hintergrund
Die Arbeitsgruppe ParMol wurde im März 2004 gegründet. In ihrem Rahmen sollen neue Verfahren entwickelt werden, um in großen Datenbanken interessante Zusammenhänge zwischen chemischen Strukturen zu finden. Diese Zusammenhänge sollen als Molekülfragmente, d.h. in Form von Zusammenhangsgraphen dargestellt werden. Ein Anwendungsgebiet ist z.B. die in vitro Vorhersage von toxischen Seiteneffekten von Medikamentenkandidaten schon vor in vivo oder klinischen Tests. Im Gegensatz zu bisher bekannten Verfahren sollen auch ähnliche Strukturen gefunden werden, die biologisch oder chemisch die gleiche Wirkung zeigen. Um den dadurch entstehenden, deutlich höheren Rechenbedarf zu decken, werden die entwickelten Verfahren parallelisiert und so entworfen, dass sie sich auch für die Bearbeitung auf verteilten Ressourcen eignen. In Zusammenarbeit mit dem Lehrstuhl für Bioinfomatik und Maschinelles Lernen der Universität in Konstanz soll in den nächsten Jahren eine Reihe von neuen Verfahren und Methoden auf diesem Gebiet entwickelt werden.

Aufgabenstellung
In [3] wurde gezeigt, dass unter den vier verglichenen Graph-Mining-Algorithmen gSpan [1] der flexibelste Algorithmus ist, der gleichzeitig wenig Speicher verbraucht und sehr gute Laufzeiten hat. In dieser Diplomarbeit soll der bereits implemetierte gSpan daher in mehrere fuer das Projekt wichtige Richtungen erweitert werden:

  • Bisher funktioniert gSpan nur für ungerichtete Graphen. Die Implementierung soll für gerichtete Graphen erweitert werden.
  • In [2] wird die Suche nach geschlossenen Fragmenten/Subgraphen näher beschrieben. Ein Subgraph ist geschlossen, wenn es keinen zugehörigen Supergraph gibt, der in genau den gleichen Graphen der Datenbank vorkommt. Die vorliegende Implementierung von gSpan ist um dieses Konzept zu erweitern.
  • gSpan basiert auf Tiefensuche. In [4] ist eine Parallelisierung der Tiefensuche beschrieben. Diese Parallelisierung soll soweit möglich auf die Implementierung von gSpan übertragen werden. Ist eine Übertragung nicht möglich, sollen andere Vorschläge zur Parallelisierung von gSpan entwickelt werden.

Literatur
[1] Yan, X., Han, J.: gSpan: Graph–Based Substructure Pattern Mining. In: Proc. IEEE Int’l Conf. on Data Mining ICDM, Maebashi City, Japan (2002), S. 721–723
[2] Yan, X., Han, J.: Closegraph: Mining Closed Frequent Graph Patterns. In: Proc. of the 9th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, Washington, DC, USA, ACM Press (2003), S. 286–295.
[3] Wörlein, M. ; Meinl, Thorsten ; Fischer, Ingrid ; Philippsen, Michael: A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston . PKDD 2005, Porto, Portugal, 2005.
[4] Vipin Kumar and V. Nageshwara Rao. Parallel Depth–First Search. Int’l J. of Parallel Programming, 16(6):501–519, December 1987.

watermark seal