Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Application of Efficient Tree Similarity Algorithms on Graphs
Organization Unit
Authors
  • Alexander Bucher
Supervisors
  • Abraham Bernstein
  • Cathrin Weiss
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Date 2008
Abstract Text Abstract for the diploma thesis “Application of Efficient Tree Similarity Algorithms on Graphs” written by Alexander Bucher This thesis presents subgraph indexing, a novel approach to query graph based datasets. To make subgraph indexing efficient on complex queries in large graph based datasets, the original graph is transformed into multiple directed subgraphs. Vector representations of these subgraphs are then stored in a tree structure. To answer a query, the subgraph representing the query is created and vectors containing similar subgraphs are retrieved from the stored data. Out of these vectors, the ones containing a valid result are filtered out and their results are presented. In the evaluation section it is shown that subgraph indexing can answer complex queries in large databases faster than some comparative approaches.
Zusammenfassung Zusammenfassung für die Diplomarbeit “Application of Efficient Tree Similarity Algorithms on Graphs” erstellt von Alexander Bucher Diese Arbeit präsentiert „subgraph indexing“, eine neuartige Methode um Graph?basierte Daten abzufragen. Um effizient komplexe Anfragen in umfangreichen, Graph?basierten Datensätzen zu tätigen, wird der ursprüngliche Graph in mehrere Subgraphen umgeformt. Diese Subgraphen werden dann als Vektoren in einer Baum?Struktur gespeichert. Um eine Anfrage zu beantworten wird ein Subgraph geformt, welcher die Anfrage darstellt. Dann werden Vektoren, welche ähnlich Subgraphen beinhalten, zurückgegeben. Diese Vektoren werden dann auf richtige Antworten zur Anfrage geprüft und die richtigen Resultate ausgegeben. Die Evaluation zeigt, dass unsere „subgraph indexing“ Methode für komplexe Anfragen in umfangreichen datensetzen schnellere Daten liefert als herkömmliche, vergleichbare Methoden.
Export BibTeX