Lesson plan

Hub labels

In computer science, hub labels or the hub-labelling algorithm is a speedup technique that consumes much fewer resources than the lookup table but is still extremely fast for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. This method allows at the most with two SELECT statements and the analysis of two strings to compute the shortest path between two vertices of a graph. For a graph that is oriented like a road graph, this technique requires the prior computation of two tables from structures constructed using the method of the contraction hierarchies. In the end, these two computed tables will have as many rows as nodes present within the graph. For each row (each node), a label will be calculated. A label is a string containing the distance information between the current node (the node of the row) and all the other nodes that can be reached with an ascending search on the relative multi-level structure. The advantage of these distances is that they all represent the shortest paths. So, for future queries, the search of a shortest path will start from the source on the first table and the destination on the second table, from which it will search within the labels for the common nodes with the associated distance information. Only the smallest sum of distances will be kept as the shortest path result.

Back to article

Article summary

In computer science, hub labels or the hub-labelling algorithm is a speedup technique that consumes much fewer resources than the lookup table but is still extremely fast for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. This method allows at the most with two SELECT statements and the analysis of two strings to compute the shortest path between two vertices of a graph. For a graph that is oriented like a road graph, this technique requires the prior computation of two tables from structures constructed using the method of the contraction hierarchies. In the end, these two computed tables will have as many rows as nodes present within the graph. For each row (each node), a label will be calculated. A label is a string containing the distance information between the current node (the node of the row) and all the other nodes that can be reached with an ascending search on the relative multi-level structure. The advantage of these distances is that they all represent the shortest paths. So, for future queries, the search of a shortest path will start from the source on the first table and the destination on the second table, from which it will search within the labels for the common nodes with the associated distance information. Only the smallest sum of distances will be kept as the shortest path result.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.