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
