[OSM-dev] pre-compute routing

Steve Coast steve at asklater.com
Thu Sep 27 12:42:45 BST 2007


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






More information about the dev mailing list