Why is KNN slow at prediction time and poor with many features?
KNN must compare a query against every stored training row, so prediction cost grows with data size. With many features, distances between points become almost equal, so 'nearest' stops meaning much. This is the curse of dimensionality.
Explain it simply
Finding the nearest tea stall in your lane is easy. Finding the single nearest person matching 500 characteristics (age, height, taste, city, and so on) is hard, because nobody is close on all 500 at once. Everyone is roughly equally "far".
And KNN has to scan every stored record at prediction time, like a clerk who checks the whole register for each customer.
Example
Cost: with n training rows and d features, a brute-force prediction takes about n x d operations per query. With 1,000,000 rows and 50 features that is 50,000,000 distance operations for one prediction.
Speed-ups:
KD-tree / Ball-tree : tree search, fast for low d (roughly under 20)
Approximate search : libraries like FAISS or Annoy, trade tiny accuracy for speed
Fewer rows/features : prototype selection, feature selection, PCAIn scikit-learn, KNeighborsClassifier(algorithm="auto") picks among brute force, KD-tree and ball-tree.
High dimensions: in a unit cube, random points get nearly the same distance to each other as d grows, so the nearest and farthest neighbour are almost equally far. Reduce dimensions with feature selection or PCA before using KNN.
What to say in the interview
"KNN is a lazy learner: training is instant but each prediction scans the stored data, so it scales badly with rows. With many features, distances concentrate and neighbours lose meaning. I use tree indexes or approximate search for speed and reduce dimensions first."
Common mistakes
- Assuming KNN is cheap because it has no training step.
- Adding many irrelevant features to a KNN model.