search

ZJULearning / nsg

Navigating Spreading-out Graph For Approximate Nearest Neighbor Search
MIT License
632 stars 150 forks source link

Inconsistent Greedy Search #39

Open yar-sh opened 12 months ago

yar-sh commented 12 months ago

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: Screenshot_2023-11-13-16-14-31-953_com.google.android.apps.docs_1.jpg

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?

fc731097343 commented 11 months ago

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.