Computer Engineering and Science

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

Expand
  • (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 published: 2012-06-30

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.

Cite this article

BAO Nan-sen1,LI Zheng-jie1,CHAI Ya-hui1,2,XU Wei-min1 . Optimization of Neighbor Searching Problem on  CUDA Based on KD-TRIE and Its Application[J]. Journal of Shanghai University, 2012 , 18(3) : 305 -310 . DOI: 10.3969/j.issn.1007-2861.2012.03.017

Outlines

/