HUGS - A Lightweight Graph Partitioning Approach

Alexander KrauseAlexander Krause, Hannes Voigt, Wolfgang LehnerHannes Voigt, Wolfgang Lehner

Download

Alexander Krause, Hannes Voigt, Wolfgang Lehner
HUGS - A Lightweight Graph Partitioning Approach
Grundlagen von Datenbanken Workshop 2016, May 2016

Details
Bibtex

KurzfassungAbstract
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: Knowledge SystemsKnowledge-Based Systems

@inproceedings{KH2016,
  author    = {Alexander Krause and Hannes Voigt, Wolfgang Lehner},
  title     = {HUGS - A Lightweight Graph Partitioning Approach},
  booktitle = {Grundlagen von Datenbanken Workshop 2016},
  year      = {2016},
  month     = {May}
}