# US 2015/0106223 A1 · System and method for improved parallel search on bipartite graphs using dynamic vertex-to-processor mapping

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0106223 A1
- Document ID: US20150106223A1
- Status: Published application
- Kind: A1
- Application number: 14/052,584
- Filed: 2013-10-11
- Published: 2015-04-16
- Earliest claimed: 2013-10-11
- Assignees: Palo Alto Research Center Incorporated
- Applicants: Palo Alto Research Center Incorporated
- Inventors: Rong Zhou; Daniel Davies
- Web page: https://patentgrep.com/patent/US20150106223A1

## CPC

- G06Q 30/0631: {Recommending goods or services}
- G06Q 30/0282: Rating or review of business operators or products
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

One embodiment of the present invention provides a system for dynamically assigning vertices to processors to generate a recommendation for a customer. During operation, the system receives graph data with customer and product vertices and purchase edges. The system traverses the graph from a customer vertex to a set of product vertices. The system divides the set of product vertices among a set of processors. Subsequently, the system determines a set of product frontier vertices for each processor. The system traverses the graph from the set of product frontier vertices to a set of customer vertices. The system divides the set of customer vertices among a set of processors. Then, the system determines a set of customer frontier vertices for each processor. The system traverses the graph from the set of customer frontier vertices to a set of recommendable product vertices. The system generates one or more product recommendations for the customer.

## Claims

### Claim 1

A computer-executable method for dynamically assigning vertices to processors to generate a recommendation for a customer, comprising:
receiving graph data indicating vertices and edges of the graph, wherein the vertices represent customers and products and the edges represent purchases;
determining, based on the graph data, a vertex that represents the customer;
traversing the graph from the vertex representing the customer to a set of vertices representing products;
dividing the set of vertices representing products among a set of processors;
determining a set of frontier vertices representing products for each processor of the set of processors;
traversing, by the set of processors, the graph from the set of frontier vertices representing products to a set of vertices representing customers;
dividing the set of vertices representing customers among a set of processors;
determining a set of frontier vertices representing customers for each processor of the set of processors;
traversing, by the set of processors, the graph from the set of frontier vertices representing customers to a set of vertices representing recommendable products;
and
generating a product recommendation for the customer based on the set of vertices representing recommendable products.

### Claim 2 (depends on 1)

The method of claim 1, wherein dividing the set of vertices representing customers among a set of processors further comprises:
generating a bitmask MU such that MU[p], the value of the pth bit, is:
1, if a set of U→V frontier vertices for processor p is not null, where U represents the set of customers and V the set of products;
0, if a set of U→V frontier vertices for processor p is null; and
assigning frontier vertices representing customers to a processor p if MU[p] is 1.

### Claim 3 (depends on 1)

The method of claim 1, wherein dividing the set of vertices representing customers among a set of processors further comprises:
estimating a maximum number of vertices assigned to each processor according to a formula └(umax−umin+1)/P┘, wherein P is the number of processors, umax is a maximum integer identifier for verticesεU, and umin is a minimum integer identifier for verticesεU, where U represents the set of customers; and
dividing the set of vertices representing customers uniformly among the set of processors based on the estimated maximum number of vertices assigned to each processor.

### Claim 4 (depends on 1)

The method of claim 1, wherein dividing the set of vertices representing customers among a set of processors further comprises:
dividing the set of vertices representing customers non-uniformly among the set of processors.

### Claim 5 (depends on 1)

The method of claim 1, wherein dividing the set of vertices representing products among a set of processors further comprises:
generating a bitmask MV such that MV[p], the value of the pth bit, is:
1, if a set of V→U frontier vertices for processor p is not null, where V represents the set of products and U the set of customers;
0, if a set of V→U frontier vertices for processor p is null; and
assigning frontier vertices representing products to a processor p if MV[p] is 1.

### Claim 6 (depends on 1)

