Graph partitioning is an important challenging problem when performing computation tasks over large distributed graphs;the reason is that a good partitioning leads to faster computations. In this work, we first introd...
详细信息
ISBN:
(纸本)9781479956661
Graph partitioning is an important challenging problem when performing computation tasks over large distributed graphs;the reason is that a good partitioning leads to faster computations. In this work, we first introduce a new heuristic for streaming partitioning and show that it outperforms the state-of-the-art heuristics for streaming partitioning, leading to exact balance and lower cut. Secondly, we introduce the partialrestreamingpartitioning which is a hybrid streaming model allowing only several portions of the graph to be restreamed while the rest is to be partitioned on a single pass of the data stream. We show that our method yields partitions of similar quality than those provided by methods restreaming the whole graph (e.g ReLDG, ReFENNEL), while incurring lower cost in running time and memory since only several portions of the graph will be restreamed.
暂无评论