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

[Brandon Martin-Anderson]

I've spent some time in the past fiddling around with Google Maps' routing
system, and was able to find 'seams' in their precomputed routing system
showing that they don't actually precompute all pairs. You can look for the
seams like this: go to Google and ask for a long route. Click on the path
and drag it around to quickly re-compute the route passing through an
intermediate waypoint. Sometimes dragging the route by a small amount
results in a large jump in route-distance. Say you know the shortest route
to a point. The shortest route to a point a block away is never more than
the shortest route to the original point plus one block. So if you drag the
route waypoint over by a block and the shortest route increases by more than
that, you've found some sort of a seam in their precomputed routing system.
I'm mentioning this because it's almost certianly the state of the art in
route precaching; I don't know of any system that returns routes at the rate
and on the scale that Google does.

-B



On 9/27/07, Stefan de Konink <skinkie at xs4all.nl> wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> Steve Coast schreef:
> > Let us assign B to be the the number of bytes per way id. B=2, 16
> > bits can currently encode all ways.
>
> Why would you like to store an entire table, instead of partial tables
> and heuristics? The last one is much more efficient in rerouting when
> ways are added.
>
> Brandon schreef:
> > 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.
>
> Second that.
>
>
> Stefan
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.7 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFG+9i8YH1+F2Rqwn0RCtneAJ9E8tCDau8aTu5hFBQ/IagWhrbwOgCgiGh1
> dTRxYJhaWLCAC0HYEGBCk74=
> =5yP/
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20070927/b437d3d3/attachment.html>