KNN efficient implementation

Question

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 library 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 of 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 explodes (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 of 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.

Answer 1

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.

Answer 2

To add what @noe has written which is very true,

Complexity of KNN always depends on 1) number of dimension 2) the distance function

If you have many many number of dimensions one can use a dimension reduction algorithm and perform the KNN on top. The dimension reduction can be something very simple for example a PCA where you do KNN on first top N components or something more complex as an auto-encoder where there are many embedding layers. If you are thinking about the real-time scenario the de-coding also will add into the running time so you have see which combination of a dimension-reduction + knn gives you the best performance.

You talked about "production" - well, bare in mind in production you won't train a model. That means you are supposed to have a trained model (all distances among the training point) (not an N*N-1/2) and just calculate the distance between "test/incoming" observation with you training subjects. So it will be N times calculation if you have N training points.

Of course I also recommend Dask which has a built-in KNN implementation e.g. here and here.