Systems and methods for pattern matching and relationship discovery

• US 10,262,077 B2
• Filed: 06/27/2014
• Issued: 04/16/2019
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Infante-Lopez, Gabriel G.
• Primary Examiner(s): Skhoun, Hicham
• Application Number:
  US14/318,015
• Publication Number:
  US 20150379158A1
• Time in Patent Office: 1,754 Days
• Field of Search: 707798
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Methods and systems for pattern matching and relationship discovery in graphs. The graph may be adapted as an actor graph, where vertices may include processing functionality and executable logic. The vertices of an actor graph may send messages to other vertices to which they are connected. A first vertex may receive an initial regular expression. The first vertex may evaluate which of its edges and/or respective vertices connected to these edges satisfy a first condition in the initial regular expression. If the first condition is met by an edge and or its connected vertex, the initial regular expression may be modified, if necessary, to reflect that the first condition has been met. The modified expression is then communicated to the connected vertex. The identity of the edge and/or the connected vertex may be recorded. A subsequent vertex may then proceed in a similar manner as the first vertex.

Claims

1. An apparatus, comprising a processor and memory arranged to:

construct an actor graph in which vertices represent entities and in which edges between the vertices represent relationships amongst the respective entities, in which vertices comprise independently acting units of computation, and in which said independently acting units of computation communicate with each other;

evaluate the actor graph to identify a path that satisfies a regular expression, including to,

with a first independently acting unit of computation, evaluate a first vertex of the actor graph based on the regular expression to determine if an edge of the first vertex satisfies a first one of multiple sequential conditions of the regular expression,

when the edge of the first vertex satisfies the first one of multiple sequential conditions of the regular expression, with the first independently acting unit of computation, send a message along the path from the first independently acting unit of computation to a second independently acting unit of computation at a second vertex at an end of the edge,

wherein the message comprises a first and a second component, the first component to encode a prefix that has been satisfied and the second component to encode the regular expression modified to reflect the remaining multiple sequential conditions to be satisfied,

wherein the processor includes a plurality of independently acting logic circuits to perform the independently acting units of computations of the vertices, with the independently acting logic circuit of each vertex to receive the message, and to store and compute intermediate values of the vertex to determine the first and second components of a next message to be sent along the path;

wherein to construct the actor graph and to evaluate the actor graph includes to perform, at the independently acting logic circuits, an evaluation of a regular path query (RPQ) of a graph from which the actor graph is adapted, independently of a size of the graph and independently of a number of the multiple sequential conditions included in the regular expression of the RPQ; and

wherein the edge of the first vertex is one of a plurality of weighted edges and to evaluate the actor graph to identify the path for the message that satisfies the regular expression includes to satisfy a condition relating to the plurality of weighted edges.

2. The apparatus of claim 1, wherein the apparatus is a first apparatus and the edge is a first edge, and wherein the message is received at the second independently acting unit of computation by a second apparatus, and the second vertex and a second edge that comes from the second vertex are evaluated based on the modified regular expression, wherein the first and second apparatuses are different apparatuses.

3. The apparatus of claim 1, wherein to modify the first one of the multiple sequential conditions comprises to reflect the satisfaction of the first one of the multiple sequential conditions.

4. The apparatus of claim 1, wherein the independently acting units of computation are further arranged to:

construct the actor graph as a social network graph in which the vertices represent persons of a social network.

5. The apparatus of claim 4, wherein the independently acting units of computation are further arranged to:

associate a value with each edge indicative of a level of trust between persons represented by vertices of the respective edges.

6. The apparatus of claim 1, wherein vertices of the actor graph represent items that include one or more of products and services, and wherein the independently acting units of computation are further arranged to:

assign a value to each edge indicative of similarity of items represented by vertices of the respective edge.

7. The apparatus of claim 1, wherein the independently acting units of computation are further arranged to:

evaluate the actor graph based on the regular expression and values assigned to vertices of the actor graph.

8. The apparatus of claim 1, wherein the prefix has been satisfied at the first vertex or a previous vertex.

9. The apparatus of claim 1, wherein to identify the path that satisfies the regular expression and satisfies a condition relating to the plurality of weighted edges includes identifying a path including a predetermined requirement of a combined weight.

10. A method, comprising:

constructing, by a computer processor, an actor graph in which vertices represent entities and edges between the vertices represent relationships amongst the respective entities, in which vertices comprise independently acting units of computation, and in which said independently acting units of computation communicate with each other;

with a first independently acting unit of computation, evaluating the actor graph to identify a path that satisfies a regular expression, including

evaluating a first vertex of the actor graph based on the regular expression to determine if an edge of the first vertex satisfies a first one of multiple sequential conditions of the regular expression,

