Article in Proceedings INPROC-2016-13

BibliographyMayer, Christian; Tariq, Muhammad Adnan; Li, Chen; Rothermel, Kurt: GrapH: Heterogeneity-Aware Graph Computation with Adaptive Partitioning.
In: Proceedings of the 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS).
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 118-128, english.
IEEE, June 30, 2016.
DOI: 10.1109/ICDCS.2016.92; ISSN: 1063-6927.
Article in Proceedings (Conference Paper).
CorporationInternational Conference on Distributed Computing Systems (ICDCS)
CR-SchemaC.2.4 (Distributed Systems)
Keywordscloud computing; data analysis; GrapH; GraphX; PowerGraph; Pregel; adaptive edge migration strategy; adaptive partitioning; data access locality; data analytics; diverse vertex traffic; expensive network links; graph vertices; graph-structured data; heterogeneity-aware graph computation; heterogeneous network; specialized graph partitioning algorithms; suboptimal partitioning decisions; vertex-centric graph processing; vertex-cut graph partitioning; Automata; Computational modeling; Data analysis; Distributed databases; Heuristic algorithms; Mirrors; Partitioning algorithms
Abstract

Vertex-centric graph processing systems such as Pregel, PowerGraph, or GraphX recently gained popularity due to their superior performance of data analytics on graph-structured data. These systems exploit the graph structure to improve data access locality during computation, making use of specialized graph partitioning algorithms. Recent partitioning techniques assume a uniform and constant amount of data exchanged between graph vertices (i.e., uniform vertex traffic) and homogeneous underlying network costs. However, in real-world scenarios vertex traffic and network costs are heterogeneous. This leads to suboptimal partitioning decisions and inefficient graph processing. To this end, we designed GrapH, the first graph processing system using vertex-cut graph partitioning that considers both, diverse vertex traffic and heterogeneous network, to minimize overall communication costs. The main idea is to avoid frequent communication over expensive network links using an adaptive edge migration strategy. Our evaluations show an improvement of 60% in communication costs compared to state-of-the-art partitioning approaches.

Full text and
other links
PDF (541155 Bytes)
The original publication is available at IEEE Xplore
Copyright© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Entry dateApril 29, 2016
   Publ. Department   Publ. Institute   Publ. Computer Science