中文

Journal of Shanghai University（Natural Science Edition） ›› 2012, Vol. 18 ›› Issue (3): 305-310.doi: 10.3969/j.issn.1007-2861.2012.03.017

• Computer Engineering and Science • Previous Articles     Next Articles

Optimization of Neighbor Searching Problem on  CUDA Based on KD-TRIE and Its Application

BAO Nan-sen1,LI Zheng-jie1,CHAI Ya-hui1,2,XU Wei-min1   

  1. (1. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China;2. School of Information Engineering Department, East China Jiaotong University, Nanchang 330013, China)
  • Online:2012-06-30 Published:2012-06-30

PDF

1156

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., 106). 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)

CLC Number: