A general purpose local search based pattern matching framework

OData support
Dr. Horváth Ákos
Department of Measurement and Information Systems

Model-driven software development tasks involve creation of graph-like models, which store facts and parameters about the system under design. Developers make use of this representation when processing the models, and apply the contained information. The ultimate goal of the development process it to produce executable code, which may be preceded by several intermediate steps.

A frequent operation executed on a models can be search, which means an exploration of elements, in other words a submodel, that comply with a set of constraints. Other typical operations include search as a subtask, such as transformation, which derives a new representation of the model, or generates executable source code. Well-formedness validation also based on search, for it checks whether the model is valid in terms of the rules of the modeling language.

In this thesis I applied graph pattern matching as the underlying technique to find submodels. Generally, graph pattern matching is a complex problem, however, different approaches are commonly used to solve it. One of them is the local search-based pattern matching that finds all matches by starting the search from specified model elements. If the search plan is optimal, this technique is highly efficient. However, this is determined only by the structure of the model on which the search is performed.

During my work I adapted and implemented a local search-based pattern matching algorithm, which uses the statistics of the underlying model to calculate the search plan. I created two versions of search execution runtimes: a single-threaded, and a parallel. In this thesis I introduce the main ideas and key steps of the algorithm, as well as the peculiarity of the implementation. I also integrated the completed software components to the open-source \eiq framework.

I provide assessment results in order to show the scalability of the proposed solution. For this purpose I carried out performance comparison for both pattern matching runtimes. Additionally I evaluated the solution with respect to the already existing, incremental pattern matcher algorithm of \eiq. Finally, the applicability of the algorithm is discussed in case of different pattern matching scenarios. According to the results, the local search-based pattern matching technique is preferable in cases when tasks require only a single run, or the environment is memory constrained.


Please sign in to download the files of this thesis.