| 摘要 |
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.
|
