留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

邵华 江南 胡斌 吕恒 朱进

邵华, 江南, 胡斌, 吕恒, 朱进. 利用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方法批量构建

doi: 10.13203/j.whugis20130158
基金项目: 国家科技支撑计划资助项目(2012BAH35B000);国家科技基础条件平台建设项目;江苏高校优势学科建设工程资助项目
详细信息
    作者简介:

    邵华,博士生,主要从事高性能空间分析和空间数据挖掘研究。

    通讯作者: 江南
  • 中图分类号: P208

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

Funds: The National Key Technology R&D Program of China,No.2012BAH35B000;the National R&D Infrastructure andFacility Development Program of China;the Priority Academic Program Development of Jiangsu Higher Education Institutions.
More Information
    Author Bio:

    SHAO Hua,PhD candidate,specializes in high performance spatial analysis and spatial data mining.

    Corresponding author: JIANG Nan
  • 摘要: 目的 大数据时代,需要对海量空间数据更快速地建立高效索引,使用递归排序网格(STR)方法构建的R树具有优秀的查询性能,但构建效率不高。本文利用基于计算机图形处理器(GPU)的通用计算具有细粒度可并行性的特点,提出了一种基于STR算法的R树GPU并行构建算法,使用线性数据结构存储R树,并且用整体排序代替分段排序,细化算法的并行粒度。实验结果表明,同CPU算法相比,本文算法的加速比最高可达27倍,并且呈现出随着数据量增大而变大的趋势。本文算法充分利用GPU的并行处理能力,高效构建了性能优越的R树空间索引。
  • [1] Papadopoulos A,Manolopoulos Y.Parallel Bulk-loading of Spatial Data[J].Parallel Computing,2003,29(10):1419-1444[2] Guttman A.R-trees:A Aynamic Index Structurefor Spatial Searching[C].ACM SIGMOD,Boston,MA,1984[3] Sellis T,Roussopoulos N,Faloutsos C.The R+-tree:A Dynamic Index for Multi-dimensional Ob-jects[C].The 13th VLDB,Brighton,England,1987[4] Bechmann N,Kriegel H P,Schneider R,et al.TheR*-tree:An Efficient and Robust Access Methodfor Points and Rectangles[C].SIGM OD,AtlanticCity,New Jersey,1990[5] Roussopoulos N,Leifker D.Direct Spatial Searchon Pictorial Databases Using Packed R-trees[C].ACM SIGMOD,Austin,TX,1985[6] Liu J,Liu T,Wu H,et al.From Graphic Process-ing Unit to General Purpose Graphic Processing U-nit[J].Journal of Wuhan University(NaturalScience Edition),2013,59(2):198-206(刘金硕,刘天晓,吴慧,等.从图形处理器到基于GPU的通用计算[J].武汉大学学报(理学版),2013,(2):198-206)[7] Simion B,Ray S,Brown A D.Speeding up SpatialDatabase Query Execution Using GPUs[J].Proce-dia Computer Science,2012,(9):1870-1879[8] Kim J,Hong S,Nam B.A Performance Study ofTraversing Spatial Indexing Structures in Parallel onGPU[C].IEEE 14th International Conference onHigh Performance Computing and Communications.Liverpool,United Kingdom,2012[9] Yang K,He B,Fang R,et al.In-memory GridFiles on Graphics Processors[C].The 3rd Interna-tional Workshop on Data management on NewHardware,ACM,Beijing,China,2007[10]Lijuan L,Wong M D F,Leong L.Parallel Imple-mentation of R-trees on the GPU[C].The 17th A-sia and South Pacific Design Automation Confer-ence,San Francisco,USA,2012[11]You S,Zhang J.GPU-based Spatial Indexing and1072 第39卷第9期 邵 华等:利用GPU的R树细粒度并行STR方法批量构建Query Processing Using R-Trees[EB/OL].http://www-cs.ccny.cuny.edu/~jzhang/papers/rtree_tr.pdf,2012[12]Leutenegger S T,Lopez M A,Edgington J.STR:A Simple and Efficient Algorithm for R-tree Packing[C].The 13th International Conference on DataEngineering,Birmingham,England,1997[13]Kamel I,Faloutsos C.On Packing R-trees[C].CIKM,Washington D C,USA,1993[14]Zhang Mingbo,Lu Feng,Shen Paiwei,et al.Evolvement and Progress of R-tree Family[J].Chi-nese Journal of Computers,2005,28(3):289-300(张明波,陆锋,申排伟,等.R树家族的演变和发展[J].计算机学报,2005,28(3):289-300)[15]Garcia Y,Lopez M,Leutenegger S.A Greedy Al-gorithm for Bulk Loading R-trees[C].The 6thACM-GIS,Washington D C,1998[16]Lee T,Lee S.Omt:Overlap Minimizing Top-downBulk Loading Algorithm for R-tree[J].AdvancedInformation Systems Engineering,2003(7):69-72[17]Micikevicius P.Comparison-Based In-place Sortingwith CUDA[M]//Wen-Mei W H.GPU ComputingGems.Waltham,MA:Morgan Kaufmann,2011
  • [1] 向隆刚, 高萌, 王德浩, 龚健雅.  Geohash-Trees:一种用于组织大规模轨迹的自适应索引 . 武汉大学学报 ● 信息科学版, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
    [2] 于安斌, 梅文胜.  一种R树与格网结合的海量地铁隧道点云管理方法 . 武汉大学学报 ● 信息科学版, 2019, 44(10): 1553-1559. doi: 10.13203/j.whugis20170419
    [3] 董路明, 张斌, 赵学胜.  一种基于GPU Tessellation的地形无缝绘制算法 . 武汉大学学报 ● 信息科学版, 2017, 42(3): 402-407. doi: 10.13203/j.whugis20140850
    [4] 翟卫欣, 程承旗, 童晓冲, 陈波.  利用地球立体剖分格网生成Subdivision R-树索引模型 . 武汉大学学报 ● 信息科学版, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
    [5] 刘坡, 龚建华.  大规模遥感影像全球金字塔并行构建方法 . 武汉大学学报 ● 信息科学版, 2016, 41(1): 117-122. doi: 10.13203/j.whugis20130718
    [6] 钟何平, 张森, 田振, 唐劲松.  异构环境下的快速质量引导相位解缠算法 . 武汉大学学报 ● 信息科学版, 2015, 40(6): 756-760. doi: 10.13203/j.whugis20130518
    [7] 胡自和, 刘坡, 龚建华, 王群.  基于虚拟地球的台风多维动态可视化系统的设计与实现 . 武汉大学学报 ● 信息科学版, 2015, 40(10): 1299-1305. doi: 10.13203/j.whugis20130669
    [8] 戴 晶, 吴明光, 郑培蓓, 王 蕾, 崔登吉, 陈泰生.  基于 hilbert曲线的str索引改进算法 . 武汉大学学报 ● 信息科学版, 2014, 39(7): 777-781.
    [9] 付仲良, 刘思远, 俞志强.  一种双映射变换的空间索引及空间连接算法研究 . 武汉大学学报 ● 信息科学版, 2014, 39(10): 1248-1251.
    [10] 孙卡, 吴冲龙, 刘刚, 何珍文.  海量三维地质空间数据的自适应预调度方法 . 武汉大学学报 ● 信息科学版, 2011, 36(2): 140-143.
    [11] 龚俊, 谢潇.  基于R树索引的三维可视化查询方法 . 武汉大学学报 ● 信息科学版, 2011, 36(10): 1140-1143.
    [12] 程昌秀.  矢量数据多尺度空间索引方法的研究 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 597-601.
    [13] 周芹, 钟耳顺, 黄耀欢, 郭会.  大型空间数据库的并发索引策略CQR树 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 856-858.
    [14] 陈鹏, 孟令奎, 宋杨.  三维GIS中基于空间拓扑约束条件的R树研究 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 347-349.
    [15] 余亮, 边馥苓.  一种原生XML空间索引及查询语言 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 936-939.
    [16] 朱庆, 龚俊.  一种改进的真三维R树空间索引方法 . 武汉大学学报 ● 信息科学版, 2006, 31(4): 340-343.
    [17] 郭晶, 刘广军, 董绪荣, 郭磊.  基于空间网格和Hilbert R-tree的二级R-tree空间索引 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1084-1088.
    [18] 谈晓军, 涂建光.  一种自适应的两阶段R树批生成算法 . 武汉大学学报 ● 信息科学版, 2003, 28(1): 31-38.
    [19] 张山山, 杨宗亮.  一种面向GIS的时空索引方法 . 武汉大学学报 ● 信息科学版, 2003, 28(1): 51-54.
    [20] 郭菁, 郭薇, 胡志勇.  大型GIS空间数据库的有效索引结构QR-树 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 306-310.
  • 加载中
计量
  • 文章访问数:  1231
  • HTML全文浏览量:  26
  • PDF下载量:  843
  • 被引次数: 0
出版历程
  • 收稿日期:  2013-05-22
  • 修回日期:  2014-09-05
  • 刊出日期:  2014-09-05

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

doi: 10.13203/j.whugis20130158
    基金项目:  国家科技支撑计划资助项目(2012BAH35B000);国家科技基础条件平台建设项目;江苏高校优势学科建设工程资助项目
    作者简介:

    邵华,博士生,主要从事高性能空间分析和空间数据挖掘研究。

    通讯作者: 江南
  • 中图分类号: P208

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

English Abstract

邵华, 江南, 胡斌, 吕恒, 朱进. 利用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
参考文献 (1)

目录

    /

    返回文章
    返回