Euclidean Distance (L2)

The Euclidean distance between two points x and y in an n-dimensional space is defined as the square root of the sum of squared differences across all dimensions:

d(x, y) = √( Σ (x_i - y_i)² )

• This is the L2 norm of the difference vector (x - y).
• It is derived from the Pythagorean theorem generalized to n dimensions.
• For example, in 2D space, the distance between points (1, 2) and (4, 6) is √((1-4)² + (2-6)²) = √(9 + 16) = 5.

Euclidean distance satisfies the four axioms of a true metric, which is essential for indexing guarantees:

• Non-negativity: d(x, y) ≥ 0
• Identity of Indiscernibles: d(x, y) = 0 if and only if x = y
• Symmetry: d(x, y) = d(y, x)
• Triangle Inequality: d(x, z) ≤ d(x, y) + d(y, z)

The triangle inequality is particularly crucial. It allows indexing structures like Voronoi diagrams (used in IVF) and graphs (used in HNSW) to prune impossible search paths, guaranteeing no false dismissals in exact search.

Unlike cosine similarity, Euclidean distance is sensitive to the magnitude (norm) of vectors. This has major implications for embedding data:

• Vectors with similar direction but different lengths can have a large Euclidean distance.
• For example, document embeddings where frequency influences magnitude (like TF-IDF) may be better compared with cosine similarity.
• Normalization (scaling vectors to unit length) is a common pre-processing step. For normalized vectors, Euclidean distance and cosine similarity are monotonically related: d² = 2(1 - cos(θ)).
• This property dictates when to choose L2 over cosine or inner product as the primary distance metric.

Calculating Euclidean distance is computationally intensive for high-dimensional vectors, impacting both indexing and query latency.

• The squared Euclidean distance (omitting the square root) is often used for ranking, as it preserves order and saves an expensive operation.
• SIMD instructions (Single Instruction, Multiple Data) on modern CPUs are heavily optimized for the fused multiply-add operations required for L2 distance calculations.
• Inverted index structures like IVF reduce computation by only calculating distances for vectors in a few selected Voronoi cells.
• Compression techniques like Product Quantization (PQ) approximate distances using lookup tables, trading some accuracy for massive speedups.

In very high-dimensional spaces (common with modern embeddings like 768d or 1536d), Euclidean distance exhibits counter-intuitive behavior known as the curse of dimensionality.

• The relative contrast between the nearest and farthest neighbor distances diminishes. All points become almost equidistant.
• This reduces the discriminative power of the metric, making approximate nearest neighbor (ANN) search essential.
• Indexing algorithms must be designed to handle this "distance concentration." Graph-based methods like HNSW and hashing methods like LSH are popular ANN solutions that work around this limitation for L2 space.

Euclidean distance is part of a family of Minkowski distances. Understanding its relation to other common metrics is key for system design.

• Manhattan (L1) Distance: Sum of absolute differences. Less sensitive to outliers than L2. d(x, y) = Σ |x_i - y_i|
• Cosine Similarity: Measures angular separation, ignoring magnitude. Defined as the dot product of normalized vectors.
• Inner Product (IP): For normalized vectors, IP(x, y) = 1 - 0.5 * d²(x, y). Many vector databases (e.g., Pinecone, Weaviate) allow indexing optimized for IP when vectors are normalized.
• Choice of metric is a hyperparameter that must match the embedding model's training objective (e.g., Sentence-BERT models are typically optimized for cosine similarity).

The k-Nearest Neighbors algorithm is a classic instance-based learning method that classifies a data point based on the majority class among its 'k' closest neighbors in the feature space. Euclidean distance is the most common metric for determining this proximity, especially for continuous numerical features. For example, in a system recommending movies, a user's preference vector (based on genre ratings) can be compared to others using L2 distance to find the most similar users and suggest films they enjoyed.

• Core Mechanism: For a query point, calculate its Euclidean distance to every point in the training set, identify the 'k' smallest distances, and assign the most frequent class label among those neighbors.
• Consideration: Performance degrades with high-dimensional data due to the 'curse of dimensionality', where Euclidean distances become less meaningful.

The k-Means clustering algorithm partitions a dataset into 'k' distinct, non-overlapping subgroups. It relies iteratively on Euclidean distance to assign data points to the nearest cluster centroid and to recalculate the centroids as the mean of all assigned points.

• Algorithm Steps: 1) Initialize 'k' centroids. 2) Assignment Step: Assign each point to the cluster whose centroid is closest (minimizing within-cluster variance, which is the sum of squared Euclidean distances). 3) Update Step: Recompute centroids as the mean of points in each cluster. Repeat steps 2-3 until convergence.
• Key Property: k-Means implicitly assumes clusters are spherical and of similar size because it minimizes variance, a property directly tied to L2 distance.

