High-performance graph analytics engine making recommendations using a finite state machine/FSM, bitmasks, and graphs with edges representing purchases, and vertices representing customers and products

• US 9,330,411 B2
• Filed: 09/27/2013
• Issued: 05/03/2016
• Est. Priority Date: 09/27/2013
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Zhou, Rong, Davies, Daniel
• Primary Examiner(s): Vincent, David
• Application Number:
  US14/039,941
• Publication Number:
  US 20150095182A1
• Time in Patent Office: 949 Days
• Field of Search: 706/12, 706/45, 706/62
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/0631 Item recommendations
• CPC Class Codes: H04N 21/4668 for recommending content, e.g. movies

Abstract

One embodiment of the present invention provides a system for generating a product recommendation. During operation, the system receives graph data indicating vertices and edges of the graph. The vertices represent customers and products and the edges represent purchases. The system then receives a query of the graph to determine a product recommendation. Next, the system generates a finite-state machine (FSM) based on the query, executes the query, and determines whether a current state of the FSM is a traversal state. In response to the current state being a traversal state, the system generates a traversal FSM. The system then searches the traversal FSM for a nearest future traversal state, generates a bitmask for the future traversal state, and utilizes the generated bitmask when executing the future traversal state to generate the product recommendation.

Claims

1. A computer-executable method for generating a product recommendation, comprising:

receiving graph data indicating vertices and edges of the graph, wherein the vertices represent customers and products and the edges represent purchases;

receiving a query of the graph to determine a product recommendation;

generating a finite-state machine (FSM) based on the query;

executing the query;

determining whether a current state of the FSM is a traversal state;

in response to the current state being a traversal state, generating a traversal FSM;

searching the traversal FSM for a nearest future traversal state;

generating a bitmask for the future traversal state; and

utilizing the generated bitmask when executing the future traversal state to generate the product recommendation.

2. The method of claim 1, further comprising:

determining whether to perform pull or push traversals by computing a ratio α

·

β

, wherein α

=a ratio between a number of sender vertices and a total number of vertices of the graph, and β

=a ratio between average random write time and average random read time of the computer executing the method; and

performing push traversals if α

·

β

<

1; and

performing pull traversals if α

·

β

>

1.

3. The method of claim 1, wherein the query of the graph is expressed with a declarative language.

4. The method of claim 1, wherein searching for a nearest future traversal state further comprises:

determining that the current traversal state is compatible with the nearest future traversal state in that the current traversal state and the nearest future traversal state are associated with equal graphs.

5. The method of claim 1, wherein generating the bitmask comprises setting bit flags associated with vertex ranges according to an equation └

(ID(v)−

v_min-src)/n┘

==p, wherein ID(v) is an identifier value for vertex v, v_min-src is a minimum identifier value of a set of source vertices, n is average number of vertices assigned to each processor, and p is an identifier value for a processor.

6. The method of claim 1, wherein generating the traversal FSM further comprises applying a total ordering to one or more states of the FSM to generate states of the traversal FSM.

7. The method of claim 1, wherein the query includes both partition-bounded primitives and partition-unbounded primitives, and the graph includes multiple edge partitions, the method further comprising:

determining whether a primitive is partition-bounded or partition-unbounded;

upon determining that the primitive is partition-bounded, assigning each processor to a range of vertices ∈

[v^p_min-src, v^p_max-src], where v^p_min-src and v^p_max-src are a minimum integer identifier and a maximum integer identifier of source vertices in a graph partition p; and

upon determining that the primitive is partition-unbounded, for each partition, assigning vertices to processors according to an equation └

(ID(v)−

v_min-src)/n┘

==p, wherein ID(v) is an identifier value for vertex v, v_min-src is a minimum identifier value of a set of source vertices, n is average number of vertices assigned to each processor, and p is an identifier value for a processor.

8. The method of claim 7, wherein the partition-bounded primitive is a push primitive and the partition-unbounded primitive is a pull primitive.

9. The method of claim 1, further comprising:

receiving data indicating a new primitive and input/output arguments of the new primitive; and

adding the new primitive to a set of primitives.

10. A tangible computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for generating a product recommendation, 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;

receiving a query of the graph to determine a product recommendation;

generating a finite-state machine (FSM) based on the query;

executing the query;

determining whether a current state of the FSM is a traversal state;

in response to the current state being a traversal state, generating a traversal FSM;

searching the traversal FSM for a nearest future traversal state;

generating a bitmask for the future traversal state; and

utilizing the generated bitmask when executing the future traversal state to generate the product recommendation.

11. The computer-readable storage medium of claim 10, wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

determining whether to perform pull or push traversals by computing a ratio α

·

β

, wherein α

