KNN efficient implementation 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.
I suggest you use facebook's faiss. It is a library for similarity search, which can be used to compute kNN on large vector collections.
From facebook's own numbers:


With approximate indexing, a brute-force k-nearest-neighbor graph (k = 10) on 128D CNN descriptors of 95 million images of the YFCC100M data set with 10-intersection of 0.8 can be constructed in 35 minutes on four Maxwell Titan X GPUs, including index construction time.
Billion-vector k-nearest-neighbor graphs are now easily within reach. One can make a brute-force k-NN graph (k = 10) of the Deep1B data set with 10-intersection of 0.65 in under 12 hours on four Maxwell Titan X GPUs, or 0.8 in under 12 hours on eight Pascal P100-PCIe GPUs. Lower-quality graphs can be produced in under 5 hours on the Titan X configuration.