CLOVER: A GPU-native, Spatio-graph-based Approach to Exact kNN¶
Authors: Victor Kamel, Hanxueyu Yan, Sean Chester
Published: 2025 (Conference Paper)
Source: Proceedings of the 39th ACM International Conference on Supercomputing
Algorithm: CLOVER
DOI: 10.1145/3721145.3730415
Summary¶
Abstract¶
Finding the k nearest neighbours (kNN) of every point in a dataset is a key primitive in many GPU applications. Unfortunately, algorithmic techniques for kNN do not translate well to GPUs, require (offline) preprocessing, sacrifice accuracy, or require low query volume. Recently, ray-tracing cores have been proposed to accelerate exact kNN, but it is not well understood how these compare to grid-based methods. This work introduces a novel approach to exact kNN for spatial data that constructs and then traverses a graph from a random voronoi tesselation. On an NVIDIA V100, we answer ten million exact 30-NN queries with no prior preprocessing in 2.71s, about 4 × faster than an optimised grid-based method, 10 × faster than a GPU tree, and 230 × faster than FAISS. Furthermore, we show on an RTX card that RT-core methods are uncompetitive when query volume is high.