SYSTEMS AND METHODS FOR PATTERN MATCHING AND RELATIONSHIP DISCOVERY

• US 20150379158A1
• Filed: 06/27/2014
• Published: 12/31/2015
• Est. Priority Date: 06/27/2014
• Status: Active Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Infante-Lopez, Gabriel G.
• Granted Patent: US 10,262,077 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. A system for identifying relationships between entities, comprising:

a processor; and

a memory in communication with said processor, said memory for storing a plurality of processing instructions for directing said processor to;

create an actor graph, wherein vertices of said actor graph represent the entities and comprise units of executable logic enabling said vertices to communicate with each other;

execute said actor graph using an initial regular expression as an input to said actor graph; and

output data representing one or more paths in said actor graph, wherein said paths satisfy said initial regular expression.

2. The system of claim 1, wherein the execution comprises:

receiving said initial regular expression at a first vertex of the actor graph;

at said first vertex, evaluating one or more of

an edge that comes from the first vertex, and

a second vertex at the end of said edge;

if the evaluation satisfies a first condition of said initial regular expression, recording the identity of the second vertex;

at said first vertex, modifying the initial regular expression to reflect the satisfaction of said first condition, if necessary;

sending the modified regular expression to the second vertex if the initial regular expression has been modified; and

sending the initial regular expression to the second vertex if the initial regular expression has not been modified.

3. The system of claim 2, wherein the execution further comprises:

receiving said modified regular expression or said initial regular expression at the second vertex;

at the second vertex, evaluating one or more of

an edge that comes from the second vertex, and

a third vertex at the end of said edge that comes from the second vertex;

if the evaluation at the second vertex satisfies a first condition of said received regular expression, recording the identity of the third vertex;

at said second vertex, modifying the received regular expression to reflect the satisfaction of said first condition, if necessary;

sending the modified received regular expression to the third vertex if the received regular expression has been modified; and

sending the received regular expression to the third vertex if the received regular expression has not been modified.

4. The system of claim 3, wherein the actor graph represents a social network and said vertices of said actor graph represent persons in said social network.

5. The system of claim 4, wherein each edge in said actor graph has an associated value representing a level of trust between corresponding persons represented by the vertices connected by the edge.

6. The system of claim 3, wherein vertices of the actor graph represent respective products or services, and wherein each edge in the actor graph has an associated value representing a degree of similarity between corresponding products or services represented by the vertices connected by the edge.

7. The system of claim 1, wherein each vertex comprises a value used in said evaluation.

8. The system of claim 1, wherein each edge has an associated value used in said evaluation.

9. A method of identifying relationships between entities, comprising:

creating an actor graph, wherein vertices of the actor graph represent the entities and comprise units of executable logic enabling the vertices to communicate with each other;

at a programmable processor, executing the actor graph using an initial regular expression as an input to the actor graph; and

outputting data representing one or more paths in the actor graph, wherein the paths satisfy the initial regular expression.

10. The method of claim 9, wherein the execution comprises:

receiving the initial regular expression at a first vertex of the actor graph;

at the first vertex, evaluating one or more of

an edge that comes from the first vertex, and

a second vertex at the end of the edge;

if the evaluation satisfies a first condition of the initial regular expression, recording the identity of the second vertex;

at the first vertex, modifying the initial regular expression to reflect the satisfaction of the first condition, if necessary;

sending the modified regular expression to the second vertex if the initial regular expression has been modified; and

sending the initial regular expression to the second vertex if the initial regular expression has not been modified.

11. The method of claim 10, wherein the execution further comprises:

receiving the modified regular expression or the initial regular expression at the second vertex;

at the second vertex, evaluating one or more of

an edge that comes from the second vertex, and

a third vertex at the end of the edge that comes from the second vertex;

if the evaluation at the second vertex satisfies a first condition of the received regular expression, recording the identity of the third vertex;

at the second vertex, modifying the received regular expression to reflect the satisfaction of the first condition, if necessary;

sending the modified received regular expression to the third vertex if the received regular expression has been modified; and

sending the received regular expression to the third vertex if the received regular expression has not been modified.

12. The method of claim 11, wherein the actor graph represents a social network and the vertices of the actor graph represent persons in the social network.

13. The method of claim 12, wherein each edge in the actor graph has an associated value representing a level of trust between corresponding persons represented by the vertices connected by the edge.

14. The method of claim 11, wherein vertices of the actor graph represent respective products or services, and wherein each edge in the actor graph has an associated value representing a degree of similarity between corresponding products or services represented by the vertices connected by the edge.

15. The method of claim 9, wherein each vertex comprises a value used in the evaluation.

16. The method of claim 9, wherein each edge has an associated value used in the evaluation.

17. One or more computer readable media having computer control logic stored thereon for identifying relationships between entities, the computer control logic comprising logic configured to cause a processor to:

create an actor graph, wherein vertices of the actor graph represent entities and comprise units of executable logic enabling the vertices to communicate with each other;

execute the actor graph using an initial regular expression as an input to the actor graph; and

output data representing one or more paths in the actor graph, wherein the paths satisfy the initial regular expression.

18. The computer readable media of claim 17, wherein the execution comprises:

receiving the initial regular expression at a first vertex of the actor graph;

at the first vertex, evaluating one or more of

an edge that comes from the first vertex, and

a second vertex at the end of the edge;

if the evaluation satisfies a first condition of the initial regular expression, recording the identity of the second vertex;

at the first vertex, modifying the initial regular expression to reflect the satisfaction of the first condition, if necessary;

sending the modified regular expression to the second vertex if the initial regular expression has been modified; and

sending the initial regular expression to the second vertex if the initial regular expression has not been modified.

19. The computer readable media of claim 18, wherein the execution further comprises:

receiving the modified regular expression or the initial regular expression at the second vertex;

at the second vertex, evaluating one or more of

an edge that comes from the second vertex, and

a third vertex at the end of the edge that comes from the second vertex;

if the evaluation at the second vertex satisfies a first condition of the received regular expression, recording the identity of the third vertex;

at the second vertex, modifying the received regular expression to reflect the satisfaction of the first condition, if necessary;

sending the modified received regular expression to the third vertex if the received regular expression has been modified; and

sending the received regular expression to the third vertex if the received regular expression has not been modified.

20. The computer readable media of claim 19, wherein the actor graph represents a social network and the vertices of the actor graph represent persons in the social network.

21. The computer readable media of claim 20, wherein each edge in the actor graph has an associated value representing a level of trust between corresponding persons represented by the vertices connected by the edge.

22. The computer readable media of claim 19, wherein vertices of the actor graph represent respective products or services, and wherein each edge in the actor graph has an associated value representing a degree of similarity between corresponding products or services represented by the vertices connected by the edge.

23. The computer readable media of claim 17, wherein each vertex comprises a value used in the evaluation.

24. The computer readable media of claim 17, wherein each edge has an associated value used in the evaluation.