# US 2012/0254153 A1 · Shortest path determination in databases

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254153 A1
- Document ID: US20120254153A1
- Status: Published application
- Kind: A1
- Application number: 13/287,154
- Filed: 2011-11-02
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Microsoft Corporation
- Inventors: Ittai Abraham; Daniel Delling; Andrew V. Goldberg; Renato F. Werneck
- Web page: https://patentgrep.com/patent/US20120254153A1

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G06F 16/353: into predefined classes
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

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.

## Claims

### Claim 1

A method of determining a path between two locations, comprising:
receiving as input, at a computing device, a graph comprising a plurality of vertices and arcs;
generating a plurality of labels for each vertex of the graph wherein for each vertex, the label comprises a set of vertices referred to as hubs and the distances between the hubs in the label and the vertex; and
storing data corresponding to the vertices and labels as preprocessed graph data in a relational database associated with the computing device.

### Claim 2 (depends on 1)

The method of claim 1, wherein the method is implemented for a SQL query.

### Claim 3 (depends on 2)

The method of claim 2, wherein the SQL query comprises a point-to-point shortest path query.

### Claim 4 (depends on 2)

The method of claim 2, wherein the SQL query comprises a point of interest query.

### Claim 5 (depends on 1)

The method of claim 1, wherein the plurality of labels for each vertex of the graph comprises a forward label and a reverse label, wherein the forward label comprises the set of vertices referred to as forward hubs and the distances from the vertex to each forward hub, and wherein the reverse label comprises the set of vertices referred to as reverse hubs and the distances from each reverse hub to the vertex, and further comprising:
storing the forward labels and the reverse labels in tables in the relational database.

### Claim 6 (depends on 5)

The method of claim 5, wherein each label has a property that for every pair of vertices (s,t), there is a vertex v such that v belongs to the shortest path, vεLf(s), and vεLr(t), wherein s is a start location and t is a destination location and wherein Lf(s) is the forward label for vertex and Lr(t) is the reverse label for vertex t.

### Claim 7 (depends on 1)

The method of claim 1, wherein the graph represents a network of nodes.

### Claim 8 (depends on 1)

The method of claim 1, wherein the graph represents a road map.

### Claim 9

A method of determining a path between two locations, comprising:
preprocessing, at a computing device, a graph comprising a plurality of vertices to generate preprocessed data comprising a plurality of labels for each vertex of the graph, wherein for each vertex, each label comprises a set of vertices and the distances between the vertices in the set of vertices and the vertex;
storing the labels in a relational database of the computing device;
receiving a query at the computing device;
determining a source vertex and a destination vertex based on the query, by the computing device;
performing, by relational database operators of the computing device, a path computation on the preprocessed data with respect to the source vertex and the destination vertex to determine a path between the source vertex and the destination vertex; and
outputting the path, by the computing device.

### Claim 10 (depends on 9)

The method of claim 9, wherein performing the path computation comprises performing a point-to-point shortest path computation using SQL in the relational database, wherein the shortest path computation comprises determining a vertex in a label for the source vertex and a label for the destination vertex that minimizes the distance between the source vertex and the vertex summed with the distance between the vertex and the destination vertex.

### Claim 11 (depends on 9)

The method of claim 9, wherein performing the path computation comprises performing a point of interest computation using SQL in the relational database.

### Claim 12 (depends on 9)

The method of claim 9, wherein performing the path computation comprises performing a point of interest computation using SQL in the relational database.

### Claim 13 (depends on 9)

The method of claim 9, wherein performing the path computation comprises performing a via point computation using SQL in the relational database.

### Claim 14 (depends on 9)

The method of claim 9, wherein performing the path computation comprises performing a ride sharing computation using SQL in the relational database.

### Claim 15 (depends on 9)

The method of claim 9, wherein the preprocessing comprises performing an upwards contraction hierarchies search on the graph to generate the plurality of labels for each vertex of the graph, and wherein the plurality of labels for each vertex of the graph comprises a forward label and a reverse label, wherein the forward label comprises the set of vertices and the distances to the vertices in the set of vertices from each vertex, and wherein the reverse label comprises the set of vertices and the distances from the vertices in the set of vertices to each vertex.

### Claim 16

A method of determining a path between two locations, comprising:
receiving as input, at a relational database associated, preprocessed graph data representing a graph comprising a plurality of vertices, wherein the preprocessed data corresponds to the vertices and a plurality of labels for each vertex of the graph, wherein the plurality of labels for each vertex of the graph comprises a forward label and a reverse label, wherein the forward label comprises the set of vertices and the distances to the vertices in the set of vertices from each vertex, and wherein the reverse label comprises the set of vertices and the distances from the vertices in the set of vertices to each vertex;
performing, using SQL statements in the relational database, a path computation on the preprocessed data with respect to a source vertex and a destination vertex to determine a path between the source vertex and the destination vertex; and
outputting the shortest path, by the computing device.

### Claim 17 (depends on 16)

The method of claim 16, wherein the path computation comprises a point-to-point shortest path computation.

### Claim 18 (depends on 16)

The method of claim 16, wherein the path computation comprises a point of interest computation.

### Claim 19 (depends on 16)

The method of claim 16, wherein the path computation comprises a via point computation.

### Claim 20 (depends on 16)

The method of claim 16, wherein the path computation comprises a ride sharing computation.
