GPU-Based Algorithms for Processing the k-CP Query on Spatial Data

Algorithms for processing large-scale spatial datasets are of significant interest in both scientific research and industrial applications. The efficient implementation of such algorithms is crucial for modern data-intensive systems, and GPU-based parallel processing has emerged as a particularly effective approach for accelerating spatial queries. Among these, computing the k closest pairs (k-CP) between large spatial datasets is a fundamental problem with applications in spatial data analysis, geographic information systems, and data mining. This paper presents an exact GPU-based framework for processing k-CP queries in both two- and three-dimensional spaces, including variants capable of processing datasets that exceed the available GPU memory capacity. Starting from a baseline brute-force CUDA implementation, we develop memory-aware partitioning strategies and adapt DSPP-based spatial pruning to reduce unnecessary distance computations in the global k-CP problem. Furthermore, we incorporate several performance optimizations, including pinned memory and concurrent kernel execution, to overlap data transfers with computation and improve scalability. Experimental evaluation using both synthetic and real-world datasets demonstrates that the proposed methods substantially outperform baseline approaches. In particular, the DSPP + PEA variant employing a max-heap buffer generally achieves the best overall performance, especially for large datasets and higher values of k, highlighting its effectiveness and scalability for large-scale spatial query processing.