Striping of directed graphs and nodes with improved functionality

摘要

Embodiments are disclosed for striping a directed graph, e.g., a social graph, so as to efficiently perform an operation to each node in the directed graph. At least some of the embodiments can select first and second sets of nodes from the directed graph to form first and second stripes. The first and second sets of nodes are selected, for example, based on available computing resources. First and second intermediate results can be generated by performing the operation to each node of the first and the second stripes, respectively. The operation iteratively performs a superstep. The first and the second intermediate results are combined to form a collective result as an output of the superstep.

主权项

1. A method for striping a directed graph, comprising:
selecting a first set of nodes from the directed graph to organize a first stripe, wherein the first stripe includes a first set of edges to connect the first set of nodes; selecting a second set of nodes from the directed graph to organize a second stripe, wherein the second stripe includes a second set of edges to connect the second set of nodes, wherein the first and second sets of nodes are selected at least based on computing resources allocated to perform an operation on at least a portion of the directed graph, the operation iteratively performing a superstep, wherein the superstep performs the operation for each node of the directed graph in the stripes; generating a first intermediate result by performing the operation for each node of the first set of nodes, wherein the operation causes an interaction between multiple nodes of the first set of nodes, wherein generating the first intermediate result consumes a first amount of computing resources; storing the first intermediate result; generating a second intermediate result by performing the operation for each node of the second set of nodes, wherein generating the second intermediate result consumes a second amount of computing resources; storing the second intermediate result; generating a collective result at least based on the first intermediate result and the second intermediate result; and transmitting the collective result as an output of the superstep; updating a value of the directed graph based on the output of the superstep.