=a ratio between a number of sender vertices and a total number of vertices of the graph, and β

=a ratio between average random write time and average random read time of the computer executing the method; and

performing push traversals if α

·

β

<

1; and

performing pull traversals if α

·

β

>

1.

12. The computer-readable storage medium of claim 10, wherein the query of the graph is expressed with a declarative language.

13. The computer-readable storage medium of claim 10, wherein

searching for a nearest future traversal state further comprises:

determining that the current traversal state is compatible with the nearest future traversal state in that the current traversal state and the nearest future traversal state are associated with equal graphs.

14. The computer-readable storage medium of claim 10, wherein generating the bitmask comprises setting bit flags associated with vertex ranges according to an equation └

(ID(v)−

v_min-src)/n┘

==p, wherein ID(v) is an identifier value for vertex v, v_min-src, is a minimum identifier value of a set of source vertices, n is average number of vertices assigned to each processor, and p is an identifier value for a processor.

15. The computer-readable storage medium of claim 10, wherein generating the traversal FSM further comprises applying a total ordering to one or more states of the FSM to generate states of the traversal FSM.

16. The computer-readable storage medium of claim 10, wherein the query includes both partition-bounded primitives and partition-unbounded primitives, and the graph includes multiple edge partitions, and wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

determining whether a primitive is partition-bounded or partition-unbounded;

upon determining that the primitive is partition-bounded, assigning each processor to a range of vertices ∈

[v^p_min-src, v^p_max-src], where v^p_min-src and v^p_max-src are a minimum integer identifier and a maximum integer identifier of source vertices in a graph partition p; and

upon determining that the primitive is partition-unbounded, for each partition, assigning vertices to processors according to an equation └

(ID(v)−

v_min-src/n┘

==p, wherein ID(v) is an identifier value for vertex v, v_min-src is a minimum identifier value of a set of source vertices, n is average number of vertices assigned to each processor, and p is an identifier value for a processor.

17. The computer-readable storage medium of claim 10, wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

receiving data indicating a new primitive and input/output arguments of the new primitive; and

adding the new primitive to a set of primitives.

18. A computing system for generating a product recommendation, 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;

receiving a query of the graph to determine a product recommendation;

generating a finite-state machine (FSM) based on the query;

executing the query;

determining whether a current state of the FSM is a traversal state;

in response to the current state being a traversal state, generating a traversal FSM;

searching the traversal FSM for a nearest future traversal state;

generating a bitmask for the future traversal state; and

utilizing the generated bitmask when executing the future traversal state to generate the product recommendation.

19. The computing system claim 18, wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

determining whether to perform pull or push traversals by computing a ratio α

·

β

, wherein α

=a ratio between a number of sender vertices and a total number of vertices of the graph, and β

=a ratio between average random write time and average random read time of the computer executing the method; and

performing push traversals if α

·

β

<

1; and

performing pull traversals if α

β

>

1.

20. The computing system of claim 18, wherein the query of the graph is expressed with a declarative language.

21. The computing system of claim 18, wherein searching for a nearest future traversal state further comprises:

determining that the current traversal state is compatible with the nearest future traversal state in that the current traversal state and the nearest future traversal state are associated with equal graphs.

22. The computing system of claim 18, wherein generating the bitmask comprises setting bit flags associated with vertex ranges according to an equation └

(ID(v)−

vmin-src)/n┘

==p, wherein ID(v) is an identifier value for vertex v, vmin-src is a minimum identifier value of a set of source vertices, n is average number of vertices assigned to each processor, and p is an identifier value for a processor.

23. The computing system of claim 18, wherein generating the traversal FSM further comprises applying a total ordering to one or more states of the FSM to generate states of the traversal FSM.

24. The computing system of claim 18, wherein the query includes both partition-bounded primitives and partition-unbounded primitives, and the graph includes multiple edge partitions, and wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

determining whether a primitive is partition-bounded or partition-unbounded;

upon determining that the primitive is partition-bounded, assigning each processor to a range of vertices ∈

[v^p_min-src, v^p_max-src], where v^p_min-src and v^p_max-src are a minimum integer identifier and a maximum integer identifier of source vertices in a graph partition p; and

upon determining that the primitive is partition-unbounded, for each partition, assigning vertices to processors according to an equation └

(ID(v)−

v_min-src/n┘

==p, wherein ID(v) is an identifier value for vertex v, v_min-src is a minimum identifier value of a set of source vertices, n is average number of vertices assigned to each processor, and p is an identifier value for a processor.

25. The computing system of claim 18, wherein the computer-readable storage medium stores additional instructions that, when executed, cause the computer to perform additional steps comprising:

receiving data indicating a new primitive and input/output arguments of the new primitive; and

adding the new primitive to a set of primitives.