Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization
As core algorithms of geographic computing, overlay analysis algorithms typically have computation-intensive and data-intensive characteristics. It is highly important to optimize overlay analysis algorithms by parallelizing the vector polygons after reasonable data division. To address the problem...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/14/5/2006 |
| _version_ | 1797264772159242240 |
|---|---|
| author | Junfu Fan Jiwei Zuo Guangwei Sun Zongwen Shi Yu Gao Yi Zhang |
| author_facet | Junfu Fan Jiwei Zuo Guangwei Sun Zongwen Shi Yu Gao Yi Zhang |
| author_sort | Junfu Fan |
| collection | DOAJ |
| description | As core algorithms of geographic computing, overlay analysis algorithms typically have computation-intensive and data-intensive characteristics. It is highly important to optimize overlay analysis algorithms by parallelizing the vector polygons after reasonable data division. To address the problem of unbalanced data partitioning in the task decomposition process for parallel polygon overlay analysis and calculation, this paper presents a data partitioning method based on shape complexity index optimization, which achieves data equalization among multicore parallel computing tasks. Taking the intersection operator and difference operator of the Vatti algorithm as examples, six polygon shape indexes are selected to construct the shape complexity model, and the vector data are divided in accordance with the calculated shape complexity results. Finally, multicore parallelism is achieved based on OpenMP. The experimental results show that when a data set with a large amount of data is used, the effect of the multicore parallel execution of the Vatti algorithm’s intersection operator and difference operator based on shape complexity division is clearly improved. With 16 threads, compared with the serial algorithm, speedups of 29 times and 32 times can be obtained. Compared with the traditional multicore parallel algorithm based on polygon number division, the speed can be improved by 33% and 29%, and the load balancing index is reduced. For a data set with a small amount of data, the acceleration effect of this method is similar to that of traditional methods involving multicore parallelism. |
| first_indexed | 2024-04-25T00:34:12Z |
| format | Article |
| id | doaj.art-481f4c8de5ef43ea9ff4d87cb0e2cc67 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-04-25T00:34:12Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-481f4c8de5ef43ea9ff4d87cb0e2cc672024-03-12T16:39:47ZengMDPI AGApplied Sciences2076-34172024-02-01145200610.3390/app14052006Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index OptimizationJunfu Fan0Jiwei Zuo1Guangwei Sun2Zongwen Shi3Yu Gao4Yi Zhang5School of Civil Engineering and Geomatics, Shandong University of Technology, Zibo 255000, ChinaSchool of Civil Engineering and Geomatics, Shandong University of Technology, Zibo 255000, ChinaSchool of Civil Engineering and Geomatics, Shandong University of Technology, Zibo 255000, ChinaSchool of Civil Engineering and Geomatics, Shandong University of Technology, Zibo 255000, ChinaSchool of Civil Engineering and Geomatics, Shandong University of Technology, Zibo 255000, ChinaCollege of Land and Resources and Surveying & Mapping Engineering, Shandong Agriculture and Engineering University, Jinan 250100, ChinaAs core algorithms of geographic computing, overlay analysis algorithms typically have computation-intensive and data-intensive characteristics. It is highly important to optimize overlay analysis algorithms by parallelizing the vector polygons after reasonable data division. To address the problem of unbalanced data partitioning in the task decomposition process for parallel polygon overlay analysis and calculation, this paper presents a data partitioning method based on shape complexity index optimization, which achieves data equalization among multicore parallel computing tasks. Taking the intersection operator and difference operator of the Vatti algorithm as examples, six polygon shape indexes are selected to construct the shape complexity model, and the vector data are divided in accordance with the calculated shape complexity results. Finally, multicore parallelism is achieved based on OpenMP. The experimental results show that when a data set with a large amount of data is used, the effect of the multicore parallel execution of the Vatti algorithm’s intersection operator and difference operator based on shape complexity division is clearly improved. With 16 threads, compared with the serial algorithm, speedups of 29 times and 32 times can be obtained. Compared with the traditional multicore parallel algorithm based on polygon number division, the speed can be improved by 33% and 29%, and the load balancing index is reduced. For a data set with a small amount of data, the acceleration effect of this method is similar to that of traditional methods involving multicore parallelism.https://www.mdpi.com/2076-3417/14/5/2006overlay analysisshape complexitydata partitioningparallel computingacceleration ratioload balancing |
| spellingShingle | Junfu Fan Jiwei Zuo Guangwei Sun Zongwen Shi Yu Gao Yi Zhang Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization Applied Sciences overlay analysis shape complexity data partitioning parallel computing acceleration ratio load balancing |
| title | Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization |
| title_full | Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization |
| title_fullStr | Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization |
| title_full_unstemmed | Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization |
| title_short | Multicore Parallelized Spatial Overlay Analysis Algorithm Using Vector Polygon Shape Complexity Index Optimization |
| title_sort | multicore parallelized spatial overlay analysis algorithm using vector polygon shape complexity index optimization |
| topic | overlay analysis shape complexity data partitioning parallel computing acceleration ratio load balancing |
| url | https://www.mdpi.com/2076-3417/14/5/2006 |
| work_keys_str_mv | AT junfufan multicoreparallelizedspatialoverlayanalysisalgorithmusingvectorpolygonshapecomplexityindexoptimization AT jiweizuo multicoreparallelizedspatialoverlayanalysisalgorithmusingvectorpolygonshapecomplexityindexoptimization AT guangweisun multicoreparallelizedspatialoverlayanalysisalgorithmusingvectorpolygonshapecomplexityindexoptimization AT zongwenshi multicoreparallelizedspatialoverlayanalysisalgorithmusingvectorpolygonshapecomplexityindexoptimization AT yugao multicoreparallelizedspatialoverlayanalysisalgorithmusingvectorpolygonshapecomplexityindexoptimization AT yizhang multicoreparallelizedspatialoverlayanalysisalgorithmusingvectorpolygonshapecomplexityindexoptimization |