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

[Nic Roets]

With "include everything" I meant the data for the nodes that were actually
used, plus the extra temporary data for routing.

On Thu, Oct 16, 2008 at 5:55 AM, j2megps <j2megps at yahoo.com> wrote:

>
> 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)
>

The average node has 2 edges entering and 2 edges leaving. 2 x 5m = 10m
edges.


> "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
>

Saving 1 or 2 bytes on each structure will cause misalignment and only
degrade performance.


> You said:
> <<<
> gosmore mmap()s a flat file. So the operating system loads pages as they
> are
> accessed.
> >>>
>

http://en.wikipedia.org/wiki/Mmap

>
> 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?...)
>

I do this : http://en.wikipedia.org/wiki/Binary_heap
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20081016/71368a56/attachment.html>