Benchmarking scalable graph query techniques

OData support
Supervisor:
Dr. Szárnyas Gábor
Department of Measurement and Information Systems

Since the '70s, database handling typically meant the application of relational technologies. However, in the last decade many database systems appeared which are utilizing non-relational data models, including graph databases which provided a native graph storage and allowed users to run graph queries including pattern matching, traversal, and shortest path operations. At the same time, a number of graph processing systems appeared that allow users to define graph algorithms (e.g. depth-first search, PageRank) using a high-level programming interface, and execute them over a distributed cluster.

While systems in both categories have been enjoying a significant increase in popularity, many such systems are lacking performance and are therefore unable to scale for large graphs. Additionally, there is a lack of a unified theory for graph processing workloads, which could cover both graph database queries and graph analytical algorithms.

GraphBLAS is a recent initiative that aims to create an application programming interface for defining graph algorithms in the language of linear algebra.

Due to the novelty of GraphBLAS, its usability and performance need to be investigated. To this end, we used the benchmarks specified by the Linked Data Benchmark Council (LDBC).

First, thesis discusses the foundations of GraphBLAS and the LDBC benchmarks. Then, we detail the lessons learned when implementing three graph algorithms (breadth-first search, single source shortest path, and local clustering coefficient) of LDBC Graphalytics, and analyze the performance of the algorithms on a number of synthetic graphs. Finally, we discuss the applicability of the results for evaluating the graph queries of the LDBC Social Network Benchmark's Business Intelligence workload. This proves that the GraphBLAS-based building blocks can be used to design and implement both efficient graph analytical systems and graph query engines.

Downloads

Please sign in to download the files of this thesis.