Systems and methods for metadata based path finding
AssigneeDatawalk Spolka Akcyjna
InventorMateusz Mieszkowski
Life of this patent
Estimating the term…
Abstract
The present disclosure provides a computer-implemented method for traversing a graph. The method can comprise generating a metadata graph by reducing the graph, wherein the metadata graph is generated based on metadata describing one or more vertices and one or more edges of the graph. The metadata graph can comprise one or more edge types and one or more reduced vertices. Edge types in the metadata graph can be filtered to optimize finding of a path between a source vertex and a target vertex within a predetermined maximum path length.
Claims21
1-21. (canceled)
A computer-implemented method for traversing a graph, the method comprising:
- (a) generating a metadata graph based on metadata associated with vertices and edges of the graph, wherein each reduced vertex of the metadata graph represents a plurality of vertices of the graph sharing a common entity class, and each edge of the metadata graph represents an edge type defining a relationship between two entity classes;
- (b) identifying, in the metadata graph, one or more filtered edge types connecting a source reduced vertex to one or more neighbor reduced vertices, wherein the source reduced vertex represents the entity class of a source vertex of the graph, and each of the one or more neighbor reduced vertices has a path distance in the metadata graph to a target reduced vertex that is no greater than a predetermined value, wherein the target reduced vertex represents the entity class of a target vertex of the graph;
- (c) traversing the graph from the source vertex to one or more neighbor vertices using only edges of the one or more filtered edge types;
- and
- (d) returning one or more paths from the source vertex to the target vertex based at least in part on the one or more neighbor vertices.
A non-transitory computer-readable medium comprising machine-executable code that, upon execution by one or more computer processors, implements a method for for traversing a graph comprising:
- (a) generating a metadata graph based on metadata associated with vertices and edges of the graph, wherein each reduced vertex of the metadata graph represents a plurality of vertices of the graph sharing a common entity class, and each edge of the metadata graph represents an edge type defining a relationship between two entity classes;
- (b) identifying, in the metadata graph, one or more filtered edge types connecting a source reduced vertex to one or more neighbor reduced vertices, wherein the source reduced vertex represents the entity class of a source vertex of the graph, and each of the one or more neighbor reduced vertices has a path distance in the metadata graph to a target reduced vertex that is no greater than a predetermined value, wherein the target reduced vertex represents the entity class of a target vertex of the graph;
- (c) traversing the graph from the source vertex to one or more neighbor vertices using only edges of the one or more filtered edge types;
- and
- (d) returning one or more paths from the source vertex to the target vertex based at least in part on the one or more neighbor vertices.
The non-transitory computer-readable medium of claim 41, wherein generating the metadata graph comprises pre-computing a path length between each pair of reduced vertices in the metadata graph.
The non-transitory computer-readable medium of claim 41, wherein the method further comprises:
- intersecting the one or more neighbor vertices with the target vertex;
- and saving a path to the target vertex as a traverse result upon identifying the target vertex among the one or more neighbor vertices.
Dependencies are inferred from the claim text.