Logo der Fachhochschule Nordwestschweiz
De
Standorte und KontaktBibliothek FHNWKarriere an der FHNWMedien

      Logo der Fachhochschule Nordwestschweiz
      De
      Standorte und KontaktBibliothek FHNWKarriere an der FHNWMedien

      Development of a Graph Matching Toolkit

      Entwicklung einer benutzerfreundlichen Software für Graph Matching

      Graphen sind die mächtigsten und flexibelsten Datenstrukturen, die in der Informatik Anwendung finden. Während der quantitative Vergleich von Vektoren oder Zeichenketten trivial ist, ist der Vergleich von Graphen, respektive die Distanzberechnung zwischen Graphen (bekannt als "Graph Matching"), ein schwieriges Problem. Tatsächlich existieren zur exakten Lösung des Graph-Matching-Problems nur exponentielle Algorithmen. Der Verantwortliche dieses Projektes hat in der Vergangenheit mehrere approximative Verfahren für das Graph-Matching-Problem entwickelt. Obschon die Algorithmen zur Graph-Distanz- Berechnung zur Verfügung stehen, besteht kein benutzerfreundliches Framework, das die Anwendung dieser Verfahren für eine breitere Öffentlichkeit ermöglicht.

      Das primäre Ziel dieses Projektes ist es, basierend auf den bestehenden Algorithmen eine benutzer-freundliche Software für flexibles Graph Matching zu entwickeln.

      Aufgrund der Tatsache, dass Graphen Attribute und Beziehungen gleichzeitig darstellen können, besitzen Graphen vielfältige Anwendungen in der Wissenschaft und Industrie. In der Bio- und Chemoinformatik werden Graphen als Datenstruktur zum Beispiel in der Web-Content-Analyse und im Data Mining, in der Bildanalyse und Bildklassifikation oder in der Netzwerkanalyse verwendet.

      Distanzberechnungen zwischen zwei Objekten in den oben genannten Anwendungsgebieten sind ein häufiges Problem. Im Gegensatz zu Vektorräumen, in denen die Euklidische Distanz als "Gold-Standard" verwendet wird, existiert für Graphen kein Standardmodell zur Distanzberechnung. Die Editierdistanz von Graphen ist eine der flexibelsten und mächtigsten Werkzeuge zur Graphdistanzberechnung. Allerdings weist die Berechnung der Editierdistanz von Graphen eine exponentielle Laufzeit auf, was deren Anwendung massiv einschränkt. Die in diesem Projekt verwendeten Algorithmen zur Approximation der Editierdistanz basieren auf Zuordnungsproblemen, für deren Lösung verschiedene sehr schnelle Verfahren existieren (z.B. der Algorithmus von Kuhn-Munkres oder das Verfahren von Edmonds-Karp).

      Hasler Stiftung

      hsw_iwi_systemsengineering_teaserhsw_iwi_systemsengineering_projekt