Patent Document ID: 9672557
Application ID: 14052584
Patent Status: 1

Claim One:
1. A computer-executable method for optimizing a recommendation computation, comprising: obtaining, from a storage device, a bipartite graph comprising a disjoint first set of vertices and second set of vertices; performing, by a set of processors, a first graph traversal from the first set of vertices to the second set of vertices, which involves: allocating only the first set of vertices among the set of processors, which further comprises assigning a first disjoint subset of the first set of vertices exclusively to a respective processor, wherein assigning the first disjoint subset further comprises: estimating a maximum number of vertices assigned to each processor according to a total number of vertices in the first set divided by a total number of processors; and assigning the first set of vertices among the set of processors based on the estimated maximum number; and traversing, by the respective processor, the graph from the first disjoint subset of vertices assigned to the respective processor to a first destination subset of the second set of vertices; performing, by the set of processors, a second graph traversal from the second set of vertices to the first set of vertices, which involves: allocating only the second set of vertices among the set of processors, which involves assigning a second disjoint subset of the second set of vertices exclusively to the same respective processor in the set of processors: wherein the second disjoint subset of vertices does not have vertices in common with the first disjoint subset ; and wherein assigning the second disjoint subset of vertices is based on a total number of vertices in the second disjoint subset of vertices divided by the total number of processors; selecting, from the second disjoint subset of vertices assigned to the respective processor, a frontier subset of vertices; and traversing, by the respective processor, the graph from the frontier subset of vertices selected for the respective processor to a second destination subset of the first set of vertices associated with any of the frontier subset of vertices by one or more edges of the bipartite graph; performing, by the set of processors, a third graph traversal from the first set of vertices to the second set of vertices, which involves: allocating only the first set of vertices among the set of processors, which further comprises assigning a third disjoint subset of the first set of vertices exclusively to the same respective processor: wherein the third disjoint subset of vertices does not have vertices in common with the second disjoint subset; and wherein assigning the third disjoint subset of vertices is based on a total number of vertices in the third disjoint subset of vertices divided by the total number of processors; and traversing, by the respective processor, the graph from the third disjoint subset of vertices assigned to the respective processor to a third destination subset of the second set of vertices; and generating a recommendation based at least on a count of the third destination subset of the second set of vertices.