3 ms·

That paper is old and definitely not what Google Maps actually uses. Techniques which people actually use (mostly Contraction hierarchies and CRP) are much more

That paper is old and definitely not what Google Maps actually uses. Techniques which people actually use (mostly Contraction hierarchies and CRP) are much more compact than what you describe. Routing isn't just a table lookup. Google Maps' offline maps also include routing information. The downloads are pretty small, which definitely excludes the more space-intensive algorithms.

karussell 6y ago
> which definitely excludes the more space-intensive algorithms No. A small area means a small download.
- lorenzhs 6y ago
  I'd be very concerned if download size wouldn't scale with the size of the map, so I'm not quite sure what your point is. Nobody uses lookup tables for routing (that would require quadratic space to store). If you really want to use something that could be described as lookup tables (even though "set intersection" would be more accurate), have a look at hub labeling. But that still requires a lot of space and isn't particularly suitable for traffic updates, so it's clearly not what any of the maps services use, online or offline.
morganherlocker 6y ago
To be fair, contraction hierarchies are inflexible for exactly the reasons OP described. CRP (aka multi-level dijkstra) is more flexible, but there's always a trade off between query speed, pre-process/weight-update speed, and route quality. These services are very expensive to run at global scale if you need multi-modal or live congestion support.
- lorenzhs 6y ago
  Customizable Contraction Hierarchies go a long way towards solving that, they're quite similar to CRP with regards to both customization and query time. Also, route quality isn't part of the trade-off: all of these methods are exact. I would argue that updating the routing algorithm's data structure isn't the expensive part of reacting to live traffic. Getting and processing the raw data sounds a lot harder than re-running the customization phase of routing preprocessing.

karussell 6y ago

> which definitely excludes the more space-intensive algorithms No. A small area means a small download.

lorenzhs 6y ago
I'd be very concerned if download size wouldn't scale with the size of the map, so I'm not quite sure what your point is. Nobody uses lookup tables for routing (that would require quadratic space to store). If you really want to use something that could be described as lookup tables (even though "set intersection" would be more accurate), have a look at hub labeling. But that still requires a lot of space and isn't particularly suitable for traffic updates, so it's clearly not what any of the maps services use, online or offline.

morganherlocker 6y ago

To be fair, contraction hierarchies are inflexible for exactly the reasons OP described. CRP (aka multi-level dijkstra) is more flexible, but there's always a trade off between query speed, pre-process/weight-update speed, and route quality. These services are very expensive to run at global scale if you need multi-modal or live congestion support.

lorenzhs 6y ago
Customizable Contraction Hierarchies go a long way towards solving that, they're quite similar to CRP with regards to both customization and query time. Also, route quality isn't part of the trade-off: all of these methods are exact. I would argue that updating the routing algorithm's data structure isn't the expensive part of reacting to live traffic. Getting and processing the raw data sounds a lot harder than re-running the customization phase of routing preprocessing.