Euclidean Distance

Euclidean distance is the straight-line distance between two points in Euclidean space. For vectors a and b in n-dimensional space, it is calculated as the square root of the sum of squared differences: distance(a, b) = √(Σ (a_i - b_i)²). This is the geometric interpretation of the L2 norm of the difference vector (a - b).

Euclidean distance satisfies the four axioms defining a metric, making it a rigorous measure for similarity:

• Non-negativity: d(a, b) ≥ 0
• Identity of Indiscernibles: d(a, b) = 0 if and only if a = b
• Symmetry: d(a, b) = d(b, a)
• Triangle Inequality: d(a, c) ≤ d(a, b) + d(b, c) These properties ensure consistent and interpretable results in vector search.

Unlike cosine similarity, Euclidean distance is sensitive to the magnitude (norm) of vectors. Two vectors pointing in the same direction but with different lengths will have a large Euclidean distance. This makes it the preferred metric when vector magnitude carries semantic information, such as in models where the L2 norm of an embedding is constrained or meaningful.

In high-dimensional spaces, Euclidean distance becomes less discriminative—a phenomenon central to the curse of dimensionality. As dimensions increase, the relative difference between the nearest and farthest neighbor distances shrinks, making all points appear almost equidistant. This challenges the efficiency and meaningfulness of nearest neighbor search and motivates dimensionality reduction or alternative indexing strategies.

For unit vectors (vectors normalized to L2 norm = 1), Euclidean distance and cosine similarity are monotonically related. The squared Euclidean distance between two unit vectors u and v is 2 - 2 * cos(θ), where cos(θ) is their dot product. Therefore, for normalized embeddings, minimizing Euclidean distance is equivalent to maximizing cosine similarity. This is not true for non-normalized vectors.

In practice, the square root operation in the Euclidean distance formula is often omitted for efficiency, as ordering by squared Euclidean distance preserves the nearest neighbor ranking. This optimization is critical in Approximate Nearest Neighbor (ANN) libraries like Faiss and ScaNN, where distance computations are the primary bottleneck. For normalized vectors, computing Euclidean distance can be less efficient than direct maximum inner product search (MIPS).

k-Nearest Neighbors (k-NN) is the fundamental search problem solved using Euclidean distance. Given a query vector, the goal is to find the 'k' database vectors with the smallest Euclidean distances. This is the core objective of vector search systems.

• Exact k-NN requires computing distances to all vectors (brute-force).
• Approximate k-NN (ANN) uses indices like HNSW or IVF to find approximate nearest neighbors much faster, trading perfect accuracy for speed.
• The choice of 'k' balances result richness against computational cost and relevance.

Cosine similarity measures the cosine of the angle between two vectors, independent of their magnitude. It is a primary alternative to Euclidean distance for similarity search.

• Key Difference: Cosine similarity cares about orientation; Euclidean distance cares about magnitude and orientation.
• Relationship: For L2-normalized vectors (unit vectors), cosine similarity and Euclidean distance are monotonically related: vectors with high cosine similarity have low Euclidean distance.
• Use Case: Dominant for text embeddings (e.g., from sentence transformers) where vector magnitude is less informative than direction.

Maximum Inner Product Search (MIPS) is the problem of finding vectors with the highest dot product (inner product) with a query. It is distinct from, but related to, Euclidean distance search.

• Critical Distinction: MIPS does not assume vectors are normalized. It is the objective in recommendation systems using user/item embeddings.
• Mathematical Link: For normalized vectors, MIPS is equivalent to minimizing Euclidean distance. For unnormalized vectors, specialized techniques (like ScaNN) are required.
• Euclidean distance can be used for MIPS if vectors are normalized, otherwise, direct optimization for the inner product is necessary.

Recall@K is the definitive metric for evaluating the accuracy of an Approximate Nearest Neighbor (ANN) search system using Euclidean distance.

• Definition: It measures the fraction of the true top-K nearest neighbors (found by exact search) that are retrieved by the approximate search. Formula: Recall@K = (|ApproxTopK ∩ TrueTopK|) / K.
• Interpretation: A Recall@K of 0.95 means 95% of the true nearest neighbors were found in the approximate result set.
• Trade-off: ANN systems tune parameters (like efSearch in HNSW) to balance Recall@K against search latency. Higher recall typically requires more computation.

The L2 Norm (or Euclidean norm) is the length of a vector and is directly used in the computation of Euclidean distance.

• Calculation: For a vector v, its L2 norm is ||v|| = sqrt(v₁² + v₂² + ... + vₙ²).
• Role in Distance: Euclidean distance between vectors p and q is the L2 norm of their difference: d(p, q) = ||p - q||.
• Normalization: Dividing a vector by its L2 norm transforms it into a unit vector on the surface of a hypersphere. This is a common pre-processing step to make Euclidean distance equivalent to cosine distance.

Manhattan Distance (or L1 distance) is an alternative distance metric defined as the sum of the absolute differences between vector components.

• Formula: d(p, q) = |p₁ - q₁| + |p₂ - q₂| + ... + |pₙ - qₙ|.
• Comparison to Euclidean: It measures distance along axes (like city blocks), not the straight line. It is less sensitive to large differences in a single dimension.
• Use Case: Often used in computer vision and scenarios where feature differences are additive. It induces a different geometric "shape" (a diamond) for nearest-neighbor regions compared to Euclidean's sphere.