Are you a salesman by any chance?

Nah just trying to write a paper with GIS data..

Nah. Ebay already solved that problem.

Obligatory: https://xkcd.com/399/

Heh, I liked it better when it was implied.

I assume you want to calculate the driving distance from the user's location. So you pick something like 20-50 nearest points (a very cheap and quick operation with a geo-spatial index) and then you will calculate the driving distance to each of them using something like Valhalla, which is much more expensive, but it scales linearly and can be parallelized.

So the 100+ million number is irrelevant.

The problem is I have 5MM "users" through several years and I want to compute their distance to a set of points that change through time, so I do care a lot about speed.

Computing the geodesic distances was slow but not that slow because I used a variation of R* with some caching on top, but I still had to compute around 5MM distances or so.

How can computing geodesic distances be slow? Isn't it rather trivial math? I'm pretty sure 5 million of them can be calculated in a few seconds on my laptop. And it can be offloaded to the client.

Whereas route calculation can't be easily offloaded.

You sure can do this on your own machine. Have a look here for how to set this up on your own machine: https://github.com/valhalla/chef-valhalla/blob/master/README...

Thanks!!

With Contraction Hierarchies you can get several hundred routes (or distances) per second. If you want to calculate distance matrices you can get a lot faster.