Long shot, but if by any chance you could explain Highway Dimension [1] like I'm 5, and how it leads to faster routing algorithms, I would definitely be interested! I've watched some of Goldberg's videos (e.g. [2]), so I have some vague intuition, but not nearly as much as I feel I could/should. (Though it's entirely possible it's just something that can't be meaningfully ELI5'd in a usable manner... I don't know.)
Sure! That is a classic paper, I didn't know there was a video too. Let me try:
Highway Dimension-
Say we are given a bidirectional graph G and a radius r. Now take a vertex v, and find the set of all shortest paths from v of length > r and <= 4r. Let us call this set P(v, r). Iterate for all vertices in the graph and real radii, and obtain similar sets. Then, highway dimension is the size of the smallest set (H) of vertices such that all sets collected in the previous step have at least one vertex in H.
Why is this useful-
Empirically, we know that road networks have small highway dimensions. This is interesting because it implies that there are only a handful of vertices from which you can take the shortest paths to all the vertices in the network. Intuitively, it makes sense too. If you want to travel long distances, it's best to take the highway as early as possible, and travel along it for as long as you can, then descend to the local roads as you reach closer to the destination.
Highway dimension basically gives us a theoretical way of capturing the inherent 'hierarchy' of the road network edges and explains why Contraction Hierarchies works so well on road networks (as opposed to random graphs, where CH can be easily beaten). HTH!
Oh wow! To confirm I understand this, is the following correct? "The radius-r highway dimension of a graph G is the(/a?) minimal set of vertices that must be visited when traveling a distance ∈ (r, 4r]." I'm actually a little unclear on r—I assumed HD is a function of r, but you said you iterate over all real radii to obtain HD, which would mean HD is independent of r?
HD is independent of r.
And it's not the minimal set of vertices that must be visited.. it is the smallest set of which at least one must be visited. Another good explanation of HD is in section 1.3 of the skeleton dimension paper (https://arxiv.org/pdf/1609.00512.pdf).
Oh, sorry, I was vague about the visiting—I meant the set must be visited, i.e. something in it must be visited. I'll take a look at that one too, thanks!
Wow, the abstract on skeleton dimension looks quite amazing. I only happened to come across HD after working on a tangentially related algorithm, but I didn't keep up with the progress on that front... it didn't even hit me they might've already progressed beyond that to a stronger measure. That's pretty awesome, thanks for sharing!
[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...
[2] https://www.youtube.com/watch?v=ArO1ZviOMhI