GeoInformatica Информационные системы

K Nearest neighbor join algorithms for spatial data using compact and plain data structures in main memory

Guillermo de Bernardo, Miguel R. Penabad, Antonio Corral, Michael Vassilakopoulos, Nieves R. Brisaboa
Springer Nature · 2026-09-10 · DOI 10.1007/s10707-026-00591-1

Аннотация

Abstract The K Nearest Neighbors Query ( K NNQ) is a fundamental distance-based query with applications in Geographic Information Systems (GIS) and many other domains. The K Nearest Neighbors Join Query ( K NNJQ) combines K NNQ with the join operation to find the K nearest neighbors from a dataset P to every object in another dataset Q . Due to the large number of distance computations involved, K NNJQ is an expensive operation that poses a challenge for in-memory systems. In this paper, we propose and evaluate novel in-memory algorithms for K NNQ and K NNJQ using the compact data structure $$k^2$$ -tree. The proposed algorithms exploit hierarchical spatial decomposition together with grouping, pre-processing and progressive pruning techniques. In addition, we develop two new plane-sweep algorithms for K NNQ and K NNJQ, that improve the brute-force algorithms by reducing redundant computations. We conduct an extensive experimental evaluation using real-world spatial datasets to evaluate the performance of our K NNQ and K NNJQ algorithms, comparing them with KD-tree and R*-tree based algorithms. Our results highlight the efficiency of pruning techniques in $$k^2$$ -trees, which reduce distance computations and response time by up to an order of magnitude in K NNJQ, in comparison with the equivalent KD-tree, R*-tree and plane-sweep algorithms.

Читать у издателя →