Subgraph-isomorphism in Graph Streams Pattern Matching

Type of thesis: Bachelorarbeit / location: Leipzig / Status of thesis: Theses in progress

Graph processing has become an indispensable part of several domains of computer science, including machine learning, social network analysis, computational sciences, and others. Graphs ease the perception of the data and recognized as a valuable means to view, study, and extract the latent information. The stream processing model will enjoy the lack of a rigid database systems storage that customarily handles those duties, and will produce a real-time output nature that could benefit many real-life applications. Graph pattern matching, which is also known as subgraph matching and pattern detection has been extensively researched for static graphs, but for stream graphs, it falls like many stream problems currently as a new research area. Data streams that have relationships connecting their objects can be interpreted and handled as streamed graphs, and these graphs are evolving with each new object or event.

In previous research this issue has been tangled and a proof of concept was implemented. One algorithm of many others has been used to test the implementation. In this bachelor thesis, we want to expand the selection of available algorithms with the use of subgraph-iso morphism and to check, using the evaluation, the enhancement this streaming approach provide -or not- over the identical situation but in static graph variant.

Envisioned Tasks

  • Get familiar with Flink stream processing environment
  • Expand the implemented algorithms with subgraph isomorphism implementation,..
  • Evaluate the system with/ without the current streaming approach to prove the enhancement or discover problems


Christopher Rost

Universität Leipzig

Temporal Graph Analysis and Algorithms, Distributed Systems