Systems and methods for pattern matching and relationship discovery
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22, 23)
-
Specification