Master Thesis MSTR-2017-37

BibliographyGrunert, Jonas: Concurrent query analytics on distributed graph systems.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 37 (2017).
60 pages, english.

Large-scale graph problems, such as shortest path finding or social media graph evaluations, are an important area in computer science. In recent years, important graph applications such as PowerGraph or PowerLyra lead to a shift of paradigms of distributed graph processing systems towards processing of multiple parallel queries rather than a single global graph algorithm. Queries usually have locality in graphs, i.e. involve only a subset of the graphs vertices. Suitable partitioning and query synchronization approaches can minimize communication overhead and query latency by exploiting this locality. Additionally, partitioning algorithms must be dynamic as the number and locality of queries can change over time. Existing graph processing systems are not optimized to exploit query locality or to adapt graph partitioning at runtime. In this thesis we present Q-Graph, an open source, multitenant graph analytics system with dynamic graph repartitioning. Q-Graph's query-aware partitioning algorithm Q-Cut performs adaptive graph partitioning at runtime. Compared to static partitioning strategies, Q-Cut can exploit runtime knowledge about query locality and workload to improve partitioning dynamically. Furthermore a case study with an implementation for the shortest path problem and point search queries is presented. We present evaluations showing the performance of Q-Graph and the effectiveness of Q-Cut. Measurements show that Q-Cut improves query processing performance by up to 60% and automatically adapts partitioning on changing query workload and locality, outperforming partitioning methods using domain knowledge.

Full text and
other links
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Mayer, Christian
Entry dateMay 28, 2019
   Publ. Computer Science