HUGS - A Lightweight Graph Partitioning Approach

Alexander KrauseAlexander Krause, Hannes VoigtHannes Voigt, Wolfgang LehnerWolfgang Lehner

Download

Alexander Krause, Hannes Voigt, Wolfgang Lehner
HUGS - A Lightweight Graph Partitioning Approach
Proceedings of the 28th GI-Workshop Grundlagen von Datenbanken, May 2016

Details
Bibtex

KurzfassungAbstract
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 upto 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.
Projekt:Project: HAEC B08
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{KVL2016,
  author    = {Alexander Krause and Hannes Voigt and Wolfgang Lehner},
  title     = {HUGS - A Lightweight Graph Partitioning Approach},
  booktitle = {Proceedings of the 28th {GI-Workshop} Grundlagen von Datenbanken},
  year      = {2016},
  month     = {May}
}