邵华, 江南, 胡斌, 吕恒, 朱进. 利用GPU的R树细粒度并行STR方法批量构建[J]. 武汉大学学报 ( 信息科学版), 2014, 39(9): 1068-1073. DOI: 10.13203/j.whugis20130158
引用本文: 邵华, 江南, 胡斌, 吕恒, 朱进. 利用GPU的R树细粒度并行STR方法批量构建[J]. 武汉大学学报 ( 信息科学版), 2014, 39(9): 1068-1073. DOI: 10.13203/j.whugis20130158
SHAO Hua, JIANG Nan, HU Bin, LV Heng, ZHU Jin. GPU-Based Parallel Bulk Loading R-trees Using STR Methodon Fine-Grained Model[J]. Geomatics and Information Science of Wuhan University, 2014, 39(9): 1068-1073. DOI: 10.13203/j.whugis20130158
Citation: SHAO Hua, JIANG Nan, HU Bin, LV Heng, ZHU Jin. GPU-Based Parallel Bulk Loading R-trees Using STR Methodon Fine-Grained Model[J]. Geomatics and Information Science of Wuhan University, 2014, 39(9): 1068-1073. DOI: 10.13203/j.whugis20130158

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

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

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

     

    Abstract: Objective In the era of big data,efficient spatial indexes need to be established quickly for massivespatial data.The R-tree spatial index built by the sort tile recursive(STR)technique has excellentquery performance but low efficiency when building.We propose an R-tree bulk loading algorithm u-sing a STR technique based on general purpose computing on a GPU.A linear array structure is usedto store an R-tree and an overall sorting algorithm is used instead of segmented sorting.Experimentsshow that our proposed algorithm achieves up to a 27speedup.Our experiments also indicate that thespeedup 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 advan-tage of the parallel processing capacity of the GPU and achieves high efficiency which shows that thetechnology of GPU computing has broad applicability in the spatial indexing field.

     

/

返回文章
返回