Machine learning - PCA and KNN on rgb images are too slow I work with python and images of tables (taken from above). My aim is to take a photo of a random table and then find the most similar tables to it in my database. Obviously, the main feature which distinguishes the tables are their shape (square, rectangular, round, oval) but there are also other details.
For now, I am just running a PCA and a KNN on rgb images of tables to find the most similar tables in the database for each of the tables of the database.
The problem is that when I increase the number of rgb images of tables e.g. from 400 to 500 the processing time significantly increases. My final goal is to run this program with 2000 or even 4000 table images so I need a more efficient machine learning algorithm for my task.
Can you recommend me another more efficient machine learning algorithm for this task?
 A: It depends on a lot of parameters. Calling $h$ the height, $w$ the width of the image and $n_{channels}$ then number of channels, probably 3, then we define $p=h*w*n_{channels}$.
The PCA step has a complexity of $O(np^2+p^3)$ for training and O($np$) for predictions. Calling $p'$ the number of principal components you keep, running a (naive) $k$ Nearest Neighbours search on the points will have a complexity of $O(p'n)$.
So increasing the training size by 20% should increase the time taken by 20%, which I find a little puzzling (unless you run into memory issue and other things happen).
Besides, if you want to make your method faster, based on the definition of $p$ you may note that the size of the image is critical. Dividing $w$ and $h$ by two may divide the time taken by the PCA by $(2*2)^2=16$. 
Regarding the kNN step, it is worth noting that there are many smart implementation relying on quadtrees (in R SearchTrees, per example) that significantly decrease the prediction time.
A: Try a faster KNN library.  Some suggestions:
https://github.com/spotify/annoy
https://github.com/FALCONN-LIB/FALCONN 
Comparisons:
https://github.com/erikbern/ann-benchmarks
https://erikbern.com/2016/06/02/approximate-nearest-news.html 
