利用GPU的R树细粒度并行STR方法批量构建

GPU-Based Parallel Bulk Loading R-trees Using STR Method on Fine-Grained Model

大数据时代,需要对海量空间数据更快速地建立高效索引,使用递归排序网格(STR)方法构建的R树具有优秀的查询性能,但构建效率不高。本文利用基于计算机图形处理器(GPU)的通用计算具有细粒度可并行性的特点,提出了一种基于STR算法的R树GPU并行构建算法,使用线性数据结构存储R树,并且用整体排序代替分段排序,细化算法的并行粒度。实验结果表明,同CPU算法相比,本文算法的加速比最高可达27倍,并且呈现出随着数据量增大而变大的趋势。本文算法充分利用GPU的并行处理能力,高效构建了性能优越的R树空间索引。

In the era of big data, efficient spatial indexes need to be established quickly for massive spatial data. The R-tree spatial index built by the sort tile recursive （STR） technique has excellent query performance but low efficiency when building. We propose an R-tree bulk loading algorithm using a STR technique based on general purpose computing on a GPU, A linear array structure is used to store an R-tree and an overall sorting algorithm is used instead of segmented sorting. Experiments show that our proposed algorithm achieves up to a 27 speedup. Our experiments also indicate that the speedup increases as the data becomes larger. We use a query algorithm on the GPU to verify the R- tree bulk loading algorithm; finding that it has good query performance. Our algorithm takes advantage of the parallel processing capacity of the GPU and achieves high efficiency which shows that the technology of GPU computing has broad applicability in the spatial indexing field.