| 多边形间空间关系查询的异构多核架构并行算法 |
| |
| 引用本文： | 谢传节,龙舟,马益杭,由志杰.多边形间空间关系查询的异构多核架构并行算法[J].测绘学报,2016,45(1):119-126. |
| |
| 作者姓名： | 谢传节 龙舟 马益杭 由志杰 |
| |
| 作者单位： | 1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101;2. 中国科学院大学, 北京 100049 |
| |
| 基金项目： | 国家863计划(2011AA120302;2012AA12A401)，海洋公益性项目(201105033-6)，The National High-tech Research and Development Program of China (863 Program)(.2011AA120302 |
| |
| 摘 要： | 目前在空间关系查询中常用的Plane Sweep算法是一种串行算法,在处理海量空间数据时效率较低,而已有的并行计算方法对于普通的计算机并不适用。本文针对这个问题,提出了一种多边形间空间关系查询的异构多核架构并行算法,该算法先利用STR树索引过滤掉不相交的多边形,然后将过滤后的多边形数据集合分解为点集合和边集合,并对其构建四叉树索引;在保证数据浮点运算精度符合要求的情况下,利用GPU强大的批量运算能力快速处理边与边的相交情况并据此逐步计算得到环间的拓扑关系,再根据环间拓扑关系计算得到多边形间的维度扩展九交模型(DE-9IM)参数值;根据DE-9IM参数值与空间关系查询条件相比对,输出查询结果。最后通过试验验证了算法的准确性与高效性。
|
| 关 键 词： | 异构多核 并行计算 拓扑关系 空间关系查询 |
| 收稿时间： | 2014-09-04 |
| 修稿时间： | 2015-05-04 |
Parallel Algorithm of Spatial Relationship Query between Polygons Based on Heterogeneous Multi-core Architecture |
| |
| XIE Chuanjie,LONG Zhou,MA Yihang,YOU Zhijie.Parallel Algorithm of Spatial Relationship Query between Polygons Based on Heterogeneous Multi-core Architecture[J].Acta Geodaetica et Cartographica Sinica,2016,45(1):119-126. |
| |
| Authors: | XIE Chuanjie LONG Zhou MA Yihang YOU Zhijie |
| |
| Institution: | 1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China;2. University of Chinese Academy of Sciences, Beijing 100049, China |
| |
| Abstract: | The commonly used Plane Sweep algorithm in the spatial relationship query is a serial algorithm, when dealing with huge amounts of spatial data, the efficiency is very low,and the existing parallel computing method is not applicable to normal computer. Aiming at this problem, this paper proposes a parallel algorithm of spatial relationship query between polygons based on heterogeneous multi-core architecture. The algorithm uses STR-tree index to filter out non-intersection polygons first, then decomposes the filtered polygons data into points set and edges set, and constructs a quadtree index for them; under the premise of data accuracy meets the requirement of floating point calculation, uses GPU's powerful batch computing power quickly processing the intersection between edges and calculates the topology relationship between rings, then uses the topology relationship between rings to calculate the DE-9IM model between polygons; compares the DE-9IM model with spatial relationship query condition and outputs the query results. At last, the efficiency and accuracy of the algorithm is verified by experiment. |
| |
| Keywords: | heterogeneous multi-core parallel computing topological relations querying spatial relationship |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《测绘学报》浏览原始摘要信息 |
| 点击此处可从《测绘学报》下载免费的PDF全文 |
|
