Graph search optimization system based on an edge-count directed techniques

A method performed by a computing device for finding a path in a graph that matches a path pattern, the path pattern having pattern vertices and pattern edges with each pattern edge having a constraint, the graph having graph vertices and graph edges with each graph vertex having a count of connected edges, the method comprising:

• establishing a partial matching path of graph edges that matches a portion of the path pattern, a start graph edge in the partial matching path being connected to a start graph vertex and an end graph edge in the partial matching path being connected to an end graph vertex;
• and
• extending the partial matching path by:
• determining a predecessor count of predecessor graph edges connected to the start graph vertex that match the constraint for the next predecessor pattern edge of the path pattern;
• determining a successor count of successor graph edges connected to the end graph vertex that match the constraint for the next successor pattern edge of the path pattern;
• when the predecessor count is less than the successor count, adding to the partial matching path as a new start graph edge one of the predecessor graph edges;
• and
• when the predecessor count is not less than the successor count, adding to the partial matching path as a new end graph edge one of the successor graph edges.