Duplication elimination in depth based searches for distributed systems

A method comprising:

• evaluating against graph data a graph query that specifies a particular pattern to match, wherein said graph data is accessible on a multi-node computing system, wherein said graph data comprises a plurality of vertices and a plurality of edges, wherein said evaluating the graph query comprises:
• generating, at a first node of the multi-node computing system, a first thread-level merged message based on first results of one or more instances of evaluating the graph query by a first thread at the first node, wherein the first results identify one or more first matching vertices, an identifier of at least one first next vertex on a second node separate from the first node, and a current stage of evaluating the graph query;
• generating, at the first node, a second thread-level merged message based on results of one or more instances of evaluating the graph query by a second thread at the first node, wherein the subsequent results identify one or more second matching vertices, an identifier of at least one second next vertex on the second node, and the current stage of evaluating the graph query;
• generating, at the first node, a node-level merged message based on the first thread-level merged message and the second thread-level merged message, wherein the node-level merged message comprises merged results based on the first results and the second results;
• and
• sending the node-level merged message from the first node to the second node;
• and
• providing a graph query result based at least in part on evaluation of the graph query by the second node based on the merged results.

One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause:

• evaluating against graph data a graph query that specifies a particular pattern to match, wherein said graph data is accessible on a multi-node computing system, wherein said graph data comprises a plurality of vertices and a plurality of edges, wherein said evaluating the graph query comprises:
• determining, at a first node of the multi-node computing system, in a particular instance of evaluating the graph query, that one or more first vertices on the first node match a first portion of the graph query and that a second vertex that is to be evaluated next is stored on a second node separate from the first node, wherein first results of the particular instance of evaluating the graph query identify the one or more first vertices as a first set of matching vertices and the second vertex as a next vertex to be evaluated;
• generating a first message based on the first results;
• determining, at the first node in a subsequent instance of evaluating the graph query, that one or more third vertices on the first node match the first portion of the graph query and that a fourth vertex to be evaluated next is stored on the second node, wherein subsequent results of the subsequent instance of evaluating the graph query identify the one or more third vertices as a set of matching vertices and the fourth vertex as a next vertex to be evaluated;
• in response to determining that the fourth vertex to be evaluated next is stored on the second node, merging, by the first node, the subsequent results with the first results in the first message to form merged results, wherein merging the subsequent results with the first results in the first message results in generating a merged message;
• and
• sending the merged message from the first node to the second node;
• and
• providing a graph query result based at least in part on evaluation of the graph query by the second node based on the merged results.