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.

Euclidean distance transform (EDT) often suffers from high computational complexity and limited processing efficiency, especially when applied to large-scale images. To address these challenges, this paper proposes a GPU-based parallel EDT algorithm. The proposed approach first partitions the input image into multiple horizontal sub-blocks. For each sub-block, a row-wise recursive computation strategy is adopted to construct its Voronoi diagram in parallel, thereby reducing computational overhead by exploiting the strong structural similarity between the Voronoi diagrams of adjacent rows. Based on the Voronoi diagrams of all sub-blocks, the Euclidean distance from each pixel to the nearest background pixel is subsequently evaluated, completing the transform. Experimental results demonstrate that the proposed algorithm achieves up to a 52× speedup over traditional CPU-based EDT methods, leading to a substantial improvement in computational performance. Nevertheless, the scalability of the method is influenced by GPU memory capacity and the chosen sub-block partitioning strategy when processing extremely large images. Moreover, the core idea of leveraging inter-row Voronoi similarity to reduce redundant computation can be naturally extended to higher-dimensional exact EDT as well as approximate EDT variants.