3 ms·

On road networks (Google Maps style routing) much much bigger gains have been achieved. Taking things to an extreme, Hub Labelling achieves sub-microsecond quer

On road networks (Google Maps style routing) much much bigger gains have been achieved. Taking things to an extreme, Hub Labelling achieves sub-microsecond query times on continental-scale road networks [1]. More flexible algorithms (e.g. Multi-Layer Dijkstra aka Customizable Route Planning, which Bing Maps supposedly uses) achieve sub-millisecond query times, with preprocessing times for new metrics less than a few minutes. This allows full timely integration of traffic information etc. On a 2D grid, there are a few differences, but even modeling it as a graph and applying road network algorithms (even simple ones like Landmark Routing) sounds like it would yield similar, if not better speedups. [1] http://research.microsoft.com/apps/pubs/default.aspx?id=145689 http://research.microsoft.com/apps/pubs/default.aspx?id=1456...

AnonymousPlanet 11y ago
Is there any kind of proper formal definition for the algorithm? The linked paper is a bit unstructured in this regard and seems a bit implementation focussed.
- lorenzhs 11y ago
  Well, it's a paper from the Symposium on Experimental Algorithms ;) You can find a good list of interesting route planning papers, including hub labeling, at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/routenplanung/index#literatur http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (page is in German, but the literature is English of course)
lnanek2 11y ago
It would be nice if Google Maps started doing a decent job, though. I lived for years in NJ and I would typically require 3 roads and 20 minutes to get anywhere I needed to go shopping because I would drive to the highway, hop on, get off on the road to my destination, then be there. Even if I avoided the highway I would get there in 30 minutes with smaller roads, taking the minimum needed to go the right direction toward the destination. Google Maps? It was a disaster. It would take the small roads since it couldn't bear to drive 2 blocks the wrong direction to get on the highway, then every small road it would alternate taking a left and a right and end up with dozens of turns when a human only needed 3 or 4. I actually met the ex-Googler who bragged about writing that algorithm that alternates left and right, I think he must be responsible for millions of hours of lost time for drivers just because he didn't realize turning has a cost and was trying to draw a diagonal as best he could. Does it really make sense to brag about fast calculation speed when the calculation is a disaster? I'd rather wait a minute for a calculation and get the right one, than have the wrong one back in 3 seconds. I think the Google Maps engineers don't understand this.
- lorenzhs 11y ago
  Actually, the algorithms used are provably optimal in regard to whatever metric is plugged into them. This means that no matter which of these algorithms you use (including Dijkstra or A*), you will get the exact same result. The difference is in the time and space required for precomputation vs at query time. That includes Contraction Hierarchies, which Google Maps uses (or used?). But if they screw up the optimization metric, then the algorithm can't save them either.
- codeka 11y ago
  I work on Google Maps and can confirm that it definitely takes the time required to turn left vs. right into account. If you send me an example of a bad route (you can use the web interface, which uses the same backend as Google Maps on your phone) I can take a look as to why it's routing you the way it is. My email address is in my profile.

AnonymousPlanet 11y ago

Is there any kind of proper formal definition for the algorithm? The linked paper is a bit unstructured in this regard and seems a bit implementation focussed.

lorenzhs 11y ago
Well, it's a paper from the Symposium on Experimental Algorithms ;) You can find a good list of interesting route planning papers, including hub labeling, at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/routenplanung/index#literatur http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (page is in German, but the literature is English of course)

lnanek2 11y ago

It would be nice if Google Maps started doing a decent job, though. I lived for years in NJ and I would typically require 3 roads and 20 minutes to get anywhere I needed to go shopping because I would drive to the highway, hop on, get off on the road to my destination, then be there. Even if I avoided the highway I would get there in 30 minutes with smaller roads, taking the minimum needed to go the right direction toward the destination. Google Maps? It was a disaster. It would take the small roads since it couldn't bear to drive 2 blocks the wrong direction to get on the highway, then every small road it would alternate taking a left and a right and end up with dozens of turns when a human only needed 3 or 4. I actually met the ex-Googler who bragged about writing that algorithm that alternates left and right, I think he must be responsible for millions of hours of lost time for drivers just because he didn't realize turning has a cost and was trying to draw a diagonal as best he could. Does it really make sense to brag about fast calculation speed when the calculation is a disaster? I'd rather wait a minute for a calculation and get the right one, than have the wrong one back in 3 seconds. I think the Google Maps engineers don't understand this.

lorenzhs 11y ago
Actually, the algorithms used are provably optimal in regard to whatever metric is plugged into them. This means that no matter which of these algorithms you use (including Dijkstra or A*), you will get the exact same result. The difference is in the time and space required for precomputation vs at query time. That includes Contraction Hierarchies, which Google Maps uses (or used?). But if they screw up the optimization metric, then the algorithm can't save them either.
codeka 11y ago
I work on Google Maps and can confirm that it definitely takes the time required to turn left vs. right into account. If you send me an example of a bad route (you can use the web interface, which uses the same backend as Google Maps on your phone) I can take a look as to why it's routing you the way it is. My email address is in my profile.