zur Startseite


Distributed Big Graph Processing of Localized Queries
Betreuer Dr. rer. nat. Christian Mayer
Prüfer Prof. Dr. rer. nat. Dr. h. c. Kurt Rothermel

The trend for Big Data analytics continues to attract researchers in academia and industry, to find feasible
solutions for the challenges introduced by processing huge data sets. Large companies such as
Google, Facebook andYahoo are seeking for data analysts and statisticians that are able to extract value
out of web, user or financial data.

In this thesis, we focus on distributed graph processing of billion-scale graph data sets such as the Web
graph, Social networks, and biological cellular networks. In order to be able to process these large-scale,
interconnected data sets, graph processing systems emerged in recent years [2]. More specifically, we
are interested in the problem of concurrent execution of multiple graph algorithms (denoted as queries)
with local scope on the shared graph structure [1, 3]. Examples are multiple shortest path queries on
the road network, localized PageRank queries on the web graph, and random walker based queries for
social simulations.

The goals and tasks of this thesis are the following.

• Extend an existing in-house distributed graph processing system for concurrent query analysis.

• Evaluate different partitioning algorithms on the graph system and compare it with existing graph systems.

• Document results in a written report and present them in the colloquium of the department of Distributed Systems (German or English).

Requirements: The student should have a good algorithmic comprehension, especially in the area of
distributed algorithms. Moreover, good programming skills in Java are required for implementing and
deploying the system on a computing cluster.

[1] Ayush Dubey, Greg D Hill, Robert Escriva, and Emin Gün Sirer. Weaver: A high-performance, transactional graph
database based on refinable timestamps. Proceedings of the VLDB Endowment, 9(11), 2016.
[2] Robert Ryan McCune, Tim Weninger, and Greg Madey. Thinking like a vertex: a survey of vertex-centric frameworks for
large-scale distributed graph processing. ACM Computing Surveys (CSUR), 48(2):25, 2015.
[3] J. Xue, Z. Yang, S. Hou, and Y. Dai. Processing concurrent graph analytics with decoupled computation model. IEEE
Transactions on Computers, PP(99):1–1, 2016.

announcement as pdf