when the edge of the first vertex satisfies the first one of multiple sequential conditions of the regular expression, with the first independently acting unit of computation, sending a message along the path from the first independently acting unit of computation to a second independently acting unit of computation at a second vertex at an end of the edge, wherein the message comprises a first and a second component, the first component to encode a prefix that has been satisfied and the second component to encode the regular expression modified to reflect the remaining multiple sequential conditions to be satisfied,

wherein the computer processor includes a plurality of independently acting logic circuits to perform the independently acting units of computations of the vertices, with the independently acting logic circuit of each vertex to receive the message, and to store and compute intermediate values of the vertex to determine the first and second components of a next message to be sent along the path,

wherein constructing the actor graph and evaluating the actor graph includes to perform, at the independently acting logic circuits, an evaluation of a regular path query (RPQ) of a graph from which the actor graph is adapted, independently of a size of the graph and independently of a number of the multiple sequential conditions included in the regular expression of the RPQ; and

wherein the edge of the first vertex is one of a plurality of weighted edges and evaluating the actor graph to identify the path for the message that satisfies the regular expression includes to satisfy a condition relating to the plurality of weighted edges.

11. The method of claim 10, further comprising receiving the message at the second independently acting unit of computation and, by the second independently acting unit of computation, evaluating the second vertex and a second edge that comes from the second vertex based on the modified regular expression, wherein the first and second independently acting units of computation are provided by different computers.

12. The method of claim 10, further comprising constructing the actor graph as a social network graph in which the vertices represent persons of a social network.

13. The method of claim 12, wherein constructing the actor graph further includes associating a value with each edge indicative of a level of trust between persons represented by vertices of the respective edges.

14. The method of claim 10, wherein vertices of the actor graph represent items that include one or more of products and services, and wherein constructing further includes assigning a value to each edge indicative of similarity of items represented by vertices of the respective edge.

15. The method of claim 10, wherein evaluating the actor graph further includes evaluating the actor graph based on the regular expression and values assigned to vertices of the actor graph.

16. The method of claim 10, wherein evaluating the actor graph further includes evaluating the actor graph based on the regular expression and values assigned to edges of the actor graph.

17. A non-transitory computer readable medium encoded with a computer program that includes instructions to cause a computer processor, in response to execution of the computer program, to:

construct an actor graph in which vertices represent entities and edges between the vertices represent relationships amongst the respective entities, in which vertices comprise independently acting units of computation, and in which said independently acting units of computation communicate with each other;

evaluate the actor graph to identify a path that satisfies a regular expression, including to

with a first independently acting unit of computation, evaluate a first vertex of the actor graph based on the regular expression to determine if an edge of the first vertex satisfies a first one of multiple sequential conditions of the regular expression, and

when the edge of the first vertex satisfies the first one of multiple sequential conditions of the regular expression, with the first independently acting unit of computation, send a message along the path from the first independently acting unit of computation to a second independently acting unit of computation at a second vertex at an end of the edge, wherein the message comprises a first and a second component, the first component to encode a prefix that has been satisfied and the second component to encode the regular expression modified to reflect the remaining multiple sequential conditions to be satisfied,

wherein a plurality of independently acting logic circuits to perform the independently acting units of computations of the vertices, with the independently acting logic circuit of each vertex to receive the message, and to store and compute intermediate values of the vertex to determine the first and second components of a next message to be sent along the path;

wherein to construct the actor graph and to evaluate the actor graph includes to perform, at the independently acting logic circuits, an evaluation of a regular path query (RPQ) of a graph from which the actor graph is adapted, independently of a size of the graph and independently of a number of the multiple sequential conditions included in the regular expression of the RPQ; and

wherein the edge of the first vertex is one of a plurality of weighted edges and to evaluate the actor graph to identify the path for the message that satisfies the regular expression includes to satisfy a condition relating to the plurality of weighted edges.

18. The non-transitory computer readable medium of claim 17, wherein the processor is a first processor and further including instructions to cause a second processor to receive the message at the second independently acting unit of computation and evaluate the second vertex and a second edge that comes from the second vertex based on the modified regular expression.

19. The non-transitory computer readable medium of claim 17, further including instructions to cause the first independently acting unit of computation to modify the first one of the multiple sequential conditions to reflect the satisfaction of the first one of the multiple sequential conditions.

20. The non-transitory computer readable medium of claim 17, further including instructions to cause the first independently acting unit of computation to construct the actor graph as a social network graph in which vertices represent persons of a social network.

21. The non-transitory computer readable medium of claim 20, further including instructions to cause the first independently acting unit of computation to associate a value with each edge indicative of a level of trust between persons represented by vertices of the respective edges.

22. The non-transitory computer readable medium of claim 17, wherein vertices of the actor graph represent items that include one or more of products and services, further including instructions to cause the first independently acting unit of computation to

assign a value to each edge indicative of similarity of items represented by vertices of the respective edge.

23. The non-transitory computer readable medium of claim 17, further including instructions to cause the first independently acting unit of computation to evaluate the actor graph based on the regular expression and values assigned to edges of the actor graph.