On Improvement Of Distributed FENNEL:streaming Graph Partitioning For Massive Graphs

Graph partitioning is one of the most important tasks to enable efficient solving of a wide range of computational tasks and querying over large-scale graph data. When the scale of graph is s mall, static graph partition algorithm(such as METIS) can work efficiently and acquire low edge cut ratio; But the graph data generated by applications keeps growing rapidly, static graph partitioning is no longer suitable for such scenario,especially when handling graphs up to more than 10 million's scale, because of it's low processing speed and poor scalability.The appearance of streaming graph partitioning solved this problem. FENNEL introduces an unifying framework for many current graph partitioning algorithms, it's edge cut ratio is better than previous streaming approaches, and even close to the de-facto standard offline software METIS, while its processing speed is faster. However, FENNEL is a serial algorithm, to improve its parallelism while minimizing the impact on edge cut ratio now rises as a major challenge.Based on theoretical analysis of the FENNEL's serial model and its concurrency mechanism, this research proposes a distributed partitioning design and a multi-tiered vertex-broadcasting model for the partitioning workers. Experimental results show that, if the graph stream isn't sorted, just like its natural form, the graph partitioning with clustered workers will gain a substantial speedup, yet the negative impact on the graph edge cut ratio is negligible. The observation on various types of graphs reveals that,natural graph streams with non-uniform vertex degree distribution will affect the underlying inter-worker data transfer, since the size of data packets may change drastically from time to time. And the test on BFS-sorted graph stream is proved to be almost the worst case for distributed streaming graph partitioning, because it will significantly increase edge cut ratio.