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: 33rd IEEE International Conference on Data Engineering
Pages: 151-154
Year Published: 2017
Project: ARGO, AragonLB, Paragon, Planar Subject Area: Graph Data Management
Publication Type: Conference Paper
Sponsor: NSF CBET-1609120, NSF CBET-1250171