Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Implementation and Evaluation of Graph Isomorphism Algorithms for RDF-Graphs
Organization Unit
Authors
  • Daniel Baggenstos
Supervisors
  • Abraham Bernstein
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Date 2006
Abstract Text This thesis introduces similarity measures to be used by comparing XML workflows and RDF or OWL structures. These structures are accessed and converted into a generic graph representation. Two graphs are compared by a measure to conclude in a single value indicating the similarity of the graphs. Similarity is calculated by two different similarity measures, the graph isomorphism measure and the subgraph isomorphism measure. The graph isomorphism measure detects structurally identical graphs and calculates the similarity upon the nearness of the node labels. Structurally different graphs are compared by the subgraph isomorphism measure to find matching parts. The size and the label similarity of the nodes of a matched part contribute to its similarity based upon the compared graphs. The highest similarity value of all parts is defined to be the similarity of the two graphs. Performance improvements were developed and implemented which led to a decreasing runtime. Further improvements were analyzed and proposed to be implemented at a later date.
Zusammenfassung Diese Diplomarbeit praesentiert Aehnlichkeitsmessungen zwischen XML workflows und RDF oder OWL Strukturen. Diese Strukturen werden in generische Graphen konvertiert, welche dann von den Massen verglichen werden. Die Masse liefern einen Aehnlichkeitswert zurueck. Die zwei implementierten Masse heissen Graph Isomorphism Measure und Subgraph Isomorphism Measure. Das Graph Isomorphism Measure vergleicht zwei strukturell identische Graphen und liefert einen Aehnlichkeitswert anhand der Aehnlichkeit der Knotenbeschriftungen. Das Subgraph Isomorphism Measure berechnet den groessten Subgraphen der in zwei strukturell verschiedenen Graphen vorhanden ist. Die groesse und die Aehnlichkeit der Knotenbeschriftungen des groessten Subgraphen bestimmen die Aehnlichkeit der beiden Graphen. Verbesserungen bezueglich der Performance der Masse wurden im Verlauf von dieser Arbeit implementiert und getestet. Weitere Verbesserungen wurden analysiert und zur Implementation zu einem spaeteren Zeitpunkt vorgeschlagen.
PDF File Download
Export BibTeX