@Nic Roets You said: <<< The 35km route has 529 points. Don't ask me how many nodes were evaluated. http://www.yournavigation.org/?flat=40.730599&flon=-73.98658&tlat=40.895796&tlon=-74.108587&fast=1&v=motorcar&layer=mapnik The amount of memory was what the operating system reported and should include everything. >>>
You confused me. In preivous post you said New York State will be roughly 200MB in gosmore format, but in later post you said The amount of memory (the query required about 145MB ram) was what the operating system reported and should include everything. How 145MB ram can include 200MB New York State? I have finished study "Compressed sparse row" data model and want to discuss more about your NewYork graph. You said your graph is about 5,000,000 nodes, can you let me know the number of edges in that graph? I guess the total number of edges in your graph is about 4x5,000,000 - 20,000,000 edges, is it correct? (4 is average number of links out from one node) If the number of edges in your graph is much less than 20,000,000 then I think the space to store your graph can not be 200MB. It must be less than 200MB if you are using "Compressed sparse row" data model. If the number of edges in your graph is around 20,000,000 then the space to store your graph is about 200MB. In this case, I think I can fine tune the "Compressed sparse row" data model a bit to save even more memory. For your case, I can save 2 bytes for 1 node so you can save 2x5,000,000 = 10MB for your graph. --> your graph need only 190MB. If you are interest to know how to save that 10MB, let me know so that I will explain in detail. You said: <<< gosmore mmap()s a flat file. So the operating system loads pages as they are accessed. >>> Can you tell me more about this? So gosmore did not load the whole graph into memory? It store graph data in a flat file and read it whenever needed? You said: <<< The heap is a binary heap stored in an array and algorithms are really undergrad / textbook stuff. Roughly 10 lines of code. >>> Are you the person who develop gosmore? I ask how you do the binary heap not because of I do not know how to do it. I ask you how to do the binary heap to see whether we can exchange any idea. (for example: do you sort the whole heap or just keep the first element of the heap is in the lowest cost?...) @Marcus You said: <<< the router loads updates and missing areas from the OSM-server while routing. >>> Do you mean your routing application find route tile by tile? It is very interesting. I do not know how to do routing without the need of knowing graph as the whole. i.e if the graph divide into tiles, I do not know how to do the routing. You said: <<< No, I am using a memory-sensitive cache that uses as much memory as is currently unused to cache reat or unwritten data. >>> So you cached tile by tile in memory and your routing application just calculate within the cached nodes, right? You said: <<< That sounds strange. What is the purpose of the device? Is it for pedestriand, weelchairs, bikes? >>> the device is mobile phone. it is for car routing so it has to support million of nodes. Regards, -- View this message in context: http://www.nabble.com/How-big-is-your-graph--How-long-to-find-30km-route-in-your-graph--tp19985191p20006666.html Sent from the OpenStreetMap - Routing mailing list archive at Nabble.com. _______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
