Parallel algorithms for spatial data partition and join processing
Yanchun Zhang, Jitian Xiao, Anthony John Roberts · 2002
The spatial join operations combine two sets of spatial data by their spatial relationships. They are among the most important, yet most time-consuming operations in spatial databases. We consider the problem of binary polygon intersection joins based on the filter-and-refine strategy. Our objective is to minimize the I/O cost and the response time for the refinement step. First, a graph model is proposed to formalize the refinement cost and matrix-based sequential data partition algorithms are introduced. Then a parallel data partitioning algorithm is developed with a detailed complexity analysis. Based on the data partition results, a distribution algorithm is also proposed for scheduling parallel spatial join processing.