How does the k-nearest neighbors algorithm work?
KNN measures the distance from a new point to every stored example and keeps the k closest. For classification the neighbors vote; for regression their target values are averaged. KNN has no real training step: fitting stores the data, and every prediction pays for the search.
A worked example: a new support ticket is turned into an embedding, and its five nearest past tickets are:
| Neighbor | Distance | Label |
|---|---|---|
| 1 | 0.12 | Billing |
| 2 | 0.18 | Billing |
| 3 | 0.21 | Shipping |
| 4 | 0.30 | Billing |
| 5 | 0.33 | Shipping |
With k = 5 and equal weights, billing wins three votes to two, a 0.6 probability. Weighted by inverse distance, billing scores 1/0.12 + 1/0.18 + 1/0.30 ≈ 17.2 against shipping’s 1/0.21 + 1/0.33 ≈ 7.8, so the closest neighbors count for more.
How do you choose k and the distance metric?
Start from the library defaults and tune k on held-out data. scikit-learn 1.9.1’s KNeighborsClassifier defaults to n_neighbors=5, equal weights and the Minkowski metric with p=2, which is Euclidean distance (scikit-learn docs, read 16 November 2026). Its user guide puts the trade-off plainly: “a larger k suppresses the effects of noise, but makes the classification boundaries less distinct” (Nearest Neighbors guide, read 16 November 2026). A k of 1 memorizes the training set, and a k near the dataset size predicts the majority class everywhere: the first overfits, the second underfits.
Scale features before measuring distance, or the feature with the largest units decides every vote: income in euros swamps age in years. For text embeddings, cosine distance is the usual choice.
Why does KNN slow down on large or high-dimensional data?
Brute-force search compares the query with every stored point. scikit-learn’s guide gives that cost as O[DN²] for N samples in D dimensions across a whole dataset. Tree indexes help in low dimensions: a KD tree “is very fast for low-dimensional (D < 20) neighbors searches”, and scikit-learn’s algorithm='auto' falls back to brute force above 15 dimensions (same guide). In high dimensions distances bunch together, the curse of dimensionality, and exact search stops scaling.
What is the difference between KNN and approximate nearest neighbor search?
Exact KNN returns the true k closest points; approximate nearest neighbor (ANN) search returns almost the closest, much faster.
| Exact KNN | Approximate (ANN) | |
|---|---|---|
| Recall | Perfect | Below 100%, tunable |
| Query cost | Grows with every stored vector | Roughly logarithmic for HNSW |
| Typical index | None, or KD and ball trees | HNSW, IVFFlat |
| Where you meet it | Small tabular models | Vector databases |
pgvector “performs exact nearest neighbor search, which provides perfect recall” by default, and an HNSW or IVFFlat index “trades some recall for speed” (pgvector README, v0.8.7, read 16 November 2026). HNSW comes from Malkov and Yashunin, whose layered graph search “allows a logarithmic complexity scaling” (arXiv:1603.09320, 30 March 2016, read 16 November 2026). Every semantic search query in a RAG system is a nearest-neighbor query, so when retrieval misses a passage, check the index’s recall before blaming the model.