@Marcus <<< Please read up on memory-mapping. It lets the operating-system load and cache (8kb)pages from the file while accessing it as if it where in-memory. >>>
Oh, I did not know about memory-mapping in Linux. I guess it is similar to Windows's virtual memory (using harddisk file as memory) You said: <<< Each way knows it's ordered list of node-ids. I have an index of nodeID->tileNumber (as well as wayID->tileNumber and normalized way/area-name(s) to wayID for address-searches). >>> I do different way. I have no list to capture link between wayID --> nodeID. no need to keep extra list --> save memory. When a route is found, I use node's lat/lon to match back to wayID's lat/lon (when I render map, I do the matching node and way) You said: <<< No. It calculated using all the map and loads parts of it (that need not have to be complete tiles) into memory as they are needed. >>> I do exactly the same. My A* algorithmn only load part of graph data from flat file into memory as needed. You said: <<< Your phone has just 1MB of memory for the map you are using? How do you suppose to route from one city to another or within any larger city? Where do you think of storing symbol-bitmaps for the map-rendering, the indexed address-database, ... with this little memory? >>> It can do routing from city to city as well as within city. For city to city, my application can do routing for the whole country UK from city to city (1m nodes, 2m edges) The map data for UK from OSM only contains 1m nodes. My application only uses 1MB memory to store open and close list. Everything else (map-rendering, the indexed address-database, graph data...) are stored in flat file. If the route is too long, the open and close list may excess 1MB -> my application will report not enough memory to calculate route. For within city, I choose NewYork city because this city is very density. My 1MB application can find 35km or more shortest route through this density city. I limit the maximun of nodes in the shortest route is 1,000 nodes. So when I try to find a route from junction of Coles st and 2 nd street (near Triam auto parts, Paradise Deli, Rodriguez Grocery) to the junction of Warrent st and highway 28 (near Sovergeign bank) my application report route was found but too long (>1000 nodes --> the route may have > 1000 turning points) @Nic Roets Here is my formula to calculate space for any graph using "Compressed sparse row" data model. nV is number of nodes. each node needs 12 bytes nE is number of edges. each edge need 8 bytes total space (bytes) = nV x 12 + nE x 8 You said: <<< The average node has 2 edges entering and 2 edges leaving. 2 x 5m = 10m edges. >>> Your NewYork graph contains 5m nodes and 10m edges so base on my calculation your graph needs total space = 5m x 12 + 10m x 8 = 140000000 bytes = 133MB Can you explain why your graph needs 200MB? You said: <<< Saving 1 or 2 bytes on each structure will cause misalignment and only degrade performance. >>> Saving 10MB memory may not sound anything to you because you are lucky --> your system have GB memory. My system has only 1MB so my application need to save byte per byte memory. I fine tune "Compressed sparse row" data model and here is new space formula (save 2 bytes): total space (bytes) = nV x 10 + nE x 8 You said: <<< I do this : http://en.wikipedia.org/wiki/Binary_heap >>> I do exactly the same --> it seeems that you and me can not further fine tune binary heap. Do you use any other technic beside binary heap to speed up A* algorithmn? You said: <<< http://download.cloudmade.com/north_america/united_states/new_york >>> I forgot to ask you about the New York.img.zip (29.70M) garmin map in the cloudmade link. Is this garmin map routable? or non-routable? Regards, -- View this message in context: http://www.nabble.com/How-big-is-your-graph--How-long-to-find-30km-route-in-your-graph--tp19985191p20009562.html Sent from the OpenStreetMap - Routing mailing list archive at Nabble.com. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
