Distance Metric

Euclidean distance calculates the straight-line distance between two points in Euclidean space. It is the most intuitive geometric distance, computed as the square root of the sum of squared differences between corresponding vector components.

• Formula: (d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2})
• Use Case: The default for many similarity tasks where absolute magnitude matters, such as image feature matching or physics-based embeddings.
• Index Impact: Algorithms like k-means clustering for IVF and graph construction for HNSW often optimize for L2 distance, making it the most widely supported metric.

Cosine similarity measures the cosine of the angle between two vectors, assessing orientation rather than magnitude. Cosine distance is derived as 1 - cosine similarity.

• Formula: Similarity = (\frac{\mathbf{x} \cdot \mathbf{y}}{|\mathbf{x}||\mathbf{y}|}). Distance = (1 - \text{similarity}).
• Use Case: Dominant in text and NLP applications (e.g., sentence embeddings from models like SBERT) where document length is irrelevant to meaning.
• Index Impact: Many vector databases internally optimize cosine distance by L2-normalizing all vectors, allowing the use of highly optimized Euclidean distance indexes. The distance between normalized vectors is: (d_{\text{cos}} = |\mathbf{x} - \mathbf{y}|^2 / 2).

The inner product (or dot product) is a measure of vector alignment and magnitude. For Maximum Inner Product Search (MIPS), the goal is to find vectors maximizing this value.

• Formula: (\text{IP}(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} x_i y_i).
• Use Case: Critical for recommendation systems and learned embeddings where both direction and magnitude contribute to relevance (e.g., user and item embeddings).
• Index Impact: MIPS is not a true distance metric (it doesn't satisfy the triangle inequality). Libraries like SCANN specialize in it. A common technique is to transform vectors to enable L2 search: append a dummy dimension to convert MIPS to nearest neighbor search in L2 space.

Manhattan distance (or L1 norm, Taxicab distance) sums the absolute differences between vector components. It represents the distance traveled on a grid-like path.

• Formula: (d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} |x_i - y_i|).
• Use Case: Useful in domains where differences are additive and independent, such as certain computer vision features, histogram comparison, or robust statistics where outliers have less influence than in L2.
• Index Impact: Less common than L2 or cosine in mainstream vector databases. Support depends on the underlying index library (e.g., FAISS supports L1 for Flat indexes).

These metrics are designed for binary or set-based data representations.

• Jaccard Distance: Measures dissimilarity between finite sample sets. Defined as 1 minus the Jaccard similarity coefficient (size of intersection over size of union).
• Hamming Distance: Counts the number of positions at which the corresponding symbols are different. Used for binary vectors or strings of equal length.
• Use Case: Jaccard for set similarity (e.g., shopping baskets, document shingles). Hamming for compact binary codes generated by hashing or Locality-Sensitive Hashing (LSH) schemes.
• Index Impact: Specialized indexes, like those for LSH, are built directly on these discrete metrics. They are not typically used with dense, float-based embedding indexes.

A true mathematical distance metric must satisfy four axioms:

1. Non-negativity: (d(x, y) \ge 0)
2. Identity of Indiscernibles: (d(x, y) = 0) iff (x = y)
3. Symmetry: (d(x, y) = d(y, x))
4. Triangle Inequality: (d(x, z) \le d(x, y) + d(y, z))

Selection Guide:

• L2: Default for general-purpose, magnitude-sensitive data.
• Cosine: For text, NLP, and any domain where vector direction is primary.
• Inner Product: For recommendation systems and learned similarity where magnitude signals strength.
• L1/Jaccard/Hamming: For specialized binary, set, or robust statistical data.

The metric dictates index algorithm choice, vector preprocessing (e.g., normalization), and the mathematical validity of graph or tree traversal assumptions.

Different distance metrics are optimized by different index families. Euclidean distance (L2) works naturally with Voronoi partitioning in IVF indexes and is the native geometry for many graph-based methods. Inner product (MIPS) requires specialized adaptations, as maximizing inner product does not obey the triangle inequality, making standard graph traversal less reliable. Algorithms like SCANN and HNSW with specific graph construction rules are engineered for MIPS.

Compression techniques like Product Quantization (PQ) and Scalar Quantization must preserve the relative distances defined by the metric. For cosine similarity, vectors are often L2-normalized first, converting the problem to Euclidean distance on a unit sphere, which allows the use of standard PQ codebooks. For inner product, quantization must be designed to minimize error in dot product estimation, often leading to asymmetric distance computation (ADC) where the query remains in full precision.

