[OSM-dev] pre-compute routing
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
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
SteveC | steve at asklater.com | http://www.asklater.com/steve/
More information about the dev