Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Pateras et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: