Welcome to the ADMT Publication Server

Skew-Resistant Graph Partitioning (Poster)

DocUID: 2017-002 Full Text: PDF

Author: Angen Zheng, Alexandros Labrinidis, Christos Faloutsos

Abstract: Large graph datasets have caused renewed interest for graph partitioning. However, existing well-studied graph partitioners often assume that vertices of the graph are always active during the computation, which may lead to time-varying skewness for traversal-style graph workloads, like Breadth First Search, since they only explore part of the graph in each superstep. Additionally, existing solutions do not consider what vertices each partition will have; as a result, high-degree vertices may be concentrated into a few partitions, causing imbalance. Towards this, we introduce the idea of skew-resistant graph partitioning, where the objective is to create an initial partitioning that will “hold well” over time without suffering from skewness. Skew-resistant graph partitioning tries to mitigate skewness by taking the characteristics of both the target workload and the graph structure into consideration.

Keywords: Skew-Resistant, Graph Partitioning, Distributed Graph Computing

Published In: 33nd IEEE International Conference on Data Engineering

Pages: 151-154

Year Published: 2017

Project: Planar,  Paragon,  AragonLB,  ARGO Subject Area: Graph Data Management

Publication Type: Conference Paper

Sponsor: NSF CBET-1250171, NSF CBET-1609120

Citation:Text Latex BibTex XML Angen Zheng, Alexandros Labrinidis, and Christos Faloutsos. Skew-Resistant Graph Partitioning (Poster). 33nd IEEE International Conference on Data Engineering. 151-154. 2017.