Bernardo, Guillermo deRodríguez Penabad, MiguelCorral, AntonioVassilakopoulos, MichaelBrisaboa, Nieves R.2026-10-142026-10-142026Bernardo, G. de, Penabad, M.R., Corral, A. et al. K Nearest neighbor join algorithms for spatial data using compact and plain data structures in main memory. Geoinformatica 30, 33 (2026). https://doi.org/10.1007/s10707-026-00591-11573-7624https://hdl.handle.net/2183/49709Financiado para publicación en acceso aberto: CRUE-CSIC/Springer Nature Data sets used in the experimental evaluation of this work are available at https://doi.org/10.5281/zenodo.17544411[Abstract] The K Nearest Neighbors Query (KNNQ) is a fundamental distance-based query with applications in Geographic Information Systems (GIS) and many other domains. The K Nearest Neighbors Join Query (KNNJQ) combines KNNQ 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, KNNJQ is an expensive operation that poses a challenge for in-memory systems. In this paper, we propose and evaluate novel in-memory algorithms for KNNQ and KNNJQ using the compact data structure k2-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 KNNQ and KNNJQ, 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 KNNQ and KNNJQ algorithms, comparing them with KD-tree and R*-tree based algorithms. Our results highlight the efficiency of pruning techniques in k2-trees, which reduce distance computations and response time by up to an order of magnitude in KNNJQ, in comparison with the equivalent KD-tree, R*-tree and plane-sweep algorithms.engAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/K nearest neighbors join queryk2-treePlane-sweepSpatial query evaluationjournal articleopen access10.1007/s10707-026-00591-1