The method of claim 1, wherein dividing the set of vertices representing products among a set of processors further comprises:
estimating a maximum number of vertices assigned to each processor according to a formula └(vmax−vmin+1)/P┘, wherein P is the number of processors, vmax is a maximum integer identifier for verticesεV, and vmin is a minimum integer identifier for verticesεV, where V represents the set of products; and
dividing the set of vertices representing products uniformly among the set of processors based on the estimated maximum number of vertices assigned to each processor.

### Claim 7 (depends on 1)

The method of claim 1, wherein dividing the set of vertices representing products among a set of processors further comprises:
dividing the set of vertices representing products non-uniformly among the set of processors.

### Claim 8 (depends on 1)

The method of claim 1, wherein the graph is a general graph, further comprising:
dividing a set of source vertices among a set of processors;
generating a bitmask MS such that MS[p], the value of the pth bit, is:
1, if the set of frontier source vertices for processor p is not null;
0, if the set of frontier source vertices for processor p is null; and
assigning frontier source vertices representing products to a processor p if MS[p] is 1.

### Claim 9

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for dynamically assigning vertices to processors to generate a recommendation for a customer, the method comprising:
receiving graph data indicating vertices and edges of the graph, wherein the vertices represent customers and products and the edges represent purchases;
determining, based on the graph data, a vertex that represents the customer;
traversing the graph from the vertex representing the customer to a set of vertices representing products;
dividing the set of vertices representing products among a set of processors;
determining a set of frontier vertices representing products for each processor of the set of processors;
traversing, by the set of processors, the graph from the set of frontier vertices representing products to a set of vertices representing customers;
dividing the set of vertices representing customers among a set of processors;
determining a set of frontier vertices representing customers for each processor of the set of processors;
traversing, by the set of processors, the graph from the set of frontier vertices representing customers to a set of vertices representing recommendable products;
and
generating a product recommendation for the customer based on the set of vertices representing recommendable products.

### Claim 10 (depends on 9)

The computer-readable storage medium of claim 9, wherein dividing the set of vertices representing customers among a set of processors further comprises:
generating a bitmask MU such that MU[p], the value of the pth bit, is:
1, if a set of U→V frontier vertices for processor p is not null, where U represents the set of customers and V the set of products;
0, if a set of U→V frontier vertices for processor p is null; and
assigning frontier vertices representing customers to a processor p if MU[p] is 1.

### Claim 11 (depends on 9)

The computer-readable storage medium of claim 9, wherein dividing the set of vertices representing customers among a set of processors further comprises:
estimating a maximum number of vertices assigned to each processor according to a formula └(umax−umin+1)/P┘ wherein P is the number of processors, umax is a maximum integer identifier for verticesεU, and umin is a minimum integer identifier for verticesεU, where U represents the set of customers; and
dividing the set of vertices representing customers uniformly among the set of processors based on the estimated maximum number of vertices assigned to each processor.

### Claim 12 (depends on 9)

The computer-readable storage medium of claim 9, wherein dividing the set of vertices representing customers among a set of processors further comprises:
dividing the set of vertices representing customers non-uniformly among the set of processors.

### Claim 13 (depends on 9)

The computer-readable storage medium of claim 9, wherein dividing the set of vertices representing products among a set of processors further comprises:
generating a bitmask MV such that MV[p], the value of the pth bit, is:
1, if a set of V→U frontier vertices for processor p is not null, where V represents the set of products and U the set of customers;
0, if a set of V→U frontier vertices for processor p is null; and
assigning frontier vertices representing products to a processor p if MV[p] is 1.

### Claim 14 (depends on 9)

The computer-readable storage medium of claim 9, wherein dividing the set of vertices representing customers among a set of processors further comprises:
estimating a maximum number of vertices assigned to each processor according to a formula └(vmax−vmin+1)/P┘ wherein P is the number of processors, vmax is a maximum integer identifier for verticesεV, and vmin is a minimum integer identifier for verticesεV, where V represents the set of products; and
dividing the set of vertices representing products uniformly among the set of processors based on the estimated maximum number of vertices assigned to each processor.

### Claim 15 (depends on 9)

The computer-readable storage medium of claim 9, wherein dividing the set of vertices representing products among a set of processors further comprises:
dividing the set of vertices representing products non-uniformly among the set of processors.

