Back to results
US 11,456,946 B2Granted
Regular path queries (RPQS) for distributed graphs
AssigneeOracle International Corporation
InventorsPetar Tonkovic, Vasileios Trigonakis, Tomas Faltin, Sungpack Hong, Hassan Chafi
Life of this patent
Estimating the term…
Abstract
A pattern matching engine interprets a query into a data structure resembling a finite state machine. Vertices in the query pattern are treated as states or stages, while edges connecting them are treated as state transitions or hops. To match the full pattern, the first stage is first matched by applying vertex filters, if any. If the vertex is eligible, its edges that satisfy the edge filters, if any, are followed to move to the neighbors that can potentially produce results, thus progressing to the next stage. This process is repeated; if all stages are matched, then the whole pattern has been matched successfully.
Claims20
A method comprising:
- a multi-node computing system generating a path pattern, said path pattern including a data structure representing a plurality of stages and a plurality of hops, and evaluating said path pattern against a graph;
- wherein said multi-node computing system comprising a plurality of computing nodes;
- wherein said plurality of stages includes at least one repeatable stage, said at least one repeatable stage is associated with a hop to said at least one repeatable stage;
- wherein each of said plurality of stages is associated with entity properties and each of said hops is associated with relationship properties;
- wherein said graph is distributed in said multi-node computing system such that each vertex in said graph is on a node of said multi-node computing system and each edge in said graph connects a source vertex with a destination vertex in said graph;
- wherein evaluating said path pattern against said distributed graph comprises:
- a first node of said multi-node computing system, associated with a particular repeatable stage of said plurality of stages, maintaining a plurality of message buffers, wherein said plurality of message buffers are each for an associated node of said multi-node computing system, wherein the associated node is associated with a next stage of said plurality of stages;
- in response to said first node of said multi-node computing system storing on said first node a first vertex in said distributed graph, wherein said first vertex satisfies entity properties of said particular repeatable stage:
- performing depth first traversal at said particular repeatable stage;
- storing intermediate results in a per-depth buffer for a particular traversed depth;
- when said per-depth buffer for said particular traversed depth meets size threshold criteria, storing data from said per-depth buffer for said particular traversed depth in a first message buffer of said particular repeatable stage to send as a message to another node of said multi-node computing system to evaluate a said next stage, wherein said another node of said multi-node computing system storing on said another node a second vertex in said distributed graph.
8 more elements
One or more non-transitory storage media storing sequences of instructions which, when executed by one or more processors, cause:
- a multi-node computing system generating a path pattern, said path pattern including a data structure representing a plurality of stages and a plurality of hops, and evaluating said path pattern against a graph;
- wherein said multi-node computing system comprising a plurality of computing nodes;
- wherein said plurality of stages includes at least one repeatable stage, said at least one repeatable stage is associated with a hop to said at least one repeatable stage;
- wherein each of said plurality of stages is associated with entity properties and each of said hops is associated with relationship properties;
- wherein said graph is distributed in said multi-node computing system such that each vertex in said graph is on a node of said multi-node computing system and each edge in said graph connects a source vertex with a destination vertex in said graph;
- wherein evaluating said path pattern against said distributed graph comprises:
- a first node of said multi-node computing system, associated with a particular repeatable stage of said plurality of stages, maintaining a plurality of message buffers, wherein said plurality of message buffers are each for an associated node of said multi-node computing system, wherein the associated node is associated with a next stage of said plurality of stages;
- in response to said first node of said multi-node computing system storing on said first node a first vertex in said distributed graph, wherein said first vertex satisfies entity properties of said particular repeatable stage:
- performing depth first traversal at said particular repeatable stage;
- storing intermediate results in a per-depth buffer for a particular traversed depth;
- when said per-depth buffer for said particular traversed depth meets size threshold criteria, storing data from said per-depth buffer for said particular traversed depth in a first message buffer of said particular repeatable stage to send as a message to another node of said multi-node computing system to evaluate a said next stage, wherein said another node of said multi-node computing system storing on said another node a second vertex in said distributed graph.
8 more elements
Dependencies are inferred from the claim text.