Fine-Grained Quadtree-based Polygon Indexing in CudaGIS (Initial Design & Implementation)

Different from indexing MBRs of polygons using quadtree/R-Trees [1] (Oracle Spatial) or generalized indexing search trees [2] ( PostgreSQL/PostGIS), Microsoft SQLServer Spatial decomposes polygons into four levels of grid cells with adjustable cell sizes so that these grid cells can be indexed by B+-Tree for query processing [3] as illustrated in the left side of Fig. 1. Indexing polygons directly through decompositions is computationally intensive and it is desirable to use GPU accelerations. Different from using a fixed number of grid levels as used in SQLServer Spatial, our idea is to construct quadtrees on polygons by examining spatial relationships (outside, intersect and inside) between quadrants under a quadtree node with a polygon in parallel and construct child nodes based on the resulting spatial relationships (white, gray and black nodes, respectively) and expand the quadrants that intersect with the polygon as necessary level by level as illustrated in the right side of Fig. 1. We next discuss the criteria in determining the spatial relationships and the mapping between the level-wise construction algorithm and the GPU hardware by exploiting fine-grained parallelism