Symbolic Intersect Detection: A Method for Improving Spatial Intersect Joins

Due to the increasing popularity of spatial databases, researchers have focused their efforts on improving the query processing performance of the most expensive spatial database operation: the spatial join. While most previous work focused on optimizing the filter step, it has been discovered recently that, for typical GIS data sets, the refinement step of spatial join processing actually requires a longer processing time than the filter step. Furthermore, two-thirds of the time in processing the refinement step is devoted to the computation of polygon intersections. To address this issue, we therefore introduce a novel approach to spatial join optimization that drastically reduces the time of the refinement step. We propose a new approach called Symbolic Intersect Detection (SID) for early detection of true hits. Our SID optimization eliminates most of the expensive polygon intersect computations required by a spatial join by exploiting the symbolic topological relationships between the two candidate polygons and their overlapping minimum bounding rectangle. One important feature of our SID optimization is that it is complementary to the state-of-the-art methods in spatial join processing and therefore can be utilized by these techniques to further optimize their performance. In this paper, we also develop an analytical cost model that characterizes SIDs effectiveness under various conditions. Based on real map data, we furthermore conduct an experimental evaluation comparing the performance of the spatial joins with SID against the state-of-the-art approach. Our experimental results show that SID can effectively identify more than 80% of the true hits with negligible overhead. Consequently, with SID, the time needed for resolving polygon intersect in the refinement step is improved by over 50% over known techniques, as predicted by our analytical model.