Principal Component Analysis (PCA) is a technique for reducing the dimensionality of data while preserving as much variance as possible. The principal components are the orthogonal directions of maximum variance in the data. Euclidean distance is foundational because PCA aims to preserve the pairwise L2 distances between points as much as possible in the lower-dimensional projection.

• Variance Maximization: Finding components that maximize the sum of squared distances (L2) of the projected points from the origin.
• Reconstruction Error: PCA finds the lower-dimensional representation that minimizes the reconstruction error, defined as the sum of squared Euclidean distances between the original data points and their reconstructions.

In supervised learning, particularly linear regression, the Mean Squared Error (MSE) loss function is the standard metric for model optimization. MSE is directly proportional to the sum of squared Euclidean distances between the model's predicted values and the true target values.

• Mathematical Form: (MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2). This is the squared L2 norm of the error vector.
• Optimization: Minimizing MSE (via gradient descent) is equivalent to finding the model parameters that make the predictions as close as possible to the true values in a Euclidean sense. It strongly penalizes large errors due to the squaring operation.

Euclidean distance is a straightforward yet effective measure for identifying anomalies in low to moderate-dimensional data. The core assumption is that normal data points reside in dense regions, while anomalies are far from their neighbors.

• Distance-Based Methods: Algorithms like k-NN distance classify a point as an outlier if the distance to its k-th nearest neighbor exceeds a threshold.
• Cluster-Based Methods: In methods like DBSCAN, points that are not within a specified Euclidean distance (epsilon) of any core point are labeled as noise/outliers.
• Limitation: Like k-NN, its effectiveness diminishes in very high-dimensional spaces where distance concentration occurs.

In computer vision, images are often represented as high-dimensional feature vectors extracted by a convolutional neural network. Euclidean distance between these embedding vectors provides a robust measure of visual similarity.

• Process: An image database is indexed by its feature vectors. A query image is converted to a vector, and a k-NN search using L2 distance retrieves the most visually similar images.
• Use Case: Reverse image search, product recommendation ('find similar items'), and deduplication of near-identical images in large datasets. For normalized feature vectors, cosine similarity is often preferred, but L2 distance on unnormalized vectors can capture differences in feature magnitude, which may be meaningful.

A distance metric that measures the cosine of the angle between two non-zero vectors. Unlike Euclidean distance, it focuses on orientation rather than magnitude, making it ideal for comparing text embeddings where vector length can vary with term frequency.

• Key Difference: Cosine similarity is invariant to vector magnitude; Euclidean distance is not.
• Use Case: Standard for semantic text search (e.g., comparing sentence-BERT embeddings).
• Mathematical Relationship: For L2-normalized vectors, cosine similarity and Euclidean distance are monotonically related: higher cosine similarity corresponds to lower Euclidean distance.

A distance metric calculated as the sum of the products of corresponding vector components. For many vector databases, it serves as the primary similarity measure.

• Relation to L2: For vectors normalized to unit length, maximizing inner product is equivalent to minimizing Euclidean distance.
• Performance: Often computationally cheaper to compute than Euclidean distance as it avoids a square root operation.
• Common Application: The default similarity measure in many dense retrieval models and vector database indexes.

Also known as L1 distance or taxicab distance, it calculates the sum of the absolute differences between vector coordinates. It represents the distance between points measured along axes at right angles.

• Contrast with L2: L1 is more robust to outliers than L2 because large differences are not squared.
• Use Case: Common in computer vision and scenarios where feature differences are additive.
• Mathematical Form: distance = Σ |x_i - y_i|. It induces a different geometry (diamond-shaped unit circle) compared to L2's sphere.

A generalized distance metric of which both Manhattan (L1) and Euclidean (L2) distances are special cases. It is defined by a parameter p.

• General Formula: distance = (Σ |x_i - y_i|^p)^(1/p).
• When p=1: It becomes Manhattan distance.
• When p=2: It becomes Euclidean distance.
• Higher p values: Increase the influence of the largest coordinate difference, approaching the Chebyshev distance (L∞) as p approaches infinity.

A formal distance metric must satisfy four mathematical axioms. Euclidean distance is a canonical example.

• Non-negativity: d(x, y) ≥ 0
• Identity of Indiscernibles: d(x, y) = 0 if and only if x = y
• Symmetry: d(x, y) = d(y, x)
• Triangle Inequality: d(x, z) ≤ d(x, y) + d(y, z)

These properties guarantee consistent behavior for indexing and search algorithms. Some similarity measures, like cosine similarity on non-normalized vectors, are not proper metrics.

The square of the standard Euclidean (L2) distance, omitting the final square root operation. It is often used as an optimization in computation.

• Mathematical Form: distance_sq = Σ (x_i - y_i)^2.
• Performance Benefit: Removing the square root saves a computationally expensive operation. Since the square root is a monotonic function, sorting by squared distance yields the same nearest neighbor ranking.
• Primary Use: The default internal calculation in many high-performance libraries like Faiss and Milvus for speed. Results are often labeled as 'L2' distance despite this implementation detail.