# US 2012/0250535 A1 · Hub label based routing in shortest path determination

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

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

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- H04L 45/12: Shortest path evaluation
- H04L 45/14: {Routing performance; Theoretical aspects}
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- 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)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Hub based labeling is used 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 using the labels. The hubs are determined that intersect the two labels, and this information is used to find the shortest distance. A hub based labeling technique uses a preprocessing stage and a query stage. Finding the hubs is performed in the preprocessing stage, and finding the intersecting hubs (i.e., the common hubs they share) is performed in the query stage. 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, and may be pruned. A query is processed using the labels to determine the shortest path.

## Claims

### Claim 1

A method of determining a shortest 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 storage associated with the computing device.

### Claim 2 (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.

### Claim 3 (depends on 2)

The method of claim 2, 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 s and Lr(t) is the reverse label for vertex t.

### Claim 4 (depends on 1)

The method of claim 1, wherein each label comprises an integer representing a number of vertices in the label, a zero-based array with the identifiers of all vertices in the label, in ascending order, and an array with the distances from a vertex v to each vertex in the label.

### Claim 5 (depends on 1)

The method of claim 1, further comprising performing label pruning by identifying vertices with incorrect distance bounds and removing the vertices with incorrect distance bounds from the preprocessed graph data.

### Claim 6 (depends on 1)

The method of claim 1, further comprising ordering a subset of the vertices using a shortest path covers technique during a contraction hierarchy preprocessing phase.

### Claim 7 (depends on 1)

The method of claim 1, further comprising performing label compression to reduce the memory used by the preprocessed graph data, wherein the label compression comprises decomposing each label into a prefix and a suffix and representing each unique prefix only once.

### Claim 8 (depends on 1)

The method of claim 1, further comprising partitioning the labels such that more important vertices appear before less important vertices, wherein importance is based on a rank of the vertices.

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

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

### Claim 11 (depends on 1)

The method of claim 1, wherein the method is implemented for a point-to-point shortest path application.

### Claim 12

A method of determining a shortest 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;
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 the computing device, a point-to-point shortest path computation on the preprocessed data with respect to the source vertex and the destination vertex to determine a shortest path between the source vertex and the destination vertex, 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; and
outputting the shortest path, by the computing device.

### Claim 13 (depends on 12)

The method of claim 12, 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.

### Claim 14 (depends on 12)

The method of claim 12, 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 15 (depends on 14)

The method of claim 14, 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 s and Lr(t) is the reverse label for vertex t.

### Claim 16 (depends on 12)

The method of claim 12, wherein the preprocessing comprises at least one of performing label pruning by identifying vertices with incorrect distance bounds and removing the vertices from the preprocessed graph data, ordering a subset of the vertices using a shortest path covers technique, performing label compression to reduce the memory used by the preprocessed graph data, wherein the label compression comprises decomposing each label into a prefix and a suffix and using the prefixes and suffixes in determining distances between the vertices in the graph, or partitioning the labels such that more important vertices appear before less important vertices, wherein importance is based on a rank of the vertices.

### Claim 17

A method of determining a shortest path between two locations, comprising:
receiving as input, at a computing device, 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, by the computing device, a point-to-point shortest path computation on the preprocessed data with respect to a source vertex and a destination vertex to determine a shortest path between the source vertex and the destination vertex, 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; and
outputting the shortest path, by the computing device.

### Claim 18 (depends on 17)

The method of claim 17, wherein the preprocessed graph data is generated using an upwards contraction hierarchies search on the graph.

### Claim 19 (depends on 17)

The method of claim 17, 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 s and Lr(t) is the reverse label for vertex t.

### Claim 20 (depends on 17)

The method of claim 17, further comprising:
performing label pruning by identifying vertices with incorrect distance bounds and removing the vertices from the preprocessed graph data;
partially ordering the vertices during a contraction hierarchy search using a shortest path covers technique;
performing label compression to reduce the memory used by the preprocessed graph data, wherein the label compression comprises decomposing each label into a prefix and a suffix and using the prefixes in determining distances between the vertices in the graph; and
reordering the vertices in the labels such that more important vertices appear before less important vertices, wherein importance is based on a rank of the vertices.
