Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU
Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU
复制标题
DOI：
10.1109/hipc.2019.00027
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Yiming Liu;Jie Yang;S. Puri
中科院分区：
文献类型：
--
作者：
Yiming Liu;Jie Yang;S. Puri
在本文中，我们介绍了我们的分层过滤器和细化技术，我们已经开发的并行几何相交操作，涉及大型多边形和折线。输入是两层大型多边形数据集，计算是一对跨层多边形的空间相交。这些交集是空间连接和地图叠置计算中计算密集型空间数据分析的核心。我们已经扩展了经典的过滤和细化算法使用PolySketch过滤器，以提高地理空间计算的性能。除了通过最小边界矩形（MBR）过滤多边形之外，我们的分层方法还探索了使用瓦片（较小的MBR）进行进一步过滤，以提高过滤的有效性并减少细化阶段的计算工作量。我们已经实现了这个过滤和细化系统的CPU和GPU上使用的OpenMP和OpenACC。在使用R树后，平均而言，我们的过滤技术仍然可以丢弃69%的多边形对，没有线段交点。PolySketch过滤器平均减少了99.77%的查找线段交点的工作量。基于PNP的任务简化和条带化算法平均过滤掉了95.84%的Point-in-Polygon测试工作量。我们的CPU-GPU系统使用NVidia Titan V和Titan Xp GPU在大约10秒内对两个shapefiles，即USA Water Bodies和USA Block Group Boundary执行683 K多边形的空间连接。
In this paper, we introduce our hierarchical filter and refinement technique that we have developed for parallel geometric intersection operations involving large polygons and polylines. The inputs are two layers of large polygonal datasets and the computations are spatial intersection on a pair of cross-layer polygons. These intersections are the compute-intensive spatial data analytic kernels in spatial join and map overlay computations. We have extended the classical filter and refine algorithms using PolySketch Filter to improve the performance of geospatial computations. In addition to filtering polygons by their Minimum Bounding Rectangle (MBR), our hierarchical approach explores further filtering using tiles (smaller MBRs) to increase the effectiveness of filtering and decrease the computational workload in the refinement phase. We have implemented this filter and refine system on CPU and GPU by using OpenMP and OpenACC. After using R-tree, on average, our filter technique can still discard 69% of polygon pairs which do not have segment intersection points. PolySketch filter reduces on average 99.77% of the workload of finding line segment intersections. PNP based task reduction and Striping algorithms filter out on average 95.84% of the workload of Point-in-Polygon tests. Our CPU-GPU system performs spatial join on two shapefiles, namely USA Water Bodies and USA Block Group Boundaries with 683K polygons in about 10 seconds using NVidia Titan V and Titan Xp GPU.