How do KD-trees and ball-trees speed up KNN, and when do they stop helping?
mediumAnswer
- Both are spatial index structures that let you skip large portions of the training set during queries.
- KD-trees split axis-aligned; efficient for low-dimensional data (~≤ 20 dims) with continuous features.
- Ball-trees split with hyperspheres; better for non-Euclidean metrics and moderate dimensions.
- Both degrade to brute force as dimensions grow (~50+), because the pruning becomes ineffective — then approximate methods (HNSW, FAISS, LSH) are the practical way to scale.
Check yourself — multiple choice
- They work best at 1000+ dimensions
- KD-tree / ball-tree accelerate low- to moderate-dim queries; use ANN (HNSW, FAISS) for high dim
- They only work for classification
- They increase memory but not speed
KD-tree/ball-tree scale to moderate dims; high-dim demands approximate NN structures.
#knn#optimization
Practise Supervised Learning
215 interview questions in this topic.
Related questions
- What is Empirical Risk Minimization?
- Why do we care whether the loss landscape is convex?
- Why does OLS have a closed-form solution but logistic regression doesn't?
- Why do we use cross-entropy (log loss) instead of MSE for classification?
- How is logistic regression fit in practice?
- Your scikit-learn logistic regression warns 'lbfgs failed to converge'. What do you do?