RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search
RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search
复制标题
RT-kNNS Unbound：使用 RT 内核加速无限制邻居搜索
DOI：
10.1145/3577193.3593738
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Kulkarni, Milind
中科院分区：
文献类型：
--
作者：
Nagarajan, Vani;Mandarapu, Durga;Kulkarni, Milind
识别点的k-最近邻（kNNS）的问题已被证明是非常有用的，无论是作为一个独立的应用程序，并作为一个子程序在较大的应用程序。鉴于其在机器学习和点云等领域的广泛适用性，广泛的研究已经进入利用GPU加速来解决这个问题。最近的工作表明，与使用着色器核心的传统加速相比，在最近的GPU中使用光线跟踪核心来加速kNNS要高效得多。然而，现有的翻译kNNS的光线跟踪问题施加了约束的搜索空间的邻居。因此，我们只能使用RT核心来加速固定半径的NNS，这需要用户设置搜索半径优先级，因此可能会错过邻居。在这项工作中，我们提出了TrueKNN，第一个有界RT加速的邻居搜索。TrueKNN采用迭代方法，我们逐步增加搜索空间，直到所有点都找到它们的kneighbors。我们表明，我们的方法比现有的方法快几个数量级，甚至可以用来加速固定半径的邻居搜索。
The problem of identifying the k-Nearest Neighbors (kNNS) of a point has proven to be very useful both as a standalone application and as a subroutine in larger applications. Given its far-reaching applicability in areas such as machine learning and point clouds, extensive research has gone into leveraging GPU acceleration to solve this problem. Recent work has shown that using Ray Tracing cores in recent GPUs to accelerate kNNS is much more efficient compared to traditional acceleration using shader cores. However, the existing translation of kNNS to a ray tracing problem imposes a constraint on the search space for neighbors. Due to this, we can only use RT cores to acceleratefixed-radiuskNNS, which requires the user to set a search radiusa prioriand hence can miss neighbors. In this work, we propose TrueKNN, the firstunboundedRT-accelerated neighbor search. TrueKNN adopts an iterative approach where we incrementally grow the search space until all points have found theirkneighbors. We show that our approach is orders of magnitude faster than existing approaches and can even be used to accelerate fixed-radius neighbor searches.
登录
查看更多内容
用于地球大气和近太空环境科学研究的 GPS 数据处理
DOI：
--
发表时间：
2017
期刊：
ACM SIGSPATIAL International Workshop on Advances in Geographic Information Systems
影响因子：
--
作者：
V. Pankratius;A. Coster;J. Vierinen;P. Erickson;W. Rideout
通讯作者：
W. Rideout
DOI：
10.1109/tvcg.2020.3042930
发表时间：
2020-12
影响因子：
5.2
作者：
N. Morrical;I. Wald;W. Usher;Valerio Pascucci
通讯作者：
N. Morrical;I. Wald;W. Usher;Valerio Pascucci
DOI：
10.1145/3503221.3508409
发表时间：
2022-01
期刊：
Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Yuhao Zhu
通讯作者：
Yuhao Zhu
影响因子：
9.2
作者：
Geiger, A.;Lenz, P.;Urtasun, R.
通讯作者：
Urtasun, R.
影响因子：
22.7
作者：
Andoni, Alexandr;Indyk, Piotr
通讯作者：
Indyk, Piotr