基于CUDA的并行K-近邻连接算法实现  

Implementation of Parallel K-Nearest Neighbor Join Algorithm Based on CUDA

作　　者：潘茜[1] 张育平[1] 陈海燕[1] PAN Qian ZHANG Yu-ping CHEN Hai-yan(School of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机科学》2016年第10期190-192,219,共4页Computer Science

基　　金：国家重点基础研究发展计划(973计划)(2014CB744900);南京航空航天大学研究生创新基地开放基金(KFJJ201460)资助

摘　　要：针对大规模空间数据的K-近邻连接查询问题,设计了一种CUDA编程模型下K-近邻连接算法的并行优化方法。将K-近邻连接算法的并行过程分两个阶段:1)对参与查询的数据集P和Q分别建立R-Tree索引;2)基于RTree索引进行KNNJ查询。首先根据结点所在位置划分最小外包框,在CUDA下基于递归网格排序算法创建RTree索引。然后在CUDA下基于R-Tree索引进行KNNJ查询,其中涉及并行求距离和并行距离排序两个阶段:求距离阶段利用每一个线程计算任意两点之间的距离,点与点之间距离的求取无依赖并行;排序阶段将快速排序基于CUDA以实现并行化。实验结果表明,随着样本量的不断增大,基于R-Tree索引的并行K-近邻连接算法的优势更加明显,具有高效性和可扩展性。In order to solve the problem of K-nearest neighbor join query in large scale spatial data,a parallel optimiza- tion method of K-nearest neighbor join algorithm based on CUDA programming model was designed. The parallel process of K-nearest neighbor join algorithm is divided into two stages. One is to establish the R-Tree index for the data set Q and P participate in the query,and the other is to carry out the KNNJ query based on R-Tree index Firstly,MBR is created according to the location of nodes, and the R-Tree index is created based on SRT by CUDA. Then, the KNNJ query is made based on the R-Tree index, including parallel computing and parallel sorting. The distance between two points can be calculated by each thread on the parallel, and quicksort is executed in parallel on the CUDA. Experimental results show that with the increase of sample size, the advantages of parallel K-nearest neighbor algorithm are more ob- vious, which has high efficiency and scalability.

关 键 词：CUDA K-近邻连接 空间查询 并行计算 R-Tree索引 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]