Algorithm and Code bugs?

[devvrit]

Hi. I have some questions regarding the algorithm and the code:

1. In the paper there's no mention about what InterInsert function is doing. What's its relevance?
2. There's a DFS function but not being used, contrary to what's been mentioned in the paper.
3. As the DFS function’s not getting used, how are we ensuring the connectivity.
4. When performing InterInsert, in the case when temp_pool.size() > range, it might so happen that final pool has less nodes than range. But there’s no assignment of distance as ‘-1’ to mark the end of the pool.
5. When performing InterInsert, when (temp_pool.size() > range), how are we ensuring that the graph formed still has a monotic path from the navigating node to every other node?

[fc731097343]

Fot 1. It's just an alternative implementation of the algorithm. We try to ensure the neighbor selection insensitive to the order of processing. For 2 & 3. We are testing the robustness of this part of the code. Later we will update it. For 4. We actually do not need an end mark. For 5. NSG is an approximation of MRNG. We make some trade-offs to ensure the memory and time efficiency. In NSG, we do not try to ensure all monotonic paths. Instead, most nodes will not exceed the limitation of the degree. For the long-tail part who exceeds the limitation, we cut off distant neighbors to ensure memory efficiency. The cost is some monotonic paths are not guaranteed and a little detour will be needed at search time. We have tested that there is no impact on the search performance.