CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing
Load-balanced spatial partitioning is crucial for achieving high-efficiency distributed spatial join processing. However, existing spatial partitioning methods focus more on balancing data quantity, and there is much less emphasis on accurately quantifying computational loads and generating partitio...
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2025-07-01
|
| Series: | Geo-spatial Information Science |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/10095020.2025.2510364 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850116318276091904 |
|---|---|
| author | Xiangyang Yang Xuefeng Guan Ming Zhang Hang Wu Bo Wang Pengcheng Yin Qingyang Xu Huayi Wu |
| author_facet | Xiangyang Yang Xuefeng Guan Ming Zhang Hang Wu Bo Wang Pengcheng Yin Qingyang Xu Huayi Wu |
| author_sort | Xiangyang Yang |
| collection | DOAJ |
| description | Load-balanced spatial partitioning is crucial for achieving high-efficiency distributed spatial join processing. However, existing spatial partitioning methods focus more on balancing data quantity, and there is much less emphasis on accurately quantifying computational loads and generating partitioning layouts according to the derived loads. To bridge these gaps, we propose a novel partitioning method, i.e. a computational intensity-balanced partitioner (termed CIBPartitioner for short), to enhance the efficiency of distributed spatial join processing by ensuring computational load balance. First, a computational intensity (CI) indicator is defined through theoretical analysis of the time complexity of spatial join processing to quantify the computational loads. Second, a distributed estimation method using grid histograms is introduced to efficiently calculate the distribution of CI. Finally, inspired by the KDBTree, a CI-balanced partitioning scheme is designed to partition the grid cells in the grid histogram according to the CI distribution, which minimizes the CI differences across partitions to achieve a balanced CI layout. Extensive experiments on real-world datasets demonstrate that CIBPartitioner significantly improves computational load balancing and enhances the end-to-end efficiency of distributed spatial join processing compared with popular spatial partitioners, including KDBTree. The source code of CIBPartitioner has been released. |
| format | Article |
| id | doaj-art-54df3a1806ae476181c2bf86211e8abf |
| institution | OA Journals |
| issn | 1009-5020 1993-5153 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Geo-spatial Information Science |
| spelling | doaj-art-54df3a1806ae476181c2bf86211e8abf2025-08-20T02:36:22ZengTaylor & Francis GroupGeo-spatial Information Science1009-50201993-51532025-07-0112010.1080/10095020.2025.2510364CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processingXiangyang Yang0Xuefeng Guan1Ming Zhang2Hang Wu3Bo Wang4Pengcheng Yin5Qingyang Xu6Huayi Wu7State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, ChinaState Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, ChinaGuangzhou Urban Planning & Design Survey Research Institute Co, Ltd, Guangzhou, ChinaGuangzhou Urban Planning & Design Survey Research Institute Co, Ltd, Guangzhou, ChinaGuangzhou Urban Planning & Design Survey Research Institute Co, Ltd, Guangzhou, ChinaSchool of Resource and Environmental Sciences, Wuhan University, Wuhan, ChinaState Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, ChinaState Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, ChinaLoad-balanced spatial partitioning is crucial for achieving high-efficiency distributed spatial join processing. However, existing spatial partitioning methods focus more on balancing data quantity, and there is much less emphasis on accurately quantifying computational loads and generating partitioning layouts according to the derived loads. To bridge these gaps, we propose a novel partitioning method, i.e. a computational intensity-balanced partitioner (termed CIBPartitioner for short), to enhance the efficiency of distributed spatial join processing by ensuring computational load balance. First, a computational intensity (CI) indicator is defined through theoretical analysis of the time complexity of spatial join processing to quantify the computational loads. Second, a distributed estimation method using grid histograms is introduced to efficiently calculate the distribution of CI. Finally, inspired by the KDBTree, a CI-balanced partitioning scheme is designed to partition the grid cells in the grid histogram according to the CI distribution, which minimizes the CI differences across partitions to achieve a balanced CI layout. Extensive experiments on real-world datasets demonstrate that CIBPartitioner significantly improves computational load balancing and enhances the end-to-end efficiency of distributed spatial join processing compared with popular spatial partitioners, including KDBTree. The source code of CIBPartitioner has been released.https://www.tandfonline.com/doi/10.1080/10095020.2025.2510364Distributed spatial joinspatial partitioningload balancingcomputational intensity |
| spellingShingle | Xiangyang Yang Xuefeng Guan Ming Zhang Hang Wu Bo Wang Pengcheng Yin Qingyang Xu Huayi Wu CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing Geo-spatial Information Science Distributed spatial join spatial partitioning load balancing computational intensity |
| title | CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing |
| title_full | CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing |
| title_fullStr | CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing |
| title_full_unstemmed | CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing |
| title_short | CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing |
| title_sort | cibpartitioner a computational intensity balanced partitioner for enhancing distributed spatial join processing |
| topic | Distributed spatial join spatial partitioning load balancing computational intensity |
| url | https://www.tandfonline.com/doi/10.1080/10095020.2025.2510364 |
| work_keys_str_mv | AT xiangyangyang cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT xuefengguan cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT mingzhang cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT hangwu cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT bowang cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT pengchengyin cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT qingyangxu cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing AT huayiwu cibpartitioneracomputationalintensitybalancedpartitionerforenhancingdistributedspatialjoinprocessing |