多边形间空间关系查询的异构多核架构并行算法

• 作者: 由志杰 谢传节 马益杭 龙舟
• 来源期刊: 测绘学报
• 学科: 地球科学
• 关键词: 异构多核 并行计算 拓扑关系 空间关系查询
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 地图学与地理信息
• 页码范围: 119-126
• 页数: 8页
• 分类号: P208
• 字数: 5070字
• 语种: 中文
• DOI: 10.11947/j.AGCS.2016.20140463

摘要

目前在空间关系查询中常用的Plane Sweep算法是一种串行算法,在处理海量空间数据时效率较低,而已有的并行计算方法对于普通的计算机并不适用.本文针对这个问题,提出了一种多边形间空间关系查询的异构多核架构并行算法,该算法先利用STR树索引过滤掉不相交的多边形,然后将过滤后的多边形数据集合分解为点集合和边集合,并对其构建四叉树索引;在保证数据浮点运算精度符合要求的情况下,利用GPU强大的批量运算能力快速处理边与边的相交情况并据此逐步计算得到环间的拓扑关系,再根据环间拓扑关系计算得到多边形间的维度扩展九交模型(DE-9IM)参数值;根据DE-9IM参数值与空间关系查询条件相比对,输出查询结果.最后通过试验验证了算法的准确性与高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢传节	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	28	676	10.0	26.0
2	马益杭	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	3	38	2.0	3.0
6	由志杰	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	2	8	1.0	2.0
10	龙舟	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	2	8	1.0	2.0