Document Type
Article
Language
eng
Publication Date
12-2019
Publisher
Institute of Electrical and Electronics Engineers
Source Publication
2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC)
Source ISSN
2640-0316
Abstract
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.
Recommended Citation
Liu, Yiming; Yang, Jie; and Puri, Satish, "Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU" (2019). Computer Science Faculty Research and Publications. 17.
https://epublications.marquette.edu/comp_fac/17
Comments
Accepted version. 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC), (December 17-20, 2019): 141-151. DOI. © 2019 Institute of Electrical and Electronics Engineers. Used with permission.