### Claim 16 (depends on 9)

The computer-readable storage medium of claim 9, wherein the graph is a general graph, further comprising:
dividing a set of source vertices among a set of processors;
generating a bitmask MS such that MS[p], the value of the pth bit, is:
1, if the set of frontier source vertices for processor p is not null;
0, if the set of frontier source vertices for processor p is null; and
assigning frontier source vertices representing products to a processor p if MS[p] is 1.

### Claim 17

A computing system for dynamically assigning vertices to processors to generate a recommendation for a customer, the system comprising:
one or more processors,
a computer-readable medium coupled to the one or more processors having instructions stored thereon that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
receiving graph data indicating vertices and edges of the graph, wherein the vertices represent customers and products and the edges represent purchases;
determining, based on the graph data, a vertex that represents the customer;
traversing the graph from the vertex representing the customer to a set of vertices representing products;
dividing the set of vertices representing products among a set of processors;
determining a set of frontier vertices representing products for each processor of the set of processors;
traversing, by the set of processors, the graph from the set of frontier vertices representing products to a set of vertices representing customers;
dividing the set of vertices representing customers among a set of processors;
determining a set of frontier vertices representing customers for each processor of the set of processors;
traversing, by the set of processors, the graph from the set of frontier vertices representing customers to a set of vertices representing recommendable products;
and
generating a product recommendation for the customer based on the set of vertices representing recommendable products.

### Claim 18 (depends on 17)

The computing system of claim 17, wherein dividing the set of vertices representing customers among a set of processors further comprises:
generating a bitmask MU such that MU[p], the value of the pth bit, is:
1, if a set of U→V frontier vertices for processor p is not null, where U represents the set of customers and V the set of products;
0, if a set of U→V frontier vertices for processor p is null; and
assigning frontier vertices representing customers to a processor p if MU[p] is 1.

### Claim 19 (depends on 17)

The computing system of claim 17, wherein dividing the set of vertices representing customers among a set of processors further comprises:
estimating a maximum number of vertices assigned to each processor according to a formula └(umax−umin+1)/P┘, wherein P is the number of processors, umax is a maximum integer identifier for verticesεU, and umin is a minimum integer identifier for verticesεU, where U represents the set of customers; and
dividing the set of vertices representing customers uniformly among the set of processors based on the estimated maximum number of vertices assigned to each processor.

### Claim 20 (depends on 17)

The computing system of claim 17, wherein dividing the set of vertices representing customers among a set of processors further comprises:
dividing the set of vertices representing customers non-uniformly among the set of processors.

### Claim 21 (depends on 17)

The computing system claim 17, wherein dividing the set of vertices representing products among a set of processors further comprises:
generating a bitmask MV such that MV[p], the value of the pth bit, is:
1, if a set of V→U frontier vertices for processor p is not null, where V represents the set of products and U the set of customers;
0, if a set of V→U frontier vertices for processor p is null; and
assigning frontier vertices representing customers to a processor p if MV[p] is 1.

### Claim 22 (depends on 17)

The computing system of claim 17, wherein dividing the set of vertices representing products among a set of processors further comprises:
estimating a maximum number of vertices assigned to each processor according to a formula └(vmax−vmin+1)/P┘, wherein P is the number of processors, vmax is a maximum integer identifier for verticesεV, and vmin is a minimum integer identifier for verticesεV, where V represents the set of products; and
dividing the set of vertices representing products uniformly among the set of processors based on the estimated maximum number of vertices assigned to each processor.

### Claim 23 (depends on 17)

The computing system of claim 17, wherein dividing the set of vertices representing products among a set of processors further comprises:
dividing the set of vertices representing products non-uniformly among the set of processors.

### Claim 24 (depends on 17)

The computing system of claim 17, wherein the graph is a general graph, further comprising:
dividing a set of source vertices among a set of processors;
generating a bitmask MS such that MS[p], the value of the pth bit, is:
1, if the set of frontier source vertices for processor p is not null;
0, if the set of frontier source vertices for processor p is null; and
assigning frontier source vertices representing products to a processor p if MS[p] is 1.
