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

针对大规模空间数据的K-近邻连接查询问题,设计了一种CUDA编程模型下K-近邻连接算法的并行优化方法。将K-近邻连接算法的并行过程分两个阶段:1)对参与查询的数据集P和Q分别建立R-Tree索引；2)基于R-Tree索引进行KNNJ查询。首先根据结点所在位置划分最小外包框,在CUDA下基于递归网格排序算法创建R-Tree索引。然后在CUDA下基于R-Tree索引进行KNNJ查询,其中涉及并行求距离和并行距离排序两个阶段:求距离阶段利用每一个线程计算任意两点之间的距离,点与点之间距离的求取无依赖并行；排序阶段将快速排序基于CUDA以实现并行化。实验结果表明,随着样本量的不断增大,基于R-Tree索引的并行K-近邻连接算法的优势更加明显,具有高效性和可扩展性。

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

In order to solve the problem of K-nearest neighbor join query in large scale spatial data,a parallel optimization 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 obvious,which has high efficiency and scalability.