Apparatuses, systems, and methods for efficient graph pattern matching and querying

• US 8,533,182 B1
• Filed: 05/31/2012
• Issued: 09/10/2013
• Est. Priority Date: 05/31/2012
• Status: Active Grant

• Current Assignee: David P. Charboneau
• Original Assignee: David P. Charboneau
• Inventors: Charboneau, David P.
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US13/485,904
• Time in Patent Office: 467 Days
• Field of Search: 705/7.14, 707/694, 707/765, 707/781, 714/6.3
• US Class Current: 707/718
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Apparatuses, systems, and methods for efficient graph pattern matching and querying are disclosed. According to an aspect, a method includes providing a graph comprising vertices and edges associated with the vertices. Further, the method includes sending one or more first activation messages to a first set of the vertices, wherein each of the first activation messages has a value. The method also includes determining, at each vertex of the first set of vertices, whether the values of the one or more first activation messages received at the vertex meets a query condition. Further, the method also includes sending, at each vertex of the first set of vertices, one or more second activation messages from the vertex to a second set of vertices in response to determining that the values of the one or more first activation messages received at the vertex meets the query condition.

Claims

1. A method comprising:

providing a graph comprising vertices and edges associated with the vertices;

sending one or more first activation messages to a first set of the vertices, wherein each of the first activation messages has a value;

at each vertex of the first set of vertices;

determining whether the values of the one or more first activation messages received at the vertex meets a query condition;

in response to determining that the values of the one or more first activation messages received at the vertex meets the query condition, sending one or more second activation messages from the vertex to a second set of vertices;

receiving votes from graph partitions associated with the vertices, wherein the votes indicate whether to continue;

determining whether to continue based on the votes;

in response to determining to continue, performing a query plan; and

in response to determining not to continue, halting performance of the query plan.

2. The method of claim 1, wherein the graph is one of a directed graph and a digraph.

3. The method of claim 1, wherein providing the graph comprises storing data of the graph in memory.

4. The method of claim 1, wherein the steps of determining and sending one or more second activation messages are implemented in separate processing units.

5. The method of claim 4, further comprising assigning each vertex of the first set of vertices to one of the processing units.

6. The method of claim 4, further comprising assigning each vertex of the second set of vertices to one of the processing units.

7. The method of claim 1, wherein the steps of determining and sending one or more section activation messages are implemented in separate computing threads.

8. The method of claim 1, wherein sending one or more first activation messages comprises sending the one or more first activation messages to processing units associated with the first set of vertices.

9. The method of claim 1, wherein sending one or more second activation messages comprises sending the one of more second activation messages to processing units associated with the second set of vertices.

10. The method of claim 9, further comprising repeating the step of sending one or more second activation messages.

11. The method of claim 1, further comprising generating query results based on the first and second activation messages.

12. The method of claim 9, further comprising repeating the step of generating query results.

13. The method of claim 1, further comprising repeating the steps of determining and sending one or more second activation messages in accordance with a query step.

14. The method of claim 1, further comprising generating query pattern results based on activations of the first and second set of vertices.

15. The method of claim f further comprising recording the vertex firings and resultant vertex activations in performance of sub-graph pattern matching plans directly over a reified graph representation of any graph or digraph and iterating over that record of firings and activations to generate matches to sub-graph pattern.

16. A computing device comprising:

at least one processor and memory configured to;

provide a graph comprising vertices and edges associated with the vertices;

send one or more first activation messages to a first set of the vertices, wherein each of the first activation messages has a value;

at each vertex of the first set of vertices;

determine whether the values of the one or more first activation messages received at the vertex meets a query condition;

send one or more second activation messages from the vertex to a second set of vertices in response to determining that the values of the one or more first activation messages received at the vertex meets the query condition;

receive votes from graph partitions associated with the vertices, wherein the votes indicate whether to continue;

determine whether to continue based on the votes;

perform a query plan in response to determining to continue; and

halt performance of the query plan in response to determining not to continue.

17. The computing device of claim 16, wherein the graph is one of a directed graph and a digraph.

18. The computing device of claim 16, wherein the at least one processor and memory are configured to store data of the graph in memory.

19. The computing device of claim 16, wherein determining and sending one or more second activation messages are implemented in separate processing units.

20. The computing device of claim 19, wherein the at least one processor and memory are configured to assign each vertex of the first set of vertices to one of the processing units.

21. The computing device of claim 19, wherein the at least one processor and memory are configured to assign each vertex of the second set of vertices to one of the processing units.

22. The computing device of claim 16, wherein determining and sending one or more section activation messages are implemented in separate computing threads.

23. The computing device of claim 16, wherein the at least one processor and memory are configured to send the one or more first activation messages to processing units associated with the first set of vertices.

24. The computing device of claim 16, wherein the at least one processor and memory are configured to send the one of more second activation messages to processing units associated with the second set of vertices.

25. The computing device of claim 24, wherein the at least one processor and memory are configured to repeat the function of sending one or more second activation messages.

26. The computing device of claim 16, wherein the at least one processor and memory are configured to generate query results based on the first and second activation messages.

27. The computing device of claim 26, wherein the at least one processor and memory are configured to repeat the function of generating query results.

28. The computing device of claim 16, wherein the at least one processor and memory are configured to repeat the functions of determining and sending one or more second activation messages in accordance with a query step.

29. The computing device of claim 16, wherein the at least one processor and memory are configured to generate query pattern results based on activations of the first and second set of vertices.

30. A method comprising:

providing a graph comprising vertices and edges associated with the vertices;

executing sub-graph pattern matching through vertex firing of messages to connected vertices;

in response to receipt of a message at one or more vertices, activating the one or more vertices;

applying threshold tests to aggregated messages received per activated vertex, wherein the sub-graph pattern matching steps are executed directly over a reified graph representation for any graph or digraph; and

composing sub-graph pattern matching plans to represent larger sub-graph patterns, wherein for every vertex and every threshold test satisfied by the activations of that vertex in the current round triggers a vertex firing message to connected vertices for that vertex, and a successive round of vertex activations and threshold tests.