New York State will be roughly 200MB in gosmore format. At roughly 40 bytes per arc / 40 bytes per node, we're looking at 5 million arcs / nodes. A quick glance at Tristam's URL indicates that "Compressed sparse row" is an appropriate description.
gosmore uses A*. A heap is used to find the next node to evaluate. Lambertus gave times for fastest routes. Shortest routes will be faster to compute as there is no longer a need to look for a detour involving a fast highway (motorway). http://download.cloudmade.com/north_america/united_states/new_york On Wed, Oct 15, 2008 at 10:36 AM, Lambertus <[EMAIL PROTECTED]> wrote: > j2megps wrote: > > Please share with me the following information: > > > > Which data structure you used to model a graph (i.e adjacency list or > > adjacency matrix data structure)? > > > > How big is your graph in term of number of routing nodes and routing > links > > or number of vertices and edges? > > > > Can you load the whole graph into memory when you calculate a route? > > > > How long does it take to calculate a 35km shortest route through NewYork > > city? > > > > Do you use any special technic to speed up A* algorithm? (like using > sorted > > open list,...) > > > On www.yournavigation.org [1] I use Gosmore [2] as a routing engine. > While I don't know anything about it's internals, the database size of > America is 4.8 GB but contains non-routing data also. > > Here is a route of about 35km within the New York area, running the same > query on different machines: > time > > QUERY_STRING='flat=40.730599&flon=-73.98658&tlat=40.895796&tlon=-74.108587&fast=1&v=motorcar' > nice ./gosmore > /dev/null > > - On a single core P4 3GHz, 3GB ram and local database: > real 0m0.159s > user 0m0.138s > sys 0m0.021s > > - On a dual core P4 3GHz, 2GB ram and database on NFS share: > real 0m0.170s > user 0m0.150s > sys 0m0.020s > > Another 120km route in the New York area (Smithtown to Livingston) takes: > real 0m2.469s > user 0m2.260s > sys 0m0.208s > > This query required about 145MB ram. > > [1] http://wiki.openstreetmap.org/index.php/YOURS > [2] http://wiki.openstreetmap.org/index.php/Gosmore > > _______________________________________________ > Routing mailing list > [email protected] > http://lists.openstreetmap.org/listinfo/routing >
_______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
