Fast Hilbert R-tree Bulk-loading Scheme using GPGPU

Sidong Yang, Wonik Choi

http://doi.org/

In spatial databases, R tree is one of the most widely used indexing structures and many variants have been proposed for its performance improvement. Among these variants, Hilbert R tree is a representative method using Hilbert curve to process large amounts of data without high cost split techniques to construct the R tree. This Hilbert R tree, however, is hardly applicable to large scale applications in practice mainly due to high pre processing costs and slow bulk load time. To overcome the limitations of Hilbert R tree, we propose a novel approach for parallelizing Hilbert mapping and thus accelerating bulk loading of Hilbert R tree on GPU memory. Hilbert R tree based on GPU improves bulk loading performance by applying the inversed cell method and exploiting parallelism for packing the R tree structure. Our experimental results show that the proposed scheme is up to 45 times faster compared to the traditional CPU based bulk loading schemes.