System and method for querying graphs distributed over multiple machines

Patent metadata

Field	Value
Publication number	US-2016335371-A1
Application number	US-201514713293-A
Country	US
Kind code	A1
Filing date	May 15, 2015
Priority date	May 15, 2015
Publication date	Nov 17, 2016
Grant date	—

Abstract

A method to perform query operations on nodes of large graphs distributed across multiple machines by applying a graph-query language that implements lazy evaluation techniques are disclosed. A method includes receiving a graph query expression from a client, wherein a graph comprises a plurality of edges linking a plurality of vertices, receiving a first request for evaluating the graph query expression, evaluating a partial result set for the graph query expression, and sending the partial result to the client. The partial result including at least one of a successor query and a predecessor query, wherein the successor query and the predecessor query enable evaluation of the graph query expression at a point in the graph query expression where the partial result evaluation terminated. A system and non-transitory computer readable medium are also disclosed.

First claim

We claim:

1 . A computer-implemented method, comprising:
receiving a graph query expression from a client, wherein a graph comprises a plurality of edges linking a plurality of vertices; receiving a first request for evaluating the graph query expression; evaluating a partial result set for the graph query expression; and sending the partial result to the client; the partial result including at least one of a successor query and a predecessor query, wherein the successor query and the predecessor query enable evaluation of the graph query expression at a point in the graph query expression where the partial result evaluation terminated.

2 . The computer-implemented method of claim 1 , receiving the graph query expression includes converting an infix form of the graph query expression to a postfix form.

3 . The computer-implemented method of claim 1 , including storing the graph as a first trie that includes a first plurality of strings, wherein the first trie stores a first common prefix of two or more strings of the first plurality of strings on a first page, wherein each of the first plurality of strings includes a first vertex followed by an edge that is followed by a second vertex, and wherein the edge is directed from the first vertex to the second vertex.

4 . The computer-implemented method of claim 3 , including storing the graph as a second trie that includes a second plurality of strings, wherein the second trie stores a second common prefix of two or more strings of the second plurality of strings on a second page, wherein each of the second plurality of strings includes the second vertex followed by the edge that is followed by the first vertex.

5 . The computer-implemented method of claim 4 , including storing the graph as a third trie that includes a third plurality of strings, wherein the third trie stores a third common prefix of two or more strings of the third plurality of strings on a third page, wherein each of the third plurality of strings includes the second vertex followed by the first vertex that is followed by the edge.

6 . The computer-implemented method of claim 1 , wherein the graph query expression includes operations selected from at least one of edge hopping, a Boolean function, a set of edges of the plurality of edges that are from a vertex of the plurality of vertices, a triangular relationship, a range, and an alias.

7 . The computer-implemented method of claim 1 , including storing the graph across a plurality of hosts based on storing a common portion of the graph on two or more hosts of the plurality of hosts.

8 . The computer-implemented method of claim 7 , including providing a first result that includes the merger of data on each host of the plurality of hosts.

9 . The computer-implemented method of claim 7 , including adding an edge to the graph by replicating the edge over at least two hosts of the plurality of hosts.

10 . The computer-implemented method of claim 8 , including removing an edge from the graph by sending an instruction to the plurality of hosts.

11 . A non-transitory computer readable medium containing computer-readable instructions stored therein for causing a computer processor to perform operations comprising:
receiving a graph query expression from a client, wherein a graph comprises a plurality of edges linking a plurality of vertices; receiving a first request for evaluating the graph query expression; evaluating a partial result set for the graph query expression; and sending the partial result to the client; the partial result including at least one of a successor query and a predecessor query, wherein the successor query and the predecessor query enable evaluation of the graph query expression at a point in the graph query expression where the partial result evaluation terminated.

12 . The non-transitory computer-readable medium of claim 11 , including instructions to cause the processor to perform the step of receiving the graph query expression by converting an infix form of the graph query expression to a postfix form.

13 . The non-transitory computer-readable medium of claim 11 , including instructions to cause the processor to perform the step of storing the graph as a first trie that includes a first plurality of strings, wherein the first trie stores a first common prefix of two or more strings of the first plurality of strings on a first page, wherein each of the first plurality of strings includes a first vertex followed by an edge that is followed by a second vertex, and wherein the edge is directed from the first vertex to the second vertex.

14 . The non-transitory computer-readable medium of claim 13 , including instructions to cause the processor to perform the step of storing the graph as a second trie that includes a second plurality of strings, wherein the second trie stores a second common prefix of two or more strings of the second plurality of strings on a second page, wherein each of the second plurality of strings includes the second vertex followed by the edge that is followed by the first vertex.

15 . The non-transitory computer-readable medium of claim 14 , including instructions to cause the processor to perform the step of storing the graph as a third trie that includes a third plurality of strings, wherein the third trie stores a third common prefix of two or more strings of the third plurality of strings on a third page, wherein each of the third plurality of strings includes the second vertex followed by the first vertex that is followed by the edge.

16 . The non-transitory computer-readable medium of claim 11 , wherein the graph query expression includes operations selected from at least one of edge hopping, a Boolean function, a set of edges of the plurality of edges that are from a vertex of the plurality of vertices, a triangular relationship, a range, and an alias.

17 . The non-transitory computer readable medium of claim 11 , wherein the computer processor performs the operations to store the graph across a plurality of hosts based on the computer processor stores a common portion of the graph on two or more hosts of the plurality of hosts.

18 . The non-transitory computer readable medium of claim 17 , wherein the computer processor performs the operations to provide the first result that comprises the computer processor merges each data on each host of the plurality of hosts.

19 . The non-transitory computer readable medium of claim 17 , wherein the computer processor performs the operations to add an edge to the graph by replicating the edge over at least two hosts of the plurality of hosts.

20 . The non-transitory computer readable medium of claim 17 , wherein the computer processor performs the operations to remove an edge from the graph by sending an instruction to the plurality of hosts.

Assignees

• Gen Electric

Inventors

• Rao Bharath

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2471

  Distributed queries · CPC title

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F16/214

  Database migration support · CPC title

• G06F17/30545

  Physics · mapped topic