Artikel in Tagungsband INPROC-2016-13

Bibliograph.
Daten
Mayer, 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).
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik.
S. 118-128, englisch.
IEEE, 30. Juni 2016.
DOI: 10.1109/ICDCS.2016.92; ISSN: 1063-6927.
Artikel in Tagungsband (Konferenz-Beitrag).
KörperschaftInternational Conference on Distributed Computing Systems (ICDCS)
CR-Klassif.C.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
Kurzfassung

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.

Volltext und
andere 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.
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
Eingabedatum29. April 2016
   Publ. Abteilung   Publ. Institut   Publ. Informatik