[OSM-dev] pre-compute routing

Brandon Martin-Anderson badhill at gmail.com
Thu Sep 27 16:30:41 BST 2007


A routing list. Hot. Can I has use Graphserver to precompute the routes?
It's fast as all getout. And I made it to do just this.

A few things:

An all-pairs routing graph will be proportional to the number of graph nodes
(nodes shared by more than one way) squared. I assume this is a bit higher
than 4 million, but probably less than 10x higher. I'm guessing there are
about five nodes per way, so the number is 4e6*5=20e6

The average route length will be half the width of the graph. The width of
this graph is 180 degrees longitude, so the average route length will be as
long as 90 degrees longitude, or 10018 kilometers. If the average way is
three kilometers long, that's over L=3000 ways per the average route. Half
are smaller. Half are larger.

N is 3, B is 2

20 * 10e6 * (3000 * 2) * 3 = 360 billion bytes "gigabytes".

So yeah, that's doable too with a little more effort. I've seen bigger MP3
collections.

It's important to note that you don't actually need to compute or store N^2
routes. If you take the shortest-path-tree of a node, and then take the
shortest-path-tree of a nearby node, and take the intersection of the two
SPTs, you'll find that there's a great deal of overlap between the two that
you don't need to compute twice. You'll note this is how our brains figure
out routing. When we're in an unfamiliar place we don't figure out a route
all the way to the destination; we just figure out a route to a nearby
known-place and then do a table lookup for the rest of the route. I don't
know how exactly to take advantage of this fact: it's a matter of some
fairly exciting research that either has been done or needs to be done in
order to pull this off in an open-source way. I'd love to take a swing at
it.

-B


On 9/27/07, Steve Coast <steve at asklater.com> wrote:
>
> (please reply to the new routing list, sent to dev so that you know
> it's there)
>
> We have about 4 million ways.
>
> An all pairs routing graph has therefore 16 million entries. We
> assume a route from a to b may be different than from b to a due to
> one way streets, turn restrictions etc.
>
> Almost every route is going to be something like "take street a,b,c,
> get on a motorway, come off and do streets d,e,f". That is, almost
> every route is going to be fairly simple. Let us a assign L to be the
> length of route in number of ways traversed. Of course many routes
> won't exist (you can't drive across oceans).
>
> Let us assign N to be the number of types of route, and lets say N is
> 3 for car, walk, cycle.
>
> Let us assign B to be the the number of bytes per way id. B=2, 16
> bits can currently encode all ways.
>
> The total disk space to store all routes is therefore
>
> ~= 4 * 10e6 * (L * B) * N
>
> I'm going to go out on a limb here, and almost any route I've got
> directions for is about 10 steps. Some will be more of course, but
> many will be much less.
>
> ~= 4 * 10e6 * (10 * 2) * 3 ~= 240 million bytes.
>
> Anyway the key point is we can pre-compute all routes and serve them
> from one box fairly easily if we want to. Even if you add an order of
> magnitude complexity, it's doable.
>
> This, I'm told, is exactly what Google do. But their dataset is a bit
> bigger.
>
> have fun,
>
> SteveC | steve at asklater.com | http://www.asklater.com/steve/
>
>
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20070927/de6c210f/attachment.html>


More information about the dev mailing list