Document Type

Conference Proceeding

Publication Date

11-2020

Publisher

Association for Computing Machinery

Source Publication

SIGSPATIAL '20: Proceedings of the 28th International Conference on Advances in Geographic Information Systems

Source ISSN

978-1-4503-8019-5

Original Item ID

DOI: 10.1145/3397536.3422264

Abstract

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.

Comments

Published in SIGSPATIAL '20: Proceedings of the 28th International Conference on Advances in Geographic Information Systems. Seattle WA, November 3-6, 2020. DOI. © 2020 Association for Computing Machinery (ACM). Used with permission.

Download
Puri_13953acc.pdf (1181 kB)
ADA Accessible Version

Share

COinS