Shortest path determination in databases
AssigneeMicrosoft Corporation
InventorsIttai Abraham, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck
Life of this patent
Estimating the term…
Loading patent…
AssigneeMicrosoft Corporation
InventorsIttai Abraham, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck
Estimating the term…
Hub based labeling is used, in databases, to determine a shortest path between two locations. Every point has a set of hubs: this is the label (along with the distance from the point to all those hubs). The hubs are determined that intersect the two labels. This information is used to find the shortest distance. A hub based labeling technique uses, in a database, a preprocessing stage and a query stage. Finding the hubs is performed in the preprocessing stage, and finding the intersecting hubs is performed in the query stage using relational database operators, such as SQL queries. During preprocessing, a forward label and a reverse label are defined for each vertex. The labels are generated using contraction hierarchies that may be guided by shortest path covers. A query, such as an SQL query, is processed using the labels to determine the shortest path.
A method of determining a path between two locations, comprising:
A method of determining a path between two locations, comprising:
A method of determining a path between two locations, comprising:
Dependencies are inferred from the claim text.