[FEA] Scale brute-force KNN by reducing distance computations

[cjnolet]

This is an official issue to track work on accelerating brute-force KNN by reducing distance computations. This is especially useful for distances such as Haversine where the trigonometry can be very expensive.

Initially, I'm working on a PoC for the Random Ball Cover algorithm rapidsai/raft#213 which has been shown to be effective on GPUs.

Another option is to port the popular nearest-neighbors descent algorithm to the GPU, which is currently implemented on the CPU in FAISS. A Python implementation of this algorithm has also been created by Leland McInnes and is used in UMAP.

The end-goal for either of these algorithms would ultimately be to contribute them to FAISS if they are interested in them. If we can make any speedups significant then we'll probably want to use them more broadly.

[github-actions]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.