GPU-Based Parallel Bulk Loading R-trees Using STR Methodon Fine-Grained Model

Objective In the era of big data,efficient spatial indexes need to be established quickly for massivespatial data.The R-tree spatial index built by the sort tile recursive(STR)technique has excellentquery performance but low efficiency when building.We propose an R-tree bulk loading algorithm u-sing a STR technique based on general purpose computing on a GPU.A linear array structure is usedto store an R-tree and an overall sorting algorithm is used instead of segmented sorting.Experimentsshow that our proposed algorithm achieves up to a 27speedup.Our experiments also indicate that thespeedup increases as the data becomes larger.We use a query algorithm on the GPU to verify the R-tree bulk loading algorithm;finding that it has good query performance.Our algorithm takes advan-tage of the parallel processing capacity of the GPU and achieves high efficiency which shows that thetechnology of GPU computing has broad applicability in the spatial indexing field.