Memory usage in Landmark algorithm

Hello community,

I have a few questions regarding to memory usage in LM algorithm:

1) Is it possible to not store the weighs between LM and all nodes? Memory usage and amount of LMs are linearly dependent (graph.getNodes() х landmarks х 4). 64 landmarks for the whole planet take a huge amount of memory.
For example, if we have three LMs on one line with a distance = 1000km, why we need to store the weighs between the first LM and nodes close to the third LM?

2) If we need a route only between the real junctions, how we can flexibly disable the loading of geometry and/or names to decrease memory usage? Currently we need to change BaseGraph for this, right?.

Best regards, Storm.

Hi Storm,

sure, there is still room for improvement and your pull request is always welcome :slight_smile:

It might make sense to avoid storing information close to a landmark but it will make the implementation much more complex and highly likely also reduces the speed gain.

  1. If we need a route only between the real junctions, how we can flexibly disable the loading of geometry and/or names to decrease memory usage? Currently we need to change BaseGraph for this, right?.

If memory is an issue you can customize the code and/or use memory mapped config for the DataAccess. But you’ll always end up between a compromise of speed vs. memory usage. BTW: if you do not need CH you should disable it and it’ll save lots of GB RAM.

64 landmarks for the whole planet take a huge amount of memory

The default is 16 and gives a good speed up already.

Regards
Peter

Hi karussell, thanks for the answer.

I would like to ask a few more questions:

  • I tried to replace calculated landmarks to suggested(points in the big cities from file ). And I’ve noticed that even if route crosses 3 my LMs, it takes more time for calculation this route than for route that does not cross any LM’s (calculated by default - not suggested). A litle bit strange behavior. Can I use suggested LMs without losing a speed?

  • Where can I read about subnetworks? What are they? How are they related to LMs? I’m not sure that I correctly understand it from code.

  • Three alternative routes(ALT algorithm with landmarks) from Munich to Paris has been calculated for 20sec. It is too much from my point of view. Is it possible to tune it up?

Best regards, Storm.

And I’ve noticed that even if route crosses 3 my LMs, it takes more time for calculation this route than for route that does not cross any LM’s (calculated by default - not suggested).

What do you mean here?

Where can I read about subnetworks? What are they? How are they related to LMs? I’m not sure that I correctly understand it from code.

Think about two separated graphs, like USA and Europe - they are separated and it is not necessary to hold information from one are to the other in the landmark storage.

Sure, this is too much. We have to improve the alternative routes algorithm for this somehow.

Thanks for reply.

I mean that the calculation time of the same route is different. With default LMs(by algoritmh - left picture) the route is calculated ~ 100ms but with manual LMs (suggested - right picture) it takes ~ 700ms. My LMs are closer to this route. I expected that the route between suggested LMs would be calculated faster, or it doesn’t matter?.

Currently we suggest to avoid manual landmarks (except you know what you do ;)) as our automated selection has improved a lot before the release. Did you read anywhere otherwise - please let me know where and we’ll have to fix :slight_smile:

My LMs are closer to this route. I expected that the route between suggested LMs would be calculated faster, or it doesn’t matter?.

Good landmarks are close and ‘behind’ the goal (and the start). Just close to the route does not matter much in my experience.