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

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.