Graph vertex parallel recoding method based on large synchronization model in network system

Abstract

The invention discloses a graph vertex parallel recoding method based on a large synchronization model in a network system. The method comprises the steps that each task transmits a vertex Id of an input graph to an out-degree vertex, counts the number of respective input vertexes, and writes the number into a total synchronization directory; each task updates an original vertex Id according to the number of input vertexes of each task recorded by the total synchronization directory in a progressive increase manner, establishes new and old Id mapping at the same time, then establishes an inputvertex set of each vertex according to a received message, and finally performs reverse sending according to the input vertex set by taking the new Id as a message value; and each vertex is mapped according to the new and old vertexes Id, and the received new vertexes Id are summarized into a new output edge set. According to the method, the problems of storage resource waste, low-efficiency calculation and the like caused by vertex irregular coding can be avoided. Meanwhile, the structural relationship of the original graph is not influenced, and the method has wide practical value and application prospect in the technical field of graph calculation.

Description

technical field [0001] The invention belongs to the technical field of computers, and in particular relates to a graph vertex recoding method based on a large synchronization model in a parallel environment. Background technique [0002] In recent years, graph computing has been increasingly used in social relational computing, web search, natural language processing, machine learning, and recommendation systems. As the scale and complexity of graph datasets continue to grow, how to design efficient graph computing models for distributed environments has attracted more and more attention. In response to this problem, Google proposed the Pregel model, which draws on the large synchronous computing and communication ideas in the BSP (Bulk Synchronous Parallel, BSP) model, and proposes "vertex-centric", expressing the vertex calculation as a series of supersteps (super-step), in each super-step calculation, each vertex receives the message sent by the previous super-step, uses...

AI Technical Summary

Problems solved by technology

[0004] Purpose of the invention: In order to overcome the deficiencies in the prior art, the present invention provides a parallel recoding method for graph vertices based on a large synchronization model in a network system, so that the original input graph vertex Id has disordered order, missing points and coding discontinuity In the scenario of such problems, it can be re-encoded into an ordered and continuous set of vertex Ids without affecting the structural relationship of the original graph, avoiding the waste of storage resources and inefficient calculations caused by irregular vertex encoding. Directed (undirected) graph with or without weights

Images