Efficient Computation of the K Nearest Neighbors Query Using Incremental Radius on a k²-tree

Proximity searches within metric spaces are critical for numerous real-world applications, including pattern recognition, multimedia information retrieval, and spatial data analysis, among others.With the exponential increase in data volume, the demand for memory-efficient structures to store and process information has become increasingly important. In this paper, we present an alternative algorithm for efficient computation of the K nearest neighbors (KNN) query using the k2-tree compact data structure, using the incremental radius technique. This approach offers an alternative to the existing algorithm that utilizes a priority queue over k2-trees. Through both theoretical and experimental analysis, we demonstrate that our proposed algorithm is up to 2 times faster compared to the priority queue-based solution, while also providing substantial improvements in memory efficiency.