US 10,120,956 B2 · Methods and systems for distributed computation of graph data

Abstract

Methods and systems for distributed computation of graph data permit edge collection and vertex collection, each to be partitioned among a plurality of computational units. In one embodiment, the methods employ a two-phase computational cycle, which is repeated until the computation is complete. In a first phase, processing units process each active edge and vertex by doing the following: reading their current attribute values, executing programmed computational functions, updating edge attributes and sending data messages to vertices. In a second phase, each vertex update processor processes each of its active vertices by doing the following: reading its current attribute values and received data messages, executing a programmed computational function, and updating the vertex's attribute values.

Claims20

Dependent claims

A computer-implemented method for distributed computation of a graph having one or more edges, each of the one or more edges connecting a source vertex and an endpoint vertex, the method comprising:

reading attribute values of the one or more edges by at least one edge processing unit and of the source vertices of the one or more edges by at least one vertex processing unit, the read attribute values of the one or more edges being stored in an edge list separate from a vertex list that stores the read attribute values of the source vertices of the one or more edges;
performing calculations on the read attribute values;
and
updating the attribute values of the one or more edges maintained in the edge list and of the endpoint vertices of the one or more edges maintained in the vertex list, said updating based on the performed calculations,
wherein said performing is an independent process from said updating and does not modify any of the read attribute values, and said at least one edge processing unit and said at least one vertex processing unit are computer-programmable computational devices.

2 more elements

A system for distributed computation of a graph having one or more edges, each of the one or more edges connecting a source vertex and an endpoint vertex, the system comprising:

one or more edge processing units for reading attribute values of the one or more edges;
one or more vertex processing units for reading attribute values of the source vertices of the one or more edges;
and
a graph storage unit for maintaining the attribute values of the endpoint vertices of the one or more edges, wherein the graph storage unit comprises an electronic data storage device, the read attribute values of the one or more edges are maintained in an edge list of the graph storage unit that is separate from a vertex list of the graph storage unit that stores the read attribute values of the source vertices of the one or more edges,
wherein said one or more edge processing units further perform calculations that do not modify any of the read attribute values of the one or more edges and update the attribute values of the one or more edges and of the endpoint vertices of the one or more edges based on the performed calculations, and said one or more vertex processing units further perform calculations on the attribute values of the endpoint vertices, said one or more edge processing units and said one or more vertex processing units are computer-programmable computational devices, wherein said performing calculations is an independent process from said updating.

2 more elements

Dependencies are inferred from the claim text.

Methods and systems for distributed computation of graph data

Life of this patent

Methods and systems for distributed computation of graph data

Life of this patent

Abstract

Claims20