Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Valhalla, an open source routing engine

mapzen.com

Post reply on HN
Print view View original

21–30 of 56 posts

Re: Show HN: Valhalla, an open source routing engine

#21

Post by zzleeper »

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..

Re: Show HN: Valhalla, an open source routing engine

#23

Post by magila »

zzleeper wrote: post #21

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?

Re: Show HN: Valhalla, an open source routing engine

#24

Post by alpensiedler »

zzleeper wrote: post #21

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...

Re: Show HN: Valhalla, an open source routing engine

#25

Post by imaginenore »

zzleeper wrote: post #21

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.

Re: Show HN: Valhalla, an open source routing engine

#26

Post by glennon »

davexunit wrote: post #20
sevko wrote: post #3

Also, source code is here: https://github.com/valhalla

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.

Re: Show HN: Valhalla, an open source routing engine

#27

Post by glennon »

alpensiedler wrote: post #13
jakobdabo wrote: post #11

How does this compare to Project OSRM [1]? [1] https://github.com/Project-OSRM/osrm-backend

this blog post explains some of the major differences in the two architectures: https://mapzen.com/blog/valhalla-why_tiles

The OSRM routing engine appears to focus on contraction hierarchies; is that also the case for Valhalla? http://en.wikipedia.org/wiki/Contraction_hierarchies

Re: Show HN: Valhalla, an open source routing engine

#28

Post by wtallis »

juliangoldsmith wrote: post #10

Does anyone know how good the OpenStreetMap data is? I thought I'd heard that it was pretty incomplete.

I've used OSMAnd on my phone and found it to be comparable to or better than a standalone Garmin unit, but nowhere as good as Google Maps. That's doing the route calculations on the phone itself using pre-downloaded data, and I'm not sure how much detail gets stripped in the packaging process. You can't search for a particular house number, for example. In some states and on some highways it'll tell you which lane you need to be in for the right exit ramp, but that level of detail seems to be pretty spotty.

Re: Show HN: Valhalla, an open source routing engine

#29

Post by Dewie3 »

magila wrote: post #23
zzleeper wrote: post #21

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?

Nah. Ebay already solved that problem.

Re: Show HN: Valhalla, an open source routing engine

#30

Post by glennon »

juliangoldsmith wrote: post #10

Does anyone know how good the OpenStreetMap data is? I thought I'd heard that it was pretty incomplete.

Depends on the application. The developers that made Valhalla (Mapzen) recently hired my doctoral program office mate Indy Hurt to answer some aspects of that question. She's on Twitter at @indymapper. Elsewhere in academia, Muki Haklay has been studying the problem -- here's a link to one of his original papers that can provide a seed to find his more recent work: http://www.ucl.ac.uk/~ucfamha/OSM%20data%20analysis%20070808...

There are also numerous dev gatherings that examine OSM applications and data quality. One starts in a few days: http://stateofthemap.us/program/ You might check out the program and see if your application area is addressed.

Summary: OSM data offers the best free geospatial vector data available. It is a good starting point. For serious commercial applications, however, the data are rarely ready "out of the box". You will almost certainly need to improve/transform/annotate the data for your own purposes. Keep in mind that consequential improvements are expected to be submitted back to the OSM project.

Post reply on HN