Polygon and Polyline Join Using Raster Filters

Processing spatial joins efficiently is crucial to rendering the spatial data analysis process feasible. As pointed out in many works, the exact intersection test of two spatial objects is the most time-consuming and I/O-consuming step in processing spatial joins. The use of approximations can reduce the need for examining the exact geometry of spatial objects in order to find the intersecting ones. In previous works, approximations were proposed to perform spatial joins between similar objects: polygons × polygons or polylines × polylines. This work evaluates the benefits of using approximations in spatial joins performed on polygons and polylines sets. Also, a new algorithm is proposed to compare approximations of polygons and polylines. The experiments performed with real data sets resulted in performance gains validating approach effectiveness. The number of exact intersection tests was reduced by 59%. The overall execution time and number of disk accesses were both reduced by 48%.