A stochastic approach to k-nearest neighbors search using a fixed radius method

What the paper says

This study aims to optimize the [Formula: see text]-nearest neighbors search (kNN search) by reducing the computational burden of the well-known Brute-force method while providing the same solution. While there exist rule-based approaches for reducing the computational burden of the kNN search, methods that use the stochastic patterns inherent to the data are lacking. Our method leverages data structures and probabilistic assumptions to enhance the scalability of the search. By focusing on the Training set where our neighbors reside, we define a sample space that limits the [Formula: see text]-nearest neighbors search to a smaller space. For each observation in the Query set (e.g., the set of observations for which a classification is desired), a fixed radius search is employed, with the radius stochastically linked to the desired number of neighbors. This approach allows us to find the [Formula: see text]-nearest neighbors using only a fraction of the entire Training set in contrast to the Brute-force method, which requires distances to be calculated between each observation in the Training set and each observation in the Query set. Through simulations and a theoretical computational complexity analysis, we demonstrate that our method outperforms the Brute-force approach, particularly when the Training and Query set sample sizes are large. In addition, a benchmarked comparison of our approach and the Brute-force method on an Alzheimer's disease data set further demonstrated this, showing a 27.57-fold improvement in total elapsed time. Overall, our stochastic approach significantly reduces the computational load of kNN search while maintaining accuracy, making it a viable alternative to traditional methods for large datasets.