Short Paper : Optimized Spatial Join with Grid Sub-Partitioning

Wide variation in the spatial characteristics like shape complexity, data distribution, object density is observed in the real-world data that affect the overall complexity of Spatial Join computation. We analyze 1) the impact of the nature of input data on the execution time 2) evaluate the range of optimum grid size for sub-partitioning to tune the execution time. We compare the suitability and efficiency of brute force spatial join(BFSJ), standard SJoin (provided in GeoPandas library) - with and without spatial indexing (STSJ), and our algorithm with spatial indexing (ISJ) and sub-partitioning (MSJ). A suitable algorithm is recommended along with a range for optimum sub-partition size. Experimental results illustrate a speedup of up to 45% with the proposed method as compared to STSJ and up to 95% gain over BFSJ.