Congratulations to Angen Zheng, for his poster: Skew-Resistant Graph Partitioning was recently accepted by ICDE2017

Title: Skew-Resistant Graph Partitioning
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.