Implementation of a Subgraph Matching Algorithm - Graphmatcher

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu | Master's thesis
Ask about the availability of the thesis by sending email to the Aalto University Learning Centre oppimiskeskus@aalto.fi
Date
2017-12-11
Department
Major/Subject
Communications Engineering
Mcode
ELEC3029
Degree programme
CCIS - Master’s Programme in Computer, Communication and Information Sciences (TS2013)
Language
en
Pages
48+5
Series
Abstract
As graph databases and using graph as a data structure attract more and more interest of the industry, inevitably research towards to graphs is also accelerated by this interest. Significant amount of effort has been dedicated to graph theory related research by IT industry giants such as Google and IBM with Cayley or Facebook with GraphQL. In the domain of graph theory, Subgraph Matching is one of the basic graph problems which has always room for an improvement. Therefore, numerous methods and algorithms have been developed to produce better results for different class of input graphs, such as Ullmann's Algorithm, VF2, GraphQL, TurboISO and DualISO. In this work, I have attempted to solve a subgraph matching problem encountered in a task scheduling system for software development processes. In the same vein, problem that I was attempting to solve also touched to a scheduling problem known as Job Shop Problem. To solve both problems efficiently at one time, I have developed our subgraph matching method, Graphmatcher. It is essentially a fork of DualISO algorithm with additional functionality towards efficient solution of scheduling problems I have encountered. In the practical part of this thesis, I have given detailed information about design and implementation of Graphmatcher and task scheduler application. Also I have explained how does Graphmatcher add value into task scheduling application and what kind of effect does it make under different conditions. To prove efficiency of our method, I have written tests which use various combinations of parameters and made observations from production environment. Based on results, I claim that our method of Graphmatcher is able to solve similar problems with ease and add value into software development processes by utilizing more resources at once.
Description
Supervisor
Suomela, Jukka
Thesis advisor
Suomela, Jukka
Keywords
algorithms, subgraph isomorphism, graph pattern matching, job shop scheduling problem, optimization
Other note
Citation