Hacker News Reader

Comment by londons_explore | Hacker News Reader

> choices like 'avoid tolls', or 'avoid highways'

Those choices are insanely expensive for Google to provide.

Every unique configuration of options has to be hosted by hundreds of servers in each region. The cost of running the routing service is proportional to 2 ^ (the number of options). It's because everything has to be precomputed for fast lookups, and the lookup tables for one set of options aren't valid for another. See [1].

This is why Google hasn't added any more options in ~a decade. Even then, some combinations of options use various approximations and in some cases don't return the mathematically best result, or take longer to do so.

[1]: https://bib.irb.hr/datoteka/644571.MaueSandersMatijevic.pdf

View on HN

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.

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.

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.

> which definitely excludes the more space-intensive algorithms

No. A small area means a small download.

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.

”It's because everything has to be precomputed for fast lookups”

I don’t see how that can be true. With, conservatively, 50 million destinations, that would mean 25E14 different precomputed routes (edit, that’s exactly what the paper you reference argues: An extreme way to accelerate queries is to precompute all shortest path distances d(s, t). However, this is impractical for large graphs since it requires quadratic space and preprocessing time.)

Also, the average GPS without any internet connectivity can compute routes. Surely, those don’t store those precomputed routes.

What likely is true is that it may be a bit harder to do a bicycle route planner. Slightly simplifying, a planner for cars, given two places A and B relatively far apart, ‘just’ needs to find the best route from A to any on-ramp to a highway, from any highway to B, and a route only on highways between the on- and off-ramps.

On the other hand, bike routes that have to be planned typically will be a bit shorter.

Together, that means it isn’t that hard to compute routes on the fly. https://routeplanner.fietsersbond.nl/ does exactly that, giving you options such as “shortest route”, “fewest interruptions”, “racing”, “fewer cars”, or “recreational”.

It's kind of true. Routing algorithms like Contraction Hierarchies and Transit Node Routing don't precompute every possible A-B pair, but they do store so many "shortcuts" (i.e. the best route between common As and Bs) that a route lookup will quickly converge on one of these precomputed routes for all but its first and last sections.

It's similar to the way that we intuitively navigate by car - if you drive from (say) London to Glasgow, you don't bother weighing up the many options: rather, you take whatever local roads get you to the M1 fastest, then follow M1, M6, M74, and then whatever local roads get you to your exact destination.

Would it be cheaper to download the bike route data to the device and simply do the processing there?

Generally bicyclists have a fixed starting point so you could cache the results and improve them over time. (Obviously cross-country would require further work to support efficiently.)

I’m all for “anything can be done in the cloud” but if the cloud can’t efficiently handle this, I still have a couple of supercomputers laying around that I’d be happy to let puzzle over my bicycling needs for a few minutes (or overnight, or for a few weeks when charging) if that helped me find a more scenic route someday that isn’t much slower than the direct one.

This would be an interesting interview question. (/ducks)

Even small navigation company like Sygic can do it. While calculating on my phone.

So I don't think it is that expensive or insummortably difficult.

My 10 year old TomTom seems to manage OK and is pretty under-powered in most respects.

I'd speculate that most of that can be attributed to the TomTom's status a local device. I don't think the trouble is doing this for one person, but rather doing it for thousands to millions of people simultaneously. Also, the TomTom is probably operating on a pretty old set of static maps, rather than the constant updates that a service like Google Maps gets

>Those choices are insanely expensive for Google to provide.

That's a weak hill to die on with the money G makes. That's just the cost of doing business. People using maps need choices. If you as a map app choose not to provide an option, that's just an area a competitor can one up you. Once they do, you have to play catch up. That could be advantageous as you see what the competitor did that does/does not work allowing you to shortcut some of the R&D.

> That's just the cost of doing business.

It's not "doing business" if people using maps don't provide enough revenue back to the company either directly or through advertising. The reason Google makes so much money is that they are careful to implement features that are revenue positive.

Google isn't bottlenecked by money. Computers don't run on money. They are bottlenecked by getting datacenters online and staff ability to manage the complexity to keep systems running.

I don't really buy this argument: each pre-computed route could be tagged `{toll: false, highway: true, elevation: 15, scenic: 0.9}` and such, making it almost trivial to filter given options.

The expensive part is not the filtering. Actually you can do hundred of thousands of road segments per second (maybe 10x less on a phone). The expensive part is the visited nodes from Dijkstra vs. the much less nodes from the query of a precomputed request. The speed difference can be 50x or 200x, depending on the route length.

I don't think you understand how these routing algorithms work. Contraction Hierarchies, Customizable Route Planning, Transit Node Routing, etc are all guaranteed to give you the same result as a Dijkstra search. They just exploit properties of road networks to do so much faster. The secret sauce of routing is not in the algorithms (those are publicly known), it's computing the edge weights (including things like turn costs). Effectively, the edge weight has to be the desirability of driving/riding/walking along that particular stretch of road. A big factor of this is obviously travel time. This whole discussion is centered around the observation that whatever metric Google uses for bicycle routing, it doesn't result in routes that users perceive as good.

I'm not sure I fully understand this. Is the speed difference caused by the options limiting the use of pre-computed nodes? As in, looking for guarded bike roads limits the search for pre-computed nodes' lengths and the search has to be deeper as a result of thay.

Reply on news.ycombinator.com