k-Nearest Neighbors (k-NN)

k-NN refers to the exact solution, requiring a brute-force comparison of the query against every vector in the database (O(N) time). This guarantees perfect accuracy but is computationally prohibitive at scale. Approximate Nearest Neighbor (ANN) algorithms are the practical implementations that trade a small amount of accuracy for sub-linear query times (e.g., O(log N)), enabling real-time search over billion-scale datasets.

• Brute-Force (k-NN): Perfect recall, linear time.
• ANN (e.g., HNSW, IVF): High recall, sub-linear time.

The definition of "nearest" is governed by a distance metric. The choice of metric is dictated by how the vector embeddings were generated and what similarity means for the application.

Key metrics include:

• Euclidean Distance (L2): Measures straight-line distance. Common for general-purpose embeddings.
• Cosine Similarity: Measures the angle between vectors, ignoring magnitude. Standard for text embeddings from models like BERT or OpenAI embeddings.
• Inner Product (Dot Product): Used when vector magnitude carries information, common in recommendation systems. Often requires normalization to use with metrics designed for Euclidean space.

The 'k' in k-NN is a hyperparameter that controls the granularity of the result set. It represents the number of nearest neighbors to retrieve.

• A small k (e.g., 1, 5) provides a precise, focused set of results but can be noisy or unstable.
• A larger k (e.g., 100, 1000) provides a broader context, which is useful for tasks like majority voting in classification or generating diverse candidates for a recommendation system.
• In ANN systems, the query-time 'k' is often independent of the index structure's internal parameters (like an HNSW's ef or IVF's nprobe).

k-NN search becomes fundamentally challenging in high-dimensional spaces (e.g., 768, 1536 dimensions) due to the curse of dimensionality. As dimensions increase, the volume of space grows exponentially, causing all data points to become nearly equidistant. This renders naive distance metrics less discriminative and is the primary reason exact k-NN is impractical at scale.

ANN algorithms combat this by:

• Using dimensionality reduction (e.g., PCA).
• Leveraging index structures (graphs, trees) that exploit the intrinsic, lower-dimensional geometry of the data.

The gold-standard metric for evaluating an ANN system's accuracy is Recall@K. It measures how well the approximate search replicates the results of an exact k-NN search.

Recall@K = (Number of true top-K neighbors found) / K

• A Recall@10 of 0.99 means the ANN system found 99% of the 10 true nearest neighbors.
• This metric directly quantifies the trade-off with query latency. Engineering involves tuning index parameters to achieve the optimal recall-latency curve for a specific application.

Every ANN algorithm is an optimized, approximate solution to the k-NN problem. They use different strategies to avoid exhaustive search:

• Graph-Based (HNSW): Builds a multi-layer navigable graph for greedy, logarithmic-time traversal.
• Partition-Based (IVF): Uses clustering (k-means) to partition data, searching only in promising cells.
• Hashing-Based (LSH): Projects similar vectors into the same hash buckets with high probability.
• Quantization-Based (PQ): Compresses vectors to reduce memory and distance computation cost.

k-NN defines the objective; ANN provides the scalable, engineering solutions.

Euclidean distance is the most intuitive metric, representing the straight-line distance between two points in Euclidean space. It's calculated as the square root of the sum of squared differences between corresponding vector components: distance = sqrt(Σ(x_i - y_i)^2). This metric is ideal for data where magnitude matters, such as physical sensor readings or normalized embeddings where all dimensions are on the same scale. It assumes the feature space is isotropic (uniform in all directions).

Cosine similarity measures the cosine of the angle between two non-zero vectors, focusing on orientation rather than magnitude. It's calculated as the dot product of the vectors divided by the product of their magnitudes: similarity = (A·B) / (||A|| ||B||). Values range from -1 (opposite) to 1 (identical direction). This metric is dominant in text and image retrieval, where high-dimensional embeddings (e.g., from transformers) are often compared based on their semantic direction, not their length. For k-NN search, the cosine distance (1 - similarity) is typically used.

Manhattan distance (or City Block distance) sums the absolute differences between vector components: distance = Σ|x_i - y_i|. It represents the distance traveled between two points on a grid-like path. This metric is more robust to outliers than Euclidean distance because large differences in a single dimension contribute linearly, not quadratically. It's often used in high-dimensional spaces like histograms or when features have different units, as it doesn't amplify discrepancies in any one dimension.

