Distance Metrics & Indexing

Distance metrics define similarity in feature space and directly drive the results of KNN, clustering, and retrieval. Common metrics: Euclidean distance $d_2(x, y) = \sqrt{\sum_i (x_i - y_i)^2}$ (L2, most natural when all dimensions share scale); Manhattan distance $d_1(x, y) = \sum_i |x_i - y_i|$ (L1, more robust to outliers and more stable in high dimensions); cosine similarity $\cos \theta = \frac{x \cdot y}{\Vert x \Vert \Vert y \Vert}$ (direction only, magnitude-invariant — the default for TF-IDF/embedding retrieval); Minkowski distance $d_p(x, y) = \left( \sum_i |x_i - y_i|^p \right)^{1/p}$ unifies them ($p=1$ Manhattan, $p=2$ Euclidean).Indexing: a KD-Tree recursively bisects space at coordinate medians, giving $O(\log n)$-scale low-dimensional queries; a Ball-Tree partitions with hyperspheres and degrades more gracefully in higher dimensions. Feature scaling matters: variables with larger magnitudes dominate the distance unless z-scored (or min-max normalized) first.

the similarity core of KNN and K-Means, text/vector retrieval (cosine), recommendation recall, anomaly detection; interviews often ask when to choose Euclidean vs cosine and how KD-Tree works.

no single metric covers all semantics — Euclidean assumes equal, commensurable dimensions; cosine removes document-length bias in text; L1 resists outliers; and in high dimensions $L_p$ norms lose contrast as $p$ grows (relative distances converge), which is why cosine/Manhattan are preferred there. KD-Tree/Ball-Tree cut naive $O(nd)$ KNN queries to $O(\log n)$ scale in low dimensions, but degrade in high dimensions where ANN schemes are needed.

Write the Euclidean, Manhattan, and cosine similarity formulas; how does Minkowski distance unify them?

Why is cosine similarity $\cos \theta = \frac{x \cdot y}{\Vert x \Vert \Vert y \Vert}$ invariant to vector length? Why is it standard for text retrieval?

Euclidean vs cosine vs Manhattan — when to use each? Why is L1 more stable than L2 in high dimensions?

How does a KD-Tree build and query? Why does it degrade toward a linear scan in high dimensions?

Why is feature scaling essential for distances? How do different scales distort them? What is the standardization formula?