Graph division method for distributed graph calculation

Abstract

The invention provides a graph division method for distributed graph calculation in order to solve the technical problem that expenditure is excessively large when graph division is performed for large-scale graph calculation through an existing graph division method. According to the method, based on an open source framework PowerLyra, sides of graph data as input are scattered to all nodes according to target point hashing first, then all the nodes synchronously and concurrently process the sides distributed to themselves on the distributed framework, and a corresponding distributed algorithm is executed according to need. Through the method, the concept of ''package'' is proposed, wherein a package refers to a set of part of the sides with high locality, and the maximum value of the package can be modified; data locality characteristics are introduced into a metering standard of graph division through the package, so that divided sub-graphs have locality, the data locality principleis fully utilized, and the number of image vertexes of vertexes is effectively reduced; and meanwhile, load balance among the nodes is guaranteed, communication expenditure in a distributed system isreduced, processing efficiency of large-scale graph relevant applications is improved, and the performance of distributed graph calculation is improved.

Description

technical field [0001] The invention belongs to the field of distributed graph computing, in particular to a graph segmentation method for distributed graph computing. Background technique [0002] There are currently many distributed graph computing frameworks developed around the world, mainly including two parts: graph partitioning and graph computing. Graph partitioning refers to distributing large-scale graph data to each node in the cluster according to a certain strategy, and the graph computing part refers to performing distributed operations on the graph according to the needs of practical applications. [0003] In the early days, there was PowerGraph from Carnegie University, which introduced graph division from edge segmentation to the era of point segmentation. Before this, the principle of graph partitioning is that each point only exists on one node, and all edges related to this point are stored on this node, and each edge will be stored twice. In practical ...

AI Technical Summary

Problems solved by technology

[0006] Aiming at the technical problem that the existing graph segmentation method is too expensive for large-scale graph calculation, the present invention provides a distributed The graph segmentation method of graph computing, referred to as the TopoX partition method. The TopoX partition method is based on the open source framework PowerLyra. First, the input graph data is distributed to each node, and input from each node to the entire distributed framework for processing.

Images