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

摘要：

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

关键词：R树、GPU、批量构建、细粒度并行、空间索引

分类号：P208(一般性问题)

资助基金：国家科技支撑计划资助项目2012BAH35B000；国家科技基础条件平台建设项目；江苏高校优势学科建设工程资助项目。

在线出版日期：2014-08-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：24-25