article · Mathematics · 2024
Efficient Parallel Processing of R-Tree on GPUs
Jian Nong, Xi He, Jia Chen, Yanyan Liang
Cited by 1Open access
Abstract
R-tree is an important multi-dimensional data structure widely employed in many applications for storing and querying spatial data. As GPUs emerge as powerful computing hardware platforms, a GPU-based parallel R-tree becomes the key to efficiently port R-tree-related applications to GPUs. However, traditional tree-based data structures can hardly be directly ported to GPUs, and it is also a great challenge to develop highly efficient parallel tree-based data structures on GPUs. The difficulty mostly lies in the design of tree-based data structures and related operations in the context of many-core architecture that can facilitate parallel processing. We summarize our contributions as follows: (i) design a GPU-friendly data structure to store spatial data; (ii) present two parallel R-tree construction algorithms and one parallel R-tree query algorithm that can take the hardware characteristics of GPUs into consideration; and (iii) port the vector map overlay system from CPU to GPU to demonstrate the feasibility of parallel R-tree. Experimental results show that our parallel R-tree on GPU is efficient and practical. Compared with the traditional CPU-based sequential vector map overlay system, our vector map overlay system based on parallel R-tree can achieve nearly 10-fold speedup.
Cite this paper
Nong, J., He, X., Chen, J., & Liang, Y. (2024). Efficient Parallel Processing of R-Tree on GPUs. Mathematics, 12(13), 2115. https://doi.org/10.3390/math12132115
Nong, Jian, et al. “Efficient Parallel Processing of R-Tree on GPUs.” Mathematics, vol. 12, no. 13, 2024, p. 2115, https://doi.org/10.3390/math12132115.
Nong, Jian, Xi He, Jia Chen, and Yanyan Liang. 2024. “Efficient Parallel Processing of R-Tree on GPUs.” Mathematics 12 (13): 2115. https://doi.org/10.3390/math12132115.
Nong, J. et al. (2024) ‘Efficient Parallel Processing of R-Tree on GPUs’, Mathematics, 12(13), p. 2115. Available at: https://doi.org/10.3390/math12132115.
@article{nong2024efficient,
title = {{Efficient Parallel Processing of R-Tree on GPUs}},
author = {Nong, Jian and He, Xi and Chen, Jia and Liang, Yanyan},
journal = {Mathematics},
volume = {12},
number = {13},
pages = {2115},
year = {2024},
doi = {10.3390/math12132115}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.