Partitioning Strategy Selection for In-Memory Graph Pattern Matching on Multiprocessor Systems

Alexander KrauseAlexander Krause, Thomas KissingerThomas Kissinger, Dirk HabichDirk Habich, Hannes VoigtHannes Voigt, Wolfgang LehnerWolfgang Lehner

Download

Alexander Krause, Thomas Kissinger, Dirk Habich, Hannes Voigt, Wolfgang Lehner
Partitioning Strategy Selection for In-Memory Graph Pattern Matching on Multiprocessor Systems
23rd International Conference on Parallel and Distributed Computing, Santiago de Compostela, Spain, to appear

Details
Bibtex

KurzfassungAbstract
Pattern matching on large graphs is the foundation for a variety of application domains. The continuously increasing size of the underlying graphs requires highly parallel in-memory graph processing engines that need to consider non-uniform memory access (NUMA) and concurrency issues to scale up on modern multiprocessor systems. To tackle these aspects, a fine-grained graph partitioning becomes increasingly important. Hence, we present a classification of graph partitioning strategies and evaluate representative algorithms on medium and large-scale NUMA systems in this paper. As a scalable pattern matching processing infrastructure, we leverage a data-oriented architecture that preserves data locality and minimizes concurrency-related bottlenecks on NUMA systems. Our in-depth evaluation reveals that the optimal partitioning strategy depends on a variety of factors and consequently, we derive a set of indicators for selecting the optimal partitioning strategy suitable for a given graph and workload.
Projekt:Project: HAEC B08
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{KKHVL2017,
  author    = {Alexander Krause and Thomas Kissinger and Dirk Habich and Hannes
               Voigt and Wolfgang Lehner},
  title     = {Partitioning Strategy Selection for In-Memory Graph Pattern
               Matching on Multiprocessor Systems},
  booktitle = {23rd International Conference on Parallel and Distributed
               Computing, Santiago de Compostela, Spain},
  year      = {2017},
  month     = {August}
}