The Fast $k-\text{NN}$ Algorithm Based on a Fixed Grid Method

$k-\text{Nearest}$
Neighbor
$(k-\text{NN})$
is a well-known instance-based learning algorithm; widely used in pattern recognition. A
$k-\text{NN}$
classifier can generate highly accurate predictions if provided with sufficient training instances. Thus, it plays a pivotal role in many fields. However, though its accuracy can improve with more data, the need for computational resources increases as well. In this paper, we propose a novel approach which pre-partitions instance space into smaller cells in order to reduce computational cost and greatly reduce the time complexity. Assume every instance is mapped to a point in the
$d-\text{dimensional}$
Euclidean space and a training set
$D$
contains
$n$
training instances. Given a query instance, the brute force
$k-\text{NN}$
algorithm has the
$O(nd)$
time complexity for predicting the class of a query instance. This algorithm can improve the time complexity.