hey, is there any code available about constructing the k-nn graph?

[yupbank]

From the paper, the k-NN graph $G_k$ is constructed by computing inner product nearest neighbor retrieval in the 2048-dimensional descriptor space.

which isn't saying much about the actual algorithm. Since the brutal force way would require O(N^2) time. I am wondering is there anything better than that?

[guangster]

In practice, exact algorithm can often be done very quickly on modern hardware using something like FAISS. Our experience with FAISS is that for about 1 million vertices, k-NN can be computed on a single GPU in about half an hour, with k=100. Many approximate k-NN graph construction are available, like work by Dong et. al [1], but we did not investigate this area.

[1] Dong, Wei, Charikar Moses, and Kai Li. "Efficient k-nearest neighbor graph construction for generic similarity measures." Proceedings of the 20th international conference on World wide web. ACM, 2011.

[yupbank]

interesting... thank you !