Graph data processing method applied to distributed computing node cluster and medium

Abstract

The embodiment of the invention provides a graph data processing method, which comprises the following steps of: S1, obtaining graph data containing a plurality of vertexes, sorting the vertexes according to the descending order of the vertexes, and taking a sorting serial number as a first resorting ID; S2, sequentially distributing the vertexes of the graph data to each distributed computing node in a distributed computing node cluster in a polling manner according to the first reordering ID and preset granularity; S3, traversing the obtained partial graph data by the computational nodes byusing a hybrid BFS algorithm, and obtaining a local next-layer active vertex set by each computational node after each layer is traversed; S4, after each layer is traversed, performing loop communication between adjacent computing nodes to transmit a local next-layer active vertex set, and determining the compression mode of the local next-layer active vertex set to be transmitted this time beforethe local next-layer active vertex set is transmitted after partial-layer traversal. According to the invention, vertex IDs are subjected to reordering, data compression and loop communication through the out-degree of the vertexes, and the communication efficiency is improved.

Description

technical field [0001] The present invention relates to the field of graph data processing, in particular to a distributed graph processing method based on breadth-first search, and more specifically to a graph data processing method and medium applied to distributed computing node clusters. Background technique [0002] Graph is a mathematical object representing the relationship between elements (people, intersections, documents, etc.). Many application scenarios in real life need to be represented by graph data structures, such as protein structure prediction, shortest time path, scientific literature citation relationship, social network analysis, etc. [0003] Breadth First Search (BFS algorithm for short) is a classic graph traversal algorithm. The traditional BFS algorithm adopts a top-down (Top-down) idea to find child nodes through parent nodes. The application of BFS algorithm has the typical characteristics of data-intensive applications such as poor data locali...

AI Technical Summary

Problems solved by technology

[0005] However, the average communication distance of these existing implementation methods is large, and with the increase of the number of communication nodes and the amount of communication data, the communication overhead increases exponentially

This leads to high network communication overhead when the BFS algorithm is applied on a distributed cluster, its performance is seriously affected, and its scalability is not good

Images