Method of distributed graph loading for minimal communication and good balance via lazy materialization and directory indirection using indexed tabular representation

A method comprising at least one tracking computer of a plurality of computers:

• receiving, from each particular computer of the plurality of computers, identifiers of local graph vertices that are loaded on the particular computer for a graph, and assigning the local graph vertices to the particular computer;
• identifying a set of redundant graph vertices of the graph that are redundantly assigned to multiple computers of the plurality of computers;
• dividing the set of redundant graph vertices into subsets of a fixed amount of redundant graph vertices;
• for each subset of the fixed amount of redundant graph vertices:
• for each particular graph vertex of the subset of the fixed amount of redundant graph vertices:
• sending, to each particular computer of the multiple computers to which the particular graph vertex is assigned, an indication that the particular graph vertex is redundantly assigned;
• receiving, from each particular computer of the multiple computers, a respective count of edges that are connected to the particular graph vertex on the particular computer;
• selecting a selected computer of the multiple computers that has a highest respective count of edges for the particular graph vertex;
• indicating, to the multiple computers, that the particular graph vertex is reassigned solely to a computer of the multiple computers with a highest respective count.

A method comprising one or more iterations of:

• each tracking computer of a plurality of tracking computers:
• associating each vertex of a respective plurality of vertices of a graph to a respective participating computer of a plurality of participating computers;
• and
• sending to a master computer first data that includes:
• a count of the respective plurality of vertices associated with the respective participating computer, a count of edges originating from the respective plurality of vertices at the respective participating computer, and a count of edges terminating at the respective plurality of vertices at the respective participating computer;
• based on the first data, the master computer sending to each tracking computer of the plurality of tracking computers, for each source computer of the plurality of participating computers, second data that includes:
• an identifier of the source computer, an identifier of a destination computer of the plurality of participating computers, and a count of edges to be transferred from the source computer to the destination computer;
• based on the second data, each tracking computer of the plurality of tracking computers reassigning a subset of the respective plurality of vertices of the graph to different computers of the plurality of participating computers.

A method comprising:

• storing a first segmented array that comprises a first partial segment after a first one or more whole segments that contain a same particular amount of elements;
• storing a second segmented array that comprises a second partial segment after a second one or more whole segments that contain the same particular amount of elements;
• prepending the second one or more whole segments onto the first segmented array;
• appending the second partial segment onto the first segmented array.

One or more computer-readable non-transitory media storing instructions that, when executed by one or more processors, cause:

• by each participating computer of a plurality of computers:
• receiving a respective initial partition that contains a respective subset of edges of a plurality of edges of a graph and a respective subset of vertices of a plurality of edges of the graph;
• for each edge of the respective subset of edges, storing an intermediate representation of the edge into an edge table that resides on the participating computer;
• and
• for each vertex of the respective subset of vertices:
• storing an intermediate representation of the vertex into a vertex table that resides on the participating computer, and
• announcing that the vertex resides on the participating computer to a respective tracking computer of the plurality of computers;
• by each tracking computer of the plurality of computers, making assignments of particular vertices of the plurality of vertices of the graph to particular computers of the plurality of computers and making the assignments available to the plurality of computers;
• by the plurality of computers, transferring the particular vertices of the assignments and edges that originate at the particular vertices to the particular computers of the assignments;
• by each participating computer of the plurality of computers, storing a materialized representation of a respective balanced partition based on:
• the edge table that resides on the participating computer, the vertex table that resides on the participating computer, the vertices and the edges that were transferred to the participating computer, and the edges that were transferred to the participating computer, wherein edges stored in the materialized representation of the respective balanced partition are stored in a different format than edges stored in the edge table that resides on the participating computer.