HUGS – A Lightweight Graph Partitioning Approach

Talk by Alexander Krause

Location: APB 3027
Start: 8. June 2016 at 2:50 pm
End: 8. June 2016 at 3:50 pm
Research group: Knowledge-Based Systems
Event series: KBS Seminar
iCal

The growing interest in graph data lead to increasingly more research in the field of graph data management and graph analytics. Nowadays, even large graphs of up to a size of billions of vertices and edges fit into main memory of big modern multisocket machines, making them a first-grade platform for graph management and graph analytics. High performance data management solutions have to be aware of the NUMA properties of such big machines. A data-oriented architecture (DORA) is a particular solution to that. However, it requires partitioning the data in a way such that inter-partition communication can be avoided.

Graph partitioning is a long studied problem and state-of-the-art solutions, such as multilevel k-way partitioning and recursive bisection achieve good results in feasible time. Integrating such solution is a rather difficult task, though. In this paper, we present a more lightweight approach called HUGS. The key idea of HUGS is to reuse the BFS routine present in a graph data management system anyway, since it is the foundation of many analytical graph algorithms. HUGS is not meant to produce a good general-purpose graph partitioning but good runtimes of BFS graph traversals such as reachability queries on DORA systems. In our experiments HUGS showed capable of finding good graph partitionings faster than state-of-the-art approaches. The partitioning found by HUGS also showed shorter runtimes for reachability queries.