GRAPH SEARCH OPTIMIZATION SYSTEM BASED ON SORTED PROPERTY TECHNIQUES

• US 20190325078A1
• Filed: 04/24/2018
• Published: 10/24/2019
• Est. Priority Date: 04/24/2018
• Status: Abandoned Application

• Current Assignee: Trovares, Inc.
• Original Assignee: Trovares, Inc.
• Inventors: Haglin, David, Chavarria, Daniel, Adolf, Bob, Loos, Patrice
• Application Number:
  US15/961,773
• Publication Number:
  US 20190325078A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16

Abstract

Various systems are provided for optimizing the searching of a graph for a portion that matches a pattern is provided. A Graph Search Optimization System (“GSOS”) provides various techniques for reducing the computational expense when searching for patterns within a graph. The GSOS provides techniques that include an edge-count directed (“ECD”) system, a derived constraint (“DC”) system, and a sorted property (“SP”) system. The ECD system matches a pattern in a direction based on the number of edges for that direction. The DC system derives a single-element constraint from a multi-element constraints to avoid having to check multiple elements. The SP system processes edges of a graph in a sorted order based on the value of a property of the edges.

Claims

1. A method performed by a computing system to identify edges of a property graph that satisfy a multi-edge constraint that specifies a first property of a first edge, a second property of a second edge, and an order relation between the first property and the second property, the method comprising:

accessing a first sort of first edges connected to a first vertex, the first sort based on a value of the first property of the first edges;

accessing a second sort of second edges connected to a second vertex, the second sort based on a value of the second property of the second edges;

initializing a current first edge to a start first edge of the first sort;

initializing a current second edge to a start second edge of the second sort;

repeating until a termination criterion is satisfied,

when the multi-edge constraint is not satisfied by the current first edge and the current second edge, advancing the current first edge; and

when the multi-edge constraint is satisfied by the current first edge and the current second edge,

designating as satisfying the multi-edge constraint each combination the current second edge and each first edge from the current first edge to an end edge; and

advancing the current second edge.

2. The method of claim 1 wherein the multi-edge constraint is that a value of a first property of a first edge is greater than a value of a second property of the second edge.

3. The method of claim 2 wherein the first sort and the second sort are in increasing order.

4. The method of claim 1 wherein the multi-edge constraint is a constraint of a path pattern.

5. The method of claim 4 wherein the edges are identified when searching for a matching path of the property graph that matches the path pattern.

6. The method of claim 1 further comprising generating the first sort and the second sort.

7. The method of claim 1 wherein the advancing of a current edge includes performing a binary search between the current edge and an end edge of a sort to identify the next edge in the sort that satisfies the multi-edge constraint.

8. A computing system for identifying edges of a property graph that satisfy a multi-edge constraint, the computing system comprising:

one or more computer-readable storage mediums storing computer-executable instructions for controlling the computing system to;

traverse a first sort of first edges and a second sort of second edges in order by repeatedly;

advancing a current first edge through the first sort until the current first edge and a current second edge satisfy the multi-edge constraint;

designating as satisfying the constraint each combination of the current second edge and a first edge from the current first edge to an end first edge at one end of the first sort; and

advancing the second current edge through the second sort until the current first edge and the current second edge do not satisfy the multi-edge constraint; and

one or more processors for executing the computer-executable instructions stored in the one or more computer-readable storage mediums.

9. The computing system of claim 8 wherein when the multi-edge constraint specifies that a value of a first property of the first edge is greater than a value of a second property of the second edge, the first sort and the second sort are in increasing order, and the end first edge is the first edge with the largest value of the first property.

10. The computing system of claim 8 wherein the multi-edge constraint is a constraint of a path pattern.

11. The computing system of claim 10 wherein the edges are identified when searching for a matching path of the property graph that matches the path pattern.

12. The computing system of claim 8 wherein the computer-executable instructions further control the computing system to generate the first sort and the second sort.

13. The computing system of claim 8 wherein the advancing of a current edge includes performing a binary search between the current edge and an end edge of a sort to identify the next edge in the sort that satisfies the multi-edge constraint.