search

yuyuanhang / GANNS

Article: GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction by Authors Yuanhang Yu, Dong Wen, Ying Zhang, Lu Qin, Wenjie Zhang and Xuemin Lin
14 stars 3 forks source link

Will Add a KNN Graph Construction Source Code as Paper Mentioned? #1

Open JieFengWang opened 7 months ago

JieFengWang commented 7 months ago

Hi @yuyuanhang, nice work! Turn to k-NN graph construction, will u add a k-NN graph construction API to this proj? Based on the paper, the k-NN graph construction is also in a divide-and-conquer fashion, ie, build a small k-NN graph using NN-Descent for each subset, then merge all sub-graph into one?

yuyuanhang commented 7 months ago

Hi @yuyuanhang, nice work! Turn to k-NN graph construction, will u add a k-NN graph construction API to this proj? Based on the paper, the k-NN graph construction is also in a divide-and-conquer fashion, ie, build a small k-NN graph using NN-Descent for each subset, then merge all sub-graph into one?

Hi @JieFengWang, Thanks for your attention to our work! Recently, I am busy with other works. I am afraid that I will not make any changes to the code of this project in near future.

JieFengWang commented 7 months ago

Hi @JieFengWang, Thanks for your attention to our work! Recently, I am busy with other works. I am afraid that I will not make any changes to the code of this project in near future.

Thanks for the reply, @yuyuanhang . I still have one additional question, is the k-NN graph construction using NN-Descent performed in a divide-and-conquer like indexing HNSW (build a knn graph for each subset, then merge them into one), or constructe ONE k-NN graph directly?

yuyuanhang commented 7 months ago

Hi @JieFengWang, Thanks for your attention to our work! Recently, I am busy with other works. I am afraid that I will not make any changes to the code of this project in near future.

Thanks for the reply, @yuyuanhang . I still have one additional question, is the k-NN graph construction using NN-Descent performed in a divide-and-conquer like indexing HNSW (build a knn graph for each subset, then merge them into one), or constructe ONE k-NN graph directly?

Hi, @JieFengWang, when constructing the k-nn graph, we use NN-Descent. But the divide-and-conquer strategy is not adopted when the graph does not cause the out-of-memory issue. We perform NN-Descent in a vertex-centric way where each warp or thread block is responsible for processing a vertex in a round. Initially, the neighbor lists of all vertices are randomly generated. In a round, for a vertex u, its neighbors' neighbors are read from global memory to shared memory and the distances between u and these neighbors' neighbors are computed. Finally, these distances are used to update the neighbor list of u. This process terminates when the user-defined iterations are finished. During the whole procedure, the computation of distances and the mergence of neighbor lists is performed in the same way as NSW/HNSW.