The TopoX Project Topology refactorization

TopoX: Topology Refactorization for Distributed Graph Partitioning and Computation


Overview

Graph-structured computation is central to applications ranging from language processing to social networks. Natural graphs have skewed power-law distributions of vertex degrees, leading to inefficient partitioning and computation for traditional graph-parallel systems. To address this problem, we design TopoX, a distributed graph processing system that refactorizes the topology of a skewed graph to obtain a more uniform topology suitable for partitioning.

TopoX performs the fusion operation on low-degree vertices that merges a set of neighboring low-degree vertices into a super-vertex (which will be assigned to one machine) to eliminate its inner communication; and performs the fission operation on high-degree vertices that splits a high-degree vertex into a set of sibling sub-vertices (each of which will be assigned to one machine) to evenly distribute the load. TopoX designs the delta-based GAS model to further reduce communication. TopoX is implemented as a separate computation engine of PowerGraph.

Downloads

Download the source code of TopoX.

Funding

This work was supported by ...

Contact us

We welcome feedback, suggestions, patches, and so forth. Send them to ...


Last modified: 13 July, 2017 /