A Performance Study of Traversing Spatial Indexing Structures in Parallel on GPU

CUDA is a parallel programming environment that enables significant performance improvement by leveraging the massively parallel processing capability of the GPU. Inherently spatial indexing structures such as R-Trees are not well suited for CUDA environment due to its irregular tree traversal for range queries. Traversing irregular tree search paths makes it hard to maximize the utilization of many-core architectures. In this paper, we propose assigning an individual sub-tree to each SMP (streaming multi-processor) in GPGPU, such that CUDA cores in the same SMP co-operate to navigate tree index nodes. This parallel partitioned-indexing improves the utilization of many cores in GPGPU significantly. Also, we propose a new range query search algorithm - three-phase-search that avoids non-sequential random access to tree nodes and accelerates the search performance of spatial indexing structures on GPU. Our experimental results show that GPU-based parallel spatial indexing scheme on NVIDA Tesla M2090 GPGPU outperforms the CPU-based multi-threaded R-trees on AMD Opteron 6128HE processor by two times.