41–50 of 56 posts
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..
Are you a salesman by any chance?
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..
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...
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..
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.
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.
Earlier quoted context omitted.
Glancing at the Valhalla repos, it looks like the MIT license across the board: https://github.com/valhalla ; https://github.com/valhalla/thor/blob/master/COPYING ; https://github.com/valhalla/chef-valhalla/blob/master/LICENS... ; etc... Also, it's not so much that the routing engines are proprietary -- the best ones are not. The underlying databases are the secret sauce.
what are the best ones?
There's an academic Thesis on the principles of contraction hierarchies that is worth a look if you're in this space. http://algo2.iti.kit.edu/documents/routeplanning/geisberger_... My favorite is actually a Master's thesis that steps through the process of using contraction hierarchies to build a routing engine (MoNav) on OpenStreetMap data. https://code.google.com/p/monav/downloads/detail?name=thesis...
For nuanced or complex problems, set up your objectives and constraints against a good solver: http://en.wikipedia.org/wiki/List_of_optimization_software I'm partial to Google's OR Tools https://github.com/google/or-tools (Apache License).
Any plans to add public transport support?
Earlier quoted context omitted.
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.
Whereas route calculation can't be easily offloaded.
Looks great! I really like the norse themed repository names ... though I'm not familiar with "demos" and "conf", are they some sort of mythical norse figures as well?
Demos, the great God of demonstrations and examples. He preferred to teach other Gods, as opposed to humans. Usually he could be found skulking nearby or with API, the God of documentation. Conf, the lesser known God of configurations and setups. He made sure that everything was well defined in a single place in a concise format, such as acceleration due to gravity, etc.
Earlier quoted context omitted.
Glancing at the Valhalla repos, it looks like the MIT license across the board: https://github.com/valhalla ; https://github.com/valhalla/thor/blob/master/COPYING ; https://github.com/valhalla/chef-valhalla/blob/master/LICENS... ; etc... Also, it's not so much that the routing engines are proprietary -- the best ones are not. The underlying databases are the secret sauce.
what are the best ones?
I'm the author of GraphHopper. Easy to setup, fast and flexible. Try it here: https://graphhopper.com/maps/
Earlier quoted context omitted.
Since most routing software is proprietary, I think it would be good to combat it by using a strong copyleft on the Valhalla components. GPLv3+ for client software and AGPLv3+ for server software would be awesome.
Glancing at the Valhalla repos, it looks like the MIT license across the board: https://github.com/valhalla ; https://github.com/valhalla/thor/blob/master/COPYING ; https://github.com/valhalla/chef-valhalla/blob/master/LICENS... ; etc... Also, it's not so much that the routing engines are proprietary -- the best ones are not. The underlying databases are the secret sauce.
No, it is not only about the database. Also about algorithms. But a lot about engineering and optimizing.