In graph-based indexes like HNSW, the distance metric defines "closeness." Edge creation during index build uses the metric to connect each new node to its nearest neighbors. For cosine similarity, this typically requires all vectors to be normalized, making the graph a representation of the unit hypersphere. The search traversal algorithm (e.g., greedy search with a priority queue) uses the same metric to evaluate candidates, making the metric intrinsic to the index's connectivity.

In an Inverted File (IVF) index, the dataset is partitioned into Voronoi cells using a coarse quantizer (like k-means clustering). The centroid of each cell is computed using the chosen distance metric. For Euclidean space, centroids are arithmetic means. For cosine similarity on normalized vectors, the centroid must also be normalized, often involving spherical k-means. The probe strategy—how many neighboring cells to search—is also a function of the metric's local geometry.

The computational cost of index construction is heavily influenced by the metric. k-means clustering for IVF, which requires many distance calculations, is more expensive with high-precision metrics. Graph construction for HNSW involves exhaustive nearest-neighbor searches during insertion, again dominated by distance computations. Choosing a simpler or optimized metric (e.g., using squared L2 to avoid sqrt operations) can significantly reduce index build time and resource consumption.

In production systems, vector search is often combined with metadata filtering. The distance metric influences how these operations are interleaved. For Euclidean distance, filters can be applied before or after the vector search with predictable results. For inner product, where scores are unbounded, applying a filter post-search can drastically alter rankings. This forces index architectures to support advanced filtered search strategies, such as modifying graph traversal or IVF probing based on filter predicates.

Cosine Similarity measures the cosine of the angle between two vectors, focusing on their orientation rather than magnitude. It is the standard metric for text embeddings where direction indicates semantic meaning.

• Formula: cos(θ) = (A · B) / (||A|| ||B||)
• Range: -1 to 1, where 1 indicates identical orientation.
• Use Case: Dominant for semantic search with models like Sentence-BERT, where document meaning is encoded in vector direction.
• Index Impact: Many vector databases internally optimize for cosine distance by normalizing vectors to unit length, allowing the use of efficient Maximum Inner Product Search (MIPS).

Euclidean Distance calculates the straight-line distance between two points in vector space. It is the most intuitive geometric distance and is critical for applications where the absolute position and magnitude of vectors matter.

• Formula: √Σ(Aᵢ - Bᵢ)²
• Use Case: Computer vision (image embeddings), spatial data, and any domain where vector coordinates represent measurable features.
• Index Impact: Algorithms like k-means Clustering (used in IVF) and KD-Trees are naturally geometric and often assume Euclidean space. HNSW graphs are typically built using Euclidean distance for navigation.

Inner Product (or dot product) measures the magnitude of projection of one vector onto another. It is the core operation for Maximum Inner Product Search (MIPS), a fundamental problem in recommendation systems.

• Formula: A · B = Σ(Aᵢ * Bᵢ)
• Use Case: Recommendation engines where user and item embeddings are designed so that a higher dot product indicates stronger affinity.
• Index Impact: Not a true metric (can be negative). Libraries like SCANN and FAISS provide specialized indexes for MIPS. For normalized vectors, maximizing inner product is equivalent to minimizing Euclidean distance or maximizing cosine similarity.

Jaccard Similarity measures the overlap between two finite sets, defined as the size of their intersection divided by the size of their union. It is a key metric for sparse, binary, or set-based data representations.

• Formula: J(A,B) = |A ∩ B| / |A ∪ B|
• Range: 0 to 1.
• Use Case: Document similarity with bag-of-words or shingling, duplicate detection, and genomic sequence analysis.
• Index Impact: Often used with MinHash approximations and Locality-Sensitive Hashing (LSH) families designed for set similarity, which are distinct from dense vector LSH.

Manhattan Distance (or L1 norm) sums the absolute differences between vector components. It is more robust to outliers than Euclidean distance and is used in domains where differences are additive.

• Formula: Σ|Aᵢ - Bᵢ|
• Use Case: Computer vision (e.g., histogram comparison), urban planning (grid-like movement), and certain high-dimensional statistical applications.
• Index Impact: Less common than L2 for mainstream vector indexes. Some tree-based indexes can be configured for L1 distance, but most graph-based and IVF methods are optimized for L2 or inner product.

Hamming Distance counts the number of positions at which the corresponding symbols are different between two strings or binary vectors of equal length. It is the standard metric for comparing binary codes.

• Formula: Number of positions where Aᵢ ≠ Bᵢ.
• Use Case: Comparing binary hashes (e.g., SimHash), error-correcting codes, and DNA sequence alignment.
• Index Impact: Central to bit-based LSH and indexing methods for binary embeddings. Efficient computation via XOR and popcount operations makes it extremely fast on modern CPUs.