地球信息科学学报 ›› 2015, Vol. 17 ›› Issue (5): 547-555.doi: 10.3724/SP.J.1047.2015.00547

• 本期要文(可全文下载) • 上一篇    下一篇

一种异构多核架构快速查询多边形图层间空间关系的方法

由志杰1,2, 谢传节1, 马益杭1,2, 龙舟1,2   

  1. 1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京100101;
    2. 中国科学院大学, 北京100049
  • 收稿日期:2014-12-15 修回日期:2015-01-19 出版日期:2015-05-10 发布日期:2015-05-10
  • 通讯作者: 谢传节(1971-),男,副研究员,研究方向为并行地理计算。E-mail:xiecj@lreis.ac.cn E-mail:xiecj@leris.ac.cn
  • 作者简介:由志杰(1990-),男,黑龙江虎林人,硕士生,研究方向为空间信息并行计算。E-mail:youzhijie@foxmail.com
  • 基金资助:

    国家"863"计划项目(2011AA120302、2011AA120306、2012AA12A401);海洋公益性项目(201105033-6)。

A Quick Method for Query Spatial Relationships between Polygon Layers Based on Heterogeneous Multi-core Architecture

YOU Zhijie1,2, XIE Chuanjie1, MA Yihang1,2, LONG Zhou1,2   

  1. 1. State Key Laboratory of Resources and Environmental Information System, Beijing 100101, China;
    2. University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2014-12-15 Revised:2015-01-19 Online:2015-05-10 Published:2015-05-10

摘要:

目前,空间关系查询中常用的Plane Sweep 算法是一种串行方法,而关于多核CPU的并行查询算法,在面对海量数据查询时,由于CPU核心数及线程数量的限制,其难以满足查询效率需求。针对该问题,本文提出了一种全新的异构多核架构多边形图层间空间关系查询的并行算法。首先,利用STR 树索引过滤不相交的多边形;然后,对过滤后多边形的线段构建四叉树索引,利用CPU+GPU架构并行计算线段的相交以判断多边形环间的拓扑关系;再根据环间的拓扑关系计算多边形间的维度扩展九交模型(DE-9IM)参数值,据此确定多边形间的空间关系;最后,通过实验验证了该算法的准确性和高效性。实验表明,本算法能有效缩短大数据量的空间查询时间。在实验中逐渐增加目标数据集和源数据集多边形的数量,当两数据集都为50 000 个多边形时,以包含关系为例,相比于ArcGIS,本文提出的算法可达到2 倍的加速比。

关键词: 空间关系查询, GPU, 异构多核, 并行计算, 拓扑关系

Abstract:

The commonly used Plane Sweep algorithm in spatial relationship query is a serial algorithm. Some scholars had studied some parallel query algorithms that based on multi-core CPU. However, due to the limitations induced by the number of CPU's core and thread, when dealing with massive data query, these methods are incapable to meet the requirements for query efficiency. To solve this problem, this paper proposes a new parallel algorithm of spatial relationship query between polygon layers based on heterogeneous multi-core architecture. The algorithm used STR-tree index to filter the disjointed polygons first. After the filtration, we built a quadtree index to manage the line segments of the polygons, so that we could quickly get the line segment combination to prepare for computing the intersection situations. Then, the CPU+GPU architecture was adopted to parallel compute the line segments'intersection situation. In details, we firstly put each line segment combination into each thread of GPU to calculate the relevant intersection situation, and the intersection type was counted using CPU. Next, the topological relations between the polygon rings were judged according to the type of line segment intersection, thus the values of DE-9IM parameters between these polygons were calculated based on the topological relations, and accordingly, the spatial relationship between the polygons were determined. At last, the efficiency and accuracy of the algorithm was verified by an experiment. In the experiment, we gradually increased the polygon number of the source layer and the target layer. When both of the two layers had 50000 polygons, here took the Contains relation as an example, we found that the computation time of the parallel algorithm is 15.143s faster than ArcGIS, and the speedup ratio can reach up to 2. In general, the parallel algorithm has more obvious advantages in dealing with higher volumes of data.

Key words: querying spatial relationship, GPU, heterogeneous multi-core, parallel computing, topological relations