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

[Brandon Martin-Anderson]

Hrm yes 30e6^2 *3000 * 2 * 3 = insanely big number. That's where a mix of
hierarchical graph decomposition and live route computing comes in. It is a
_difficult_ problem.

-B

On 9/27/07, Brandon Martin-Anderson <badhill at gmail.com> wrote:
>
> 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/routing/attachments/20070927/004d4ca5/attachment.html>