关键词: CUDA, KD-TRIE, 图形处理器, k-最邻近结点算法

Abstract: This paper describes the construction of a KD-TRIE on CUDA, and the search and preprocessing for solving particle neighbor searching problem. The experimental results show that it is efficient to use KD-TRIE to search the CUDA when the search radius is not very large (e.g., 0.01 and 0.001 of the entire problem space diameter) and the data scale is relatively large (e.g., 10⁶). Compare to the brute force method, the speedup factor is about 5 000 to 15 000. However, if the search radius is too large, the speedup factor will drop. Various optimization methods discussed can be used to raise the speedup factor.

Key words: CUDA, graphic processing unit (GPU), KD-TRIE, k-nearest neighbor algorithm (kNN)