The KNN algorithm is very handy and particularly suited to some of my problems, but I can't find any resources on how to implement it in production.
As a comparative example, when I use a neural network, I already have at my disposal high level tools allowing me to apply the neural network to examples (either libraries allowing me to smartly exploit the hardware of my devices when I want to do embedded, or infrastructures allowing me to use my neural networks at a lower cost if I want to run them on the cloud), and these tools are generally black boxes and are very well optimized, especially when you pass them batches of examples.
It seems that there are no such tools to use a KNN on a large scale for example on a cloud; and I guess one has to implement it oneself.
A naive implementation of KNN consisting in calculating the distances from the inferred example to all known and recorded examples makes the computational cost and thus the financial cost of using it explode (which strangely enough becomes much higher than the one I pay when I use a neural network, even though the algorithm seems simpler).
Do you know people who have shared efficient and cheap implementations of KNN? Or do you have any ideas on the subject ?
I started to imagine heuristics to quickly disqualify examples that are too far away without having to go through them one by one.
Concretely, this would consist in a set of n-dimensional nested grids such that searching in each sequence of nested grids is like searching in a tree or in a hash table and allows to locate the example in as many bins as sequences of nested grids. One then expects that the closest examples are either in the same bin or in a contiguous bin (because the example may be close to the bin boundary).
I suppose one could also imagine dividing the space into decision zones (so that a 1-KNN would generate a Voronoi diagram for example).
However, I am not a researcher and my ideas will certainly not be able to challenge the state of the art or already existing and explored ideas.