GRAPH SEARCH OPTIMIZATION SYSTEM BASED ON SORTED PROPERTY TECHNIQUES

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method performed by a computing system to identify edges of a property graph that satisfy a multiedge 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 multiedge constraint is not satisfied by the current first edge and the current second edge, advancing the current first edge; and
when the multiedge constraint is satisfied by the current first edge and the current second edge,designating as satisfying the multiedge 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.
1 Assignment
0 Petitions
Accused Products
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 edgecount 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 singleelement constraint from a multielement 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.
0 Citations
No References
No References
13 Claims
 1. A method performed by a computing system to identify edges of a property graph that satisfy a multiedge 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 multiedge constraint is not satisfied by the current first edge and the current second edge, advancing the current first edge; and when the multiedge constraint is satisfied by the current first edge and the current second edge, designating as satisfying the multiedge 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.  View Dependent Claims (2, 3, 4, 5, 6, 7)
 8. A computing system for identifying edges of a property graph that satisfy a multiedge constraint, the computing system comprising:
one or more computerreadable storage mediums storing computerexecutable 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 multiedge 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 multiedge constraint; and one or more processors for executing the computerexecutable instructions stored in the one or more computerreadable storage mediums.  View Dependent Claims (9, 10, 11, 12, 13)
1 Specification
Data relationships are often modeled as a graph with the vertices of the graph representing entities and the edges of the graph representing relationships between the entities. For example, communications data relating to communications between people can be represented by a graph that includes a vertex for each person with an edge between two vertices indicating a communication between the people represented by vertices. As another example, web traffic data relating to people selecting links on a web site (or individual web pages) that are to another web site can be represented by a graph that includes a vertex for each web site with an edge between vertices indicating that a person selected a link on the web site represented by one of the vertices to travel to the web site represented by the other vertex.
To provide even more information, a graph may include directed edges that are each from an out vertex (also referred to a source vertex) to an in vertex (also referred to as a target vertex). For example, for communication data, a directed edge indicates that the person represented by the out vertex sent a communication (e.g., electronic message) to the person represented by the in vertex. As another example, for web traffic data, a directed edge indicates that the person visiting the web site represented by the out vertex selected a link to visit the web site represented by the in vertex.
Such graphs may also have properties associated with elements (i.e., vertices and edges) of the graph. Each property has a value. For example, for communications data, an edge may have a sent time property indicating the time when the communication was sent, a type property indicating the type of the communication (e.g., email or vmail), a content property indicating the content of the communication, and so on. For web traffic data, an edge may have a time property indicating the time when the link was selected, a web page property indicating the web page that contained the selected link, a link property specifying the link selected, a session property identifying a unique user session (e.g., a combination of a machine identifier, a browser identifier, and a session start time), and so on. A vertex of a graph representing either communications data or web traffic day may store properties related to the person represented by the vertex such as a name property, an employer property, a citizen property, a postal address property, a sex property, and so on.
Graphs can be used to represent data relationships that include billions of entities (e.g., people, web pages) and many billions of relationships between entities (e.g., travel between web pages). As such, a graph that represents such data relationships can have many billions of vertices and edges.
Such large graphs store a wealth of valuable information, but the information can be difficult to extract. For example, someone may want to identify all communication cycles between persons A, B, C, and D in which A sent a communication to B and then to C, then C sent a communication to D, and then D sent a communication to B within 60 seconds of A sending the communication to B.
When searching for vertices that match a pattern, every vertex of the graph needs to be checked for every vertex of the pattern. So, for a given vertex X in a graph, the graph needs to be checked in the positions of vertices A, B, C, and D. In addition, since a graph can many hundreds of millions of vertices and each vertex can have thousands of incoming and outgoing edges, it can be very computationally expensive to identify all the sets of edges of a graph that match a pattern. Moreover, it may take so long to identify the matching sets of edges that the extracted information may no longer be useful.
Methods and systems for optimizing the searching of a graph for a portion that matches a pattern is provided. In some embodiments, 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 edgecount directed (“ECD”) system, a derived constraint (“DC”) system, and a sorted property (“SP”) system.
The vertices of the path pattern are represented using an uppercase letter (e.g., A) and a vertex of the graph that corresponds to a vertex of the path pattern is represented using an uppercase letter with a prime (e.g., A′). Edges are represented by their connected vertices (e.g., (A, B)) with the first element representing the out vertex of the pair. So, the path pattern of
In some embodiments, the ECD system employs edgecount directed searching that factors in the count of edges when deciding which end of a pattern to extend next. The ECD system thus finds a matching path of a graph that matches a path pattern by repeatedly extending a partial matching path in a direction (or end) based on a predecessor count of edges that are predecessors to the first edge in the partial matching path that match a constraint (e.g., edge direction) of a predecessor edge specified by the path pattern and a successor count of edges that are successors to the last edge in the partial matching path that match a constraint of a successor edge specified by the path pattern. Referring to
Partial matching paths 221 and 222 illustrate another example of extending partial matching paths. The ECD system starts the search with a partial matching path of {(A′, B′)}, which matches edge (A, B) of the path pattern. Since vertex A′ has an outdegree of 100 as candidates for matching predecessor edge (A, D) and vertex B′ has an indegree of 1000 as candidates for matching successor edge (C, B), the ECD system extends the partial matching path by matching successor edge (C, B)) to each of the 10 inedges (C′, B′) of vertex B′. Continuing with the example, since vertex C′ has an outdegree of 1000 as candidates for matching successor edge (D, C) and vertex A′ has an outdegree of 100 as candidates for matching predecessor edge (A, D), the ECD system extends the partial match path by matching successor edge (C, D) to each of the 100 inedges of (D′, C′) as vertex C′.
In some embodiments, the DC system inputs constraints relating to multiple elements (“multielement constraints”) of a path pattern and derives from those constraints a derived constraint relating to only one of the elements (“a singleelement constraint”). For example, a constraint relating to multiple edges (“a multiedge constraint”) may be “(A, B)·a<(B, C)·a.” In this example, the constraint relates to adjacent edges (A, B) and (B, C) in the path pattern. Another constraint relating to a single edge (“a singleedge constraint”) may be “(B, C)·a<10”. Given these two edge constraints, the DC system may derive another singleedge constraint that is “(A, B)·a<10” based on the algebraic principle that if x<y and y<z, then x is necessarily less than z. As another example, a constraint relating to multiple vertices (“a multivertex constraint”) may be “A.d<B·d,” and a constraint relating to a single vertex (“a singlevertex constraint”) may be “B·d<1990” where d represents date of birth. Given these two vertex constraints, the DC system may derive another singlevertex constraint that is “A.d<1990” based on the same algebraic principle.
Continuing with the multiedge constraint example, when searching, if the edge of the derived singleedge constraint is to be matched before another edge of the multiedge constraint (e.g., the other edge is a predecessor edge or a successor edge, depending on the search direction), then the DC system determines whether the derived singleedge constraint is satisfied by that edge. For example, when an edge (A′, B′) is selected as matching (A, B) of the path pattern, the DC system determines whether the derived constraint “(A, B)·a<10” is satisfied.” If the derived constraint is not satisfied, the DC system can exclude that edge as matching (A, B) of the path pattern. The DC system can result in a significant decrease in the search space and corresponding decrease in the computational resources needed to search a graph. For example, if there are 1000 next edges (B′, C′) to a current edge (A′, B′) and the current edge (A′, B′) does not satisfy a derived constraint “(A, B)·a<10,” then the DC system can avoid checking any of those next edges, assuming the current edge is (A′, B′), and can eliminate the current edge as matching the edge (A, B) of the pattern. Moreover, if the derived constraint for a current edge (A, B) is derived from a certain value, of not the next edge (B, C), but of the edge after the next edge (C, D), then the DC system can avoid having to check a number of edges that is the total of the count of the next edges and, for each next edge, the count of its next edge. Thus, if each vertex of the graph has a degree of 1000, the DC system avoids having to search for 1,001,000 edges (i.e., 1000+(1000×1000)). By using derived singleelements constraints (i.e., derived singleedge constraints and/or derived singlevertex constraints), the DC system can significantly reduce the computational resources needed to search for paths that match a path pattern. In the following, the DC system is described primarily in the context of derived singleedge constraints even though the DC system may be used in a similar manner to employ singlevertex constraints.
In some embodiments, the DC system applies rules to constraints to derive the derived constraints for a property graph. Each rule has a condition and a derived constraint. For example, a condition may be “a<b AND b<c” and the derived constraint may be “a<c.” The DC system may store the rules in a rules table. The following table is an example of a rules table:
Rule 6 is a rule for specifying the condition of “a<b AND b<c” and the derived constraint of “a<c.” To derive constraints, the DC system initializes a collection of constraints for a search of the constraints specified in the path pattern, which are referred to as initial constraints. For example, if a path pattern has the constraints of “(A, B)·m<(B, C)·n,” “(B, C)·n<(C, D)·o,” and “5>(C, D)·o−(A, B)·m,” then the initial constraints may be represented by the following constraint table:
where x represents (A, B)·m, y represents (B, C)·n, and z represents (C, D)·o. After initializing the collection, the DC system applies the rules to the constraints in the collection to derive new derived constraints, adds the newly derived constraints to the collection, and again applies the rules to the constraints in the collection that includes the newly derived constraints to derive new constraints based on the newly derived constraints. The DC system may repeat this process until no more rules can be derived. Applying the rules of the example rules table, the DC system may derive the derived constraints as represented by the following table:
Some of the derived constraints may not lead to reducing the search space. For example, the derived constraint “y>x,” constraint number 4, is not used to derive additional derived constraints and is just a restatement of an initial fact. The derived constraint “z>y,” constraint number 5, is, however, used to derive the derived constraint “5>y+(−x),” constraint number 8, by applying rule 8 to initial constraint “5>z+(−x)” and derived constraint “z<y.” When searching for matching paths with the initial constraints, the DC system can apply constraint number 8 to edges (A′, B′) and (B′, C′). So even if constraint number 1 is satisfied, if constraint 8 is not satisfied, the DC system can eliminate (B′, C′) as a possible next edge in a matching pattern. Without constraint 8, the search would need to check each next edge (C′, D′) only to find that there is no edge (C′, D′) that leads to all the initial constraints being satisfied. Thus, by generating and applying derived constraints, the DC system significantly reduces the search space.
In some embodiments, the SP system identifies edges of a property graph that satisfy a multiedge constraint by sorting the edges and then advancing through the edges in sorted order. A multiedge constraint is a constraint of a path pattern that is based on the value of properties of two different pattern edges. For example, the constraint “(A, B)·a>(B, C)·a” is a multiedge constraint based on two different pattern edges. When the SP system is searching for a matching path in a property graph that matches a path pattern and a first set of first edges and a second set of second edges are to be checked to determine which combination pairs of a first edge and second edge match the multiedge constraint, the SP system generates a first sort of the first set and a second sort of the second set. Continuing with the example, the first edges are edges (A′, B′) and the second edges are edges (B′, C′). The SP system may sort the sets of edges in increasing order. The SP system then alternates advancing a current first edge through the first sort until the multiedge constraint is satisfied and then advancing a current second edge through the second sort until the multiedge constraint is not satisfied. Whenever a combination of a current first edge and current second edge satisfies the constraint, the SP system designates as satisfying the constraint each combination of the current second edge and a first edge from the current first edge to the last first edge. The SP system then switches to advancing the other current edge. The SP system continues until the end of the first sort or the second sort is reached.
Table 1 contains example values for property “a” for first edges (A′, B′) and second edges (B′, C′) that have been sorted in increasing order:
In this example, the property graph includes nine first edges and seven second edges. If the multiedge constraint is “(A, B)·a>(B, C)·a,” then the SP system proceeds as follows:
The SP system thus evaluates the multiedge constraint 12 times. In comparison, if the edges were not sorted, a search would require 63 (i.e., 9×7) evaluations. The edges could also be sorted in decreasing order, and similar algorithms could be applied.
The computing systems (e.g., network nodes or collections of network nodes) on which the GSOS may be implemented may include a central processing unit, input devices, output devices (e.g., display devices and speakers), storage devices (e.g., memory and disk drives), network interfaces, graphics processing units, cellular radio link interfaces, global positioning system devices, and so on. The input devices may include keyboards, pointing devices, touch screens, gesture recognition devices (e.g., for air gestures), head and eye tracking devices, microphones for voice recognition, and so on. The computing systems may include desktop computers, laptops, tablets, ereaders, personal digital assistants, smartphones, gaming devices, servers, and so on. The computing systems may access computerreadable media that include computerreadable storage media and data transmission media. The computerreadable storage media are tangible storage means that do not include a transitory, propagating signal. Examples of computerreadable storage media include memory such as primary memory, cache memory, and secondary memory (e.g., DVD) and other storage. The computerreadable storage media may have recorded on them or may be encoded with computerexecutable instructions or logic that implements the GSOS. The data transmission media are used for transmitting data via transitory, propagating signals or carrier waves (e.g., electromagnetism) via a wired or wireless connection. The computing systems may include a secure cryptoprocessor as part of a central processing unit for generating and securely storing keys and for encrypting and decrypting data using the keys.
The GSOS may be described in the general context of computerexecutable instructions, such as program modules and components, executed by one or more computers, processors, or other devices. Generally, program modules or components include routines, programs, objects, data structures, and so on that perform tasks or implement data types of the GSOS. Typically, the functionality of the program modules may be combined or distributed as desired in various examples. Aspects of the GSOS may be implemented in hardware using, for example, an applicationspecific integrated circuit (“ASIC”) or field programmable gate array (“FPGA”).
In some embodiments, the component may schedule a separate thread of execution for each invocation of the extend path component. In general, the ECD system may employ different strategies for scheduling the thread of execution. For example, the ECD system may schedule a thread of execution for each anchor edge, but not for any subsequent edge. In this way, the parallelism will only be at the anchor edge level. Alternatively, the ECD system may not schedule a separate thread of execution for each anchor edge but rather may schedule threads of execution when, for example, the second or third edges are added to a partial matching path. The parallelism strategy can be tailored to the characteristics of the path pattern and the graph. For example, if a graph has 1,000,000,000 edges with an average indegree and outdegree of only 10 and the path pattern has four edges, then the strategy may be to have parallelism for the anchor edges, but not for other edges. The ECD system may also schedule each thread of execution to process a group of next edges. For example, if there are 1000 next edges, the ECD system may schedule 100 threads of execution to each process a group of 10 next edges.
The following paragraphs describe various embodiments of aspects of the GSOS. An implementation of the GSOS system may employ any combination of the embodiments. The processing described below may be performed by a computing device with a processor that executes computerexecutable instructions stored on a computerreadable storage medium that implements the GSOS.
In some embodiments, a method performed by a computing device for finding a path in a graph that matches a path pattern is provided. The path pattern has pattern vertices and pattern edges with each pattern edge having a constraint. The graph has graph vertices and graph edges with each graph vertex having a count of connected edges. The method establishes a partial matching path of graph edges that matches a portion of the path pattern. A start graph edge in the partial matching path is connected to a start graph vertex, and an end graph edge in the partial matching path is connected to an end graph vertex. The method extends the partial matching path by performing the following. The method determines 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. The method then determines 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, the method add to the partial matching path as a new start graph edge one of the predecessor graph edges. When the predecessor count is not less than the successor count, the method adds to the partial matching path as a new end graph edge one of the successor graph edges. In some embodiments, the constraint is a direction of an edge. In some embodiments, the establishing of a partial matching path includes initializing the partial matching path with a graph edge that matches the constraint of an anchor pattern edge. In some embodiments, the method further, for each graph edge that matches the constraint of the anchor pattern edge, initializes the partial matching path with that graph edge and extending that partial matching path. In some embodiments, the constraint is based on a value of a property of a graph edge. In some embodiments, the constraint is based on a value of a property of a graph vertex. In some embodiments, 7 the path pattern is a cycle. In some embodiments, the graph is a directed graph and the path pattern is a directed pattern. In some embodiments, the path pattern is a directed cycle. In some embodiments, the constraint is a direction of an edge. In some embodiments, the method further, when the predecessor count is less than the successor count, for each predecessor graph edge, schedule a thread of execution to extend the partial matching path with a predecessor graph edge as a new start graph edge of the partial matching path. When the predecessor count is not less than the successor count, for each successor graph edge, the method schedules a thread of execution to extend the partial matching path with a successor graph edge as a new end graph edge of the partial matching path.
In some embodiments, a computing system for finding a pattern within a graph is provided. The computing system comprises one or more computerreadable storage mediums and one or more processors for executing computerexecutable instructions stored in the one or more computerreadable storage mediums. The one or more computerreadable storage mediums store a graph that has vertices and edges, a path pattern that has vertices and edges, and computerexecutable instructions for controlling the computing system. The instructions control the computing system to find a path of the graph that matches the path pattern by extending a partial matching path that matches a subpath of the path pattern in a direction based on a predecessor count of edges that match a constraint of a predecessor edge specified by the path pattern and a successor count of edges that match a constraint of a successor edge specified by the path pattern. In some embodiments, the graph is a directed graph and the constraint is a direction of an edge. In some embodiments, the path pattern is a cycle. In some embodiments, the constraint is based on a value of a property of an edge. In some embodiments, the constraint is based on a value of a property of vertex. In some embodiments, the computerexecutable instructions further control the computing system to schedule a thread of execution for different edges that match the constraint to extend the partial matching path in the direction of the smaller of the predecessor count and the successor count. In some embodiments, the path pattern has a path pattern length and the partial matching path has a partial matching path length, and the partial path is extended only while the partial matching path length is less than the path pattern length.
In some embodiments, a method performed by one or more computing systems for finding a path in a graph that matches a path pattern is provided. The path pattern has pattern vertices and pattern edges. At least some of the pattern edges have a constraint. The graph has graph vertices and graph edges with graph vertices having a count of connected edges. The method establishes a partial matching path of graph edges that matches a portion of the path pattern. The partial matching path has a start graph vertex and an end graph vertex. The method extends the partial matching path based a predecessor count of predecessor graph edges to the start graph vertex that match the constraint for the next predecessor pattern edge of the path pattern and 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. In some embodiments, the constraint is a direction of an edge. In some embodiments, the establishing of a partial matching path includes initializing the partial matching path with a graph edge that matches the constraint of an anchor pattern edge.
In some embodiments, a method performed by one or more computing systems for identifying a path pattern within a property graph is provided. The method accesses a first constraint for a first pattern element of the path pattern and a second constraint for a second pattern element of the path pattern. The first constraint is based on a value of a first property of the first pattern element and a value of a second property of the second pattern element, and the second constraint is based on a value of the second property of the second pattern element. The method derives, from the first constraint and the second constraint, a derived constraint for the first pattern element that is based on a value of the first property of the first pattern element and not on a value of the second property of the second pattern element. When determining whether a graph edge of the property graph is to be added to a partial matching path of the property graph that matches a portion of the path pattern, the method determines whether the value of the first property of the graph element associated with the graph edge satisfies the derived constraint. In some embodiments, the element is a graph edge. In some embodiments, the element is a graph vertex. In some embodiments, the method further accesses a rule for deriving a derived constraint. The rule specifies conditions and a derived constraint that can be derived when the conditions are satisfied. In some embodiments, the method further applies the rule to derive the derived constraint. In some embodiments, the method further accesses multiple rules for deriving derived constraints. In some embodiments, the method further extends the partial matching path in a direction based on a predecessor count of graph edges that satisfy a derived constraint of a predecessor edge specified by the path pattern and a successor count of graph edges that satisfy a constraint of a successor edge specified by the path pattern.
In some embodiments, a computing system for deriving constraints for a path pattern of a property graph is provided. The path pattern has elements with initial constraints. The computing system comprises one or more computerreadable storage mediums and one or more processors for executing the computerexecutable instructions stored in the one or more computerreadable storage mediums. The one or more computerreadable storage mediums store rules specifying conditions and derived constraints that can be derived when the conditions are satisfied and computerexecutable instructions. The computerexecutable instructions control the computing system to access initial constraints for a target pattern element of the path pattern, the initial constraints including a next initial constraint based on a value of a property of a next pattern element adjacent to the target pattern element in the path pattern. The computerexecutable instructions also control the computing system to apply the rules to the initial constraints to derive one or more derived constraints, including a derived constraint that is derived from a next base constraint and that is not based on a value of a property of the next pattern element. In some embodiments, the element is a graph edge. In some embodiments, the element is a graph vertex. In some embodiments, the computerexecutable instructions further include instructions to, when determining whether a graph edge corresponding to the target pattern edge of the path pattern is to be added to a partial matching path that matches a portion of the path pattern, determine whether the graph edge satisfies a derived constraint. In some embodiments, the rules are applied to initial constraints and previously derived constraints. In some embodiments, the rules are transitively applied.
In some embodiments, a computing system for deriving constraints for a path pattern of a property graph is provided. The computing system comprises one or more computerreadable storage mediums storing computerexecutable instruction and one or more processors for executing the computerexecutable instructions stored in the one or more computerreadable storage mediums. The computerexecutable instructions control the computing system to access initial constraints for a target pattern element of the path pattern. The initial constraints include a next initial constraint that is based on a value of a property of a next pattern element adjacent to the target pattern element in the path pattern. The computerexecutable instructions control the computing system to generate a derived constraint from the next initial constraints, the derived constraint not being based on value of a property of the next element. In some embodiments, the computerexecutable instructions further control the computing system to, when determining whether a graph edge corresponding to the target pattern edge of the path pattern is to be added to a partial matching path that matches a portion of the path pattern, determine whether the element associated with the graph edge satisfies the derived constraint. In some embodiments, the computerexecutable instructions further control the computing system to generate derived constraints from initial constraints that are not based on a value of a next pattern element adjacent to the target pattern element in the path pattern. In some embodiments, the computerexecutable instructions that control the computing system to generate a derived constraint apply rules specifying conditions and derived constraints.
In some embodiments, a method performed by a computing system is provided to identify edges of a property graph that satisfy a multiedge 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 accesses a first sort of first edges connected to a first vertex. The first sort is based on a value of the first property of the first edges. The method accesses 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. The method initializes a current first edge to a start first edge of the first sort and a current second edge to a start second edge of the second sort. The method repeat the following until a termination criterion is satisfied. When the multiedge constraint is not satisfied by the current first edge and the current second edge, the method advances the current first edge. When the multiedge constraint is satisfied by the current first edge and the current second edge, the method designates as satisfying the multiedge constraint each combination the current second edge and each first edge from the current first edge to an end edge and advances advancing the current second edge. In some embodiments, the multiedge 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. In some embodiments, the first sort and the second sort are in increasing order. In some embodiments, the multiedge constraint is a constraint of a path pattern. In some embodiments, the edges are identified when searching for a matching path of the property graph that matches the path pattern. In some embodiments, the method further generates the first sort and the second sort. In some embodiments, 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 multiedge constraint.
In some embodiments, a computing system for identifying edges of a property graph that satisfy a multiedge constraint. The computing system comprises one or more computerreadable storage mediums storing computerexecutable and one or more processors for executing the computerexecutable instructions stored in the one or more computerreadable storage mediums. The instructions control the computing system to traverse a first sort of first edges and a second sort of second edges in order by repeatedly performing the following. The instructions advance a current first edge through the first sort until the current first edge and a current second edge satisfy the multiedge constraint. The instructions designate 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. The instructions also advance the second current edge through the second sort until the current first edge and the current second edge do not satisfy the multiedge constraint. In some embodiments, when the multiedge 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. In some embodiments, the multiedge constraint is a constraint of a path pattern. In some embodiments, the edges are identified when searching for a matching path of the property graph that matches the path pattern. In some embodiments, the computerexecutable instructions further control the computing system to generate the first sort and the second sort. In some embodiments, the computerexecutable instructions that control the computing system to advance a current edge performs 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 multiedge constraint.
Although the subject matter has been described in language specific to structural features and/or acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. Accordingly, the invention is not limited except as by the appended claims.