CH Warmups
The Hierarchical Nature of Road Networks
Try this as an exercise:
Look at the Google Map frame below. It has a pin dropped at Halligan Hall, the main CS building at Tufts.
Now click the - (zoom out) button at the bottom right corner of the frame, but only once.
Now zoom out again. Do you notice anything about color of the roads?
After the first click, most of the roads in the frame were still probably thin and white. If you zoom out again, you should start to see some thicker white lines and also some yellow.
After a few more clicks, many of the original thin white roads will disappear. And after 5 or 6 total clicks, many of the thick white lines will disappear. If you keep expanding so that New York is visible within the frame, the only roads you’ll see will be thick and yellow, which represent the major interstate highways like I-95.
This exercise is meant only to remphasize a fairly intuitive notion: that road networks are extremely hierarchical. Google Maps naturally identifies this when we zoom in and out of the map.
So what does this reemphasize? If we want the shortest path from Halligan Hall to Harvard Square, we’re probably only concerned with thick white roads, and maybe a few thin white roads near the start and end. And if we want the shortest path from Halligan Hall to New York, we’ll probably be concerned mostly with yellow roads. In fact, the shortest path from Halligan Hall to Providence or Philadelphia also mostly uses these yellow roads, many of which might be the same as the ones on the shortest path to New York.
The zoomed-out frame contains no fewer nodes and edges than the zoomed-in version, but it provides a helpful visualization into the number of nodes and edges that are actually important on a shortest path.
In other words, we started out by modeling our road network like this:
But really, similar to our Google Maps example, the information we want to embed in the graph conceptually looks like this:
What Can We Do With Hierarchical Information?
So if we are able to augment our graph with hierarchical information, how would that inform our querying?
Let’s go back to our Google Maps example and consider the shortest path between Halligan Hall and New York. Like we said, we should be concerned mostly with yellow roads, and this makes obvious sense: we’re more likely to travel on highways for a long distance trip because the travel time is usually short relative to the distance traveled.
Also, once we start driving on a highway, we’re unlikely to travel on a non-highway again, until we get close to our destination. In other words, during the middle of the shortest path on a long trip, we don’t expect to frequently make switches between yellow roads and white roads.
A Conceptual Model
We can then consider categorizing every edge by its level of importance. Highways for example, might be considered more important than surface roads.
Then, when running Dijkstra’s algorithm from source to target, we could heuristically choose to settle only nodes that are endpoints of an edge with a higher level of importance than the edge we previously traveled on.
In doing so, we would hope to exclude a large number of nodes from ever being settled and effectively reduce our search space.
We’ll Come Back to that Idea
However, remember that we still haven’t fully described a provably-efficient technique for assigning categories to edges.
We could simply create user-defined categories as part of our graph input (similar to our concept of yellow edges and white edges), but methods like this cannot be proven to give exact shortest paths (see [7] and [2]).
So for now, just make note of this hierarchical concept, as this is the same model that the contraction hierarchies algorithm uses.
But first, we’ll describe a variant of Dijkstra’s algorithm that doesn’t require any additional categorical information. We can then see how combining the categorical model with the Dijkstra variant can give us provably correct shortest paths with a much reduced search space.