.png){kind=icon}
.png){kind=icon}
Return
CIBPartitioner: a computational intensity-balanced partitioner for enhancing distributed spatial join processing
.png){kind=icon}
OA
AI
DOI：10.1080/10095020.2025.2510364.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 ofCI. Finally, inspired by the KDBTree, a CI-balanced partitioning scheme is designed to partition the grid cells in the grid histogram according to theCIdistribution, which minimizes theCIdifferences across partitions to achieve a balancedCIlayout. 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.
Keywords:
Distributed spatial join
spatial partitioning
load balancing
computational intensity
Journal
G
IF:
5.5
Papers:
837
Citations:
2.4K