5 ms·

A quick question: I have a list of 100+ million points with their geographical distance, but I want to improve it and calculate the "driving distance". How expe

A quick question: I have a list of 100+ million points with their geographical distance, but I want to improve it and calculate the "driving distance". How expensive in terms of time/ops would that be? I'm scanning the different subprojects on Github and I think Tyr is the one I need, but I'm not entirely sure..

magila 11y ago
Are you a salesman by any chance?
- Dewie3 11y ago
  Nah. Ebay already solved that problem.
  - hnyc 11y ago
    Obligatory: https://xkcd.com/399/ https://xkcd.com/399/
    - Dewie3 11y ago
      Heh, I liked it better when it was implied.
- zzleeper 11y ago
  Nah just trying to write a paper with GIS data..
alpensiedler 11y ago
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.md#building-and-running https://github.com/valhalla/chef-valhalla/blob/master/README...
- zzleeper 11y ago
  Thanks!!
imaginenore 11y ago
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.
- zzleeper 11y ago
  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.
  - imaginenore 11y ago
    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.
karussell 11y ago
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.

magila 11y ago

Are you a salesman by any chance?

Dewie3 11y ago
Nah. Ebay already solved that problem.
- hnyc 11y ago
  Obligatory: https://xkcd.com/399/ https://xkcd.com/399/
  - Dewie3 11y ago
    Heh, I liked it better when it was implied.
zzleeper 11y ago
Nah just trying to write a paper with GIS data..

alpensiedler 11y ago

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.md#building-and-running https://github.com/valhalla/chef-valhalla/blob/master/README...

zzleeper 11y ago
Thanks!!

imaginenore 11y ago

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.

zzleeper 11y ago
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.
- imaginenore 11y ago
  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.

karussell 11y ago

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.