Efficient Filters for Geometric Intersection Computations using GPU
Efficient Filters for Geometric Intersection Computations using GPU
复制标题
DOI：
10.1145/3397536.3422264
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Yiming Liu;S. Puri
中科院分区：
文献类型：
--
作者：
Yiming Liu;S. Puri
几何求交算法是地理信息系统(GIS)空间分析的基础。应用高性能计算对海量空间数据进行几何求交，以获得实时结果是必要的。在给定候选对的两个输入几何图形(多边形或折线)的情况下，我们引入了一种新的两步地理空间过滤器，该过滤器首先创建几何图形的草图并使用它来检测工作量，然后根据草图的公共区域对草图进行细化，以减少细化阶段的总计算量。我们称这种过滤器为基于PolySketch的CMBR(PSCMBR)过滤器。我们展示了该过滤器在加速线段交叉点(LSI)报告任务中的应用，这是多边形覆盖和空间连接等各种地理空间应用中的基本计算。我们还开发了一个基于PolySketch的并行PNP过滤器，用于在GPU上执行PNP测试，从而减少了PNP测试的计算工作量。最后，我们将这些新的过滤器集成到层次过滤和细化(HIFiRE)系统中来解决几何求交问题。我们使用CUDA在GPU上实现了新的过滤和细化系统。与现有的滤波器相比，本文提出的新的滤波器减少了更多的计算量。因此，与之前版本的HIFiRE系统相比，我们的平均加速比为7.96倍。
Geometric intersection algorithms are fundamental in spatial analysis in Geographic Information System (GIS). Applying high performance computing to perform geometric intersection on huge amount of spatial data to get real-time results is necessary. Given two input geometries (polygon or polyline) of a candidate pair, we introduce a new two-step geospatial filter that first creates sketches of the geometries and uses it to detect workload and then refines the sketches by the common areas of sketches to decrease the overall computations in the refine phase. We call this filter PolySketch-based CMBR (PSCMBR) filter. We show the application of this filter in speeding-up line segment intersections (LSI) reporting task that is a basic computation in a variety of geospatial applications like polygon overlay and spatial join. We also developed a parallel PolySketch-based PNP filter to perform PNP tests on GPU which reduces computational workload in PNP tests. Finally, we integrated these new filters to the hierarchical filter and refinement (HiFiRe) system to solve geometric intersection problem. We have implemented the new filter and refine system on GPU using CUDA. The new filters introduced in this paper reduce more computational workload when compared to existing filters. As a result, we get on average 7.96X speedup compared to our prior version of HiFiRe system.