[Routing] How big is your graph? How long to find 30km route in your graph?

[j2megps]

@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.