News

Graph-structured data is found in various domains such as social networks, websites, and recommendation networks. To analyze large graphs and gain high-level insights, distributed graph processing frameworks such as Spark/GraphX and Giraph have been established. For distributed processing, the graph needs to be split into multiple partitions, while the cut size and balancing of the partitions need to be optimized. This problem is known as graph partitioning.

In this talk, I will summarize recent advances of graph partitioning and introduce important new concepts that have been developed in my group. First, two novel techniques that reduce the memory footprint of graph partitioning while maintaining a high partitioning quality: Hybrid Edge Partitioning and Two-Phase Streaming. Second, EASE, a framework for optimizing the choice of partitioning technique for a given graph and processing algorithm. EASE is based on machine learning and achieves better performance than a manual partitioner selection based on heuristics. Finally, I will provide an outlook on open problems.