Parallel Range Query Processing on R-Tree with Graphics Processing Unit

Abstract

Recently, various research efforts have been conducted to develop strategies for accelerating multi-dimensional query processing using the Graphics Processing Units (GPUs). Well-known multidimensional access methods such as R-tree, B-tree and their variants, however, are hardly applicable to GPUs in practice, mainly due to the characteristics of a hierarchical structure. More specifically, the structure not only causes frequent transfers of small volume of data but also gives limited opportunities to exploit GPUs' advanced data parallelism. To address the problems, we propose an approach which uses GPUs as a buffer. Main idea is that object entries in recently visited leaf nodes are buffered in the global memory of the GPU and are processed by massive threads of GPUs in parallel. In this paper, we presented both a single buffer strategy and a multiple buffer strategy since a single buffer strategy has problems deteriorating query performance seriously. Through the extensive performance studies, we observed that the proposed approach achieved up to 5 times higher query performance than the original CPU-based R-trees.