[Routing] [OSM-dev] pre-compute routing

[Steve Coast]

On 27 Sep 2007, at 12:42, Steve Coast 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.

matt points out I didn't square the 10e6 so it's actually all a bit mad.

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

have fun,

SteveC | steve at asklater.com | http://www.asklater.com/steve/