The inner product (dot product) is the sum of the products of corresponding components: A·B = Σ(x_i * y_i). When used directly as a similarity score (higher is more similar), it solves the Maximum Inner Product Search (MIPS) problem. This is critical in recommendation systems where user and item embeddings are not normalized, and the goal is to find items that maximize predicted engagement. Note: A high dot product can result from large magnitudes, not just alignment, which is why specialized indices like ScaNN are often required for efficient MIPS.

The Jaccard index (or Jaccard similarity coefficient) measures the similarity between finite sample sets. It's defined as the size of the intersection divided by the size of the union: J(A,B) = |A ∩ B| / |A ∪ B|. The corresponding Jaccard distance is 1 - J(A,B). This metric is essential for k-NN on binary or set-based data, such as:

• Comparing documents represented as sets of shingles or n-grams.
• Analyzing user behavior based on sets of purchased items or visited pages.
• Measuring similarity in categorical data after one-hot encoding.

Hamming distance counts the number of positions at which the corresponding symbols or bits are different between two strings or binary vectors of equal length. For two binary vectors A and B, it's calculated as Σ (A_i XOR B_i). It is the primary metric for comparing:

• Binary embeddings generated by hashing techniques.
• Genetic codes in bioinformatics (for sequences of equal length).
• Error-detecting codes in information theory. It operates at the bit level, making it extremely fast to compute with bitwise operations, but it requires vectors to be of identical length.

A class of algorithms designed to find vectors similar to a query with high probability, trading perfect accuracy for significantly faster, sub-linear query times. ANN is the practical implementation of k-NN for billion-scale datasets where brute-force search is infeasible.

• Key Trade-off: Balances recall (accuracy) against search latency and memory footprint.
• Common Algorithms: Includes HNSW, IVF, and Locality-Sensitive Hashing (LSH).
• Use Case: Enables real-time semantic search in vector databases and recommendation systems.

The two primary distance metrics used to measure "closeness" between vectors in a k-NN search.

• Cosine Similarity: Measures the cosine of the angle between two vectors. Ideal for text embeddings where magnitude is less important than orientation. Range: -1 to 1.
• Euclidean Distance (L2): Measures the straight-line distance between two points in space. The most intuitive geometric distance. Range: 0 to infinity.

Choosing a Metric: Normalized vectors often use cosine similarity (equivalent to Euclidean on normalized vectors). Euclidean is standard for many computer vision embeddings.

A state-of-the-art, graph-based ANN algorithm that constructs a multi-layered graph for highly efficient search.

• Mechanism: Higher graph layers have long-range connections for fast, logarithmic-time navigation. Lower layers have short-range connections for high-accuracy refinement.
• Performance: Offers an excellent balance of high recall, low latency, and reasonable index build time.
• Limitation: Has a higher memory footprint than quantization-based methods. It is the default algorithm in many vector databases like Weaviate and Qdrant.

A two-stage clustering-based index that partitions the dataset to restrict search scope.

• Mechanism: Uses a coarse quantizer (like k-means) to divide vectors into Voronoi cells (clusters). For a query, it searches only the most promising cell(s).
• Advantage: Very fast index build time and lower memory use than graph-based methods.
• Trade-off: Requires careful tuning of the nprobe parameter (number of cells to search) to balance speed and recall. Often combined with Product Quantization (PQ) for further compression in the IVFADC index.

The core evaluation framework for measuring ANN search quality and understanding system performance limits.

• Recall@K: The fraction of the true top-K nearest neighbors (found by exact search) returned by the ANN system. A recall of 1.0 is perfect accuracy.
• Recall-Precision Trade-off: In system design, this refers to the inverse relationship between recall and operational precision (i.e., query speed/latency). Increasing search depth improves recall but increases latency. This trade-off is managed via algorithm parameters (e.g., HNSW's ef, IVF's nprobe).

A lossy compression technique that dramatically reduces the memory footprint of vector indexes.

• Mechanism: Splits a high-dimensional vector into subvectors and quantizes each subspace into a small set of centroids (stored in codebooks). A vector is represented by a short code of centroid indices.
• Benefit: Can compress vectors to just a few percent of their original size, enabling billion-scale indexes to fit in RAM.
• Search: Uses Asymmetric Distance Computation (ADC) to approximate the distance between a raw query and compressed database vectors. It's often used as a second-stage compressor within an IVF index (IVFADC).