Hardware Acceleration for Spatial Selection and Join

Unlike traditional relational database operations which are typicallyI/O bound, many spatial database operations are CPU-intensive due tothe complexity of the spatial objects and the complexity of theunderlying computational geometry algorithms. In this paper, wepropose a novel approach to accelerate spatial selections and joinswith computer graphics hardware. Our work is focused on hardware-basedimplementation of the polygon-polygon intersection test,which is the computational primitive for many spatial database operations.The general approach is to use graphics hardware to render the polygoninteriors or boundaries, then check the frame buffer foroverlapping pixels. Due to the disparity between the data resolution and thepixel resolution, the main challenge is to provide not only speed improvements,but also the high accuracy required by spatial database applications.We develop three approximations algorithms using hardware blending andaccumulation functions. The blending-based algorithm is simple and fast,and the two accumulation-based algorithms provide provable guarantees oneither precision or recall at a small cost of efficiency. We also show thatby combining the accumulation-based algorithms with the conventionalsoftware approach, significant speedup can be achieved for complex datawithout sacrificing accuracy.