Inconsistent Greedy Search

[yar-sh]

Hello!

I've looked closely at the paper, and it explicitly mentions that for the proper NSG constructiom the greedy search has to be performed from just the navigating node:

Link is calling get_neighbors to perform the greedy search from the navigating node. However, the following lines don't match the paper https://github.com/ZJULearning/nsg/blob/master/src/index_nsg.cpp#L171-L177

Here the pool is set to the neighbors of the navigating node, and the rest of the pool is filled with random points in the graph. So for large L, majority of the points are nowhere near the navigating node. This seems to contradict the paper. What is the reason for this? Doesn't it worsen the monotonic structure of the graph?

[CongFu92]

The consideration here is to accelerate the converge of local structure around each node while approximate indexing. We hope this can facilitate the linkage from the navi-node to this node and maintain a local monotonic structure for this node. If the nodes near the navi-node are monotonically connected, then we can derive further nodes share the monotonicity via theses nodes. Empirically it does not hurt the property compared with ideal graph.