Arkade: k-Nearest Neighbor Search With Non-Euclidean Distances using GPU Ray Tracing

高性能的低维k最近邻搜索（kNN）的实现使用基于树的数据结构。由于树算法的不规则性，它们很难在GPU上并行化。然而，较新的Nvidia GPU通过光线追踪核心提供了树操作的硬件支持。最近的研究提出使用RT核心实现kNN搜索，但它们都对搜索中使用的距离度量施加了硬件限制——欧几里得距离。我们提出并实现了两种缩减方法，以支持广泛范围内的距离（而不仅仅是欧几里得距离）的kNN：Arkade Filter-Refine和Arkade Monotone Transformation。我们的缩减方法使得基于非欧几里得距离的最近邻查询可以用欧几里得距离的形式来执行。通过我们的缩减方法，我们观察到kNN搜索时间在各种最先进的GPU着色器核心和RT核心基线上的加速比在1.6倍至200倍和1.3倍至33.1倍之间。在评估中，我们通过分析kNN搜索时间趋势，提供了关于RT架构有效构建和遍历树的几个见解。

提出使用Arkade Filter-Refine和Arkade Monotone Transformation两种方法来支持更广泛的距离度量进行kNN搜索，解决了在GPU上实现kNN搜索中距离度量受限的问题。

使用硬件支持的光线追踪核心来实现基于树的kNN搜索，通过Arkade Filter-Refine和Arkade Monotone Transformation两种方法将非欧几里得距离转化为欧几里得距离，从而支持更广泛的距离度量。

实验结果表明，相较于当前GPU着色器核心和光线追踪核心的基线，使用两种方法的kNN搜索时间加速范围分别为1.6x-200x和1.3x-33.1x。论文提供了关于光线追踪架构有效构建和遍历树的几个见解。

最近的相关研究包括：1. 'Efficient kNN Search on GPUs with Partial Sorting' 2. 'kNN Search on GPUs with CUDA' 3. 'Efficient kNN Graph Construction and Querying on GPUs'