Curse of Dimensionality

As dimensionality increases, the relative contrast between the distance to the nearest neighbor and the farthest neighbor converges to zero. All points become almost equidistant from every other point.

• In 2D, the ratio of nearest to farthest neighbor distance is typically small.
• In 100D, this ratio approaches 1.0, making similarity search meaningless.
• This phenomenon invalidates the core assumption of distance-based indexing.

The volume of the space increases exponentially with each added dimension, requiring data to fill it. To maintain a constant sampling density, the number of data points must grow exponentially.

• A unit hypercube in 10D has a volume of 1, but its corners are very far from the center.
• Most of the volume of a high-dimensional sphere is concentrated in a thin shell near its surface.
• Data sparsity becomes the default state, not the exception.

In high-dimensional spaces, certain points emerge as 'hubs'—they appear as the nearest neighbor to a disproportionately large number of query points. This skews similarity graphs and degrades the performance of k-NN classifiers.

• Hubs are often points close to the data distribution's center of mass.
• They reduce the effective diversity of retrieved neighbors.
• Graph-based ANN indices like HNSW must account for this skew to avoid routing congestion.

For vectors generated by many random processes, the Euclidean norm concentrates around a single value as dimensionality grows. Vectors sampled from a Gaussian distribution lie almost exactly on the surface of a hypersphere.

• This makes cosine similarity and Euclidean distance nearly monotonic transformations of each other.
• The variance of the norm shrinks relative to its mean.
• Magnitude-based metrics like Maximum Inner Product Search (MIPS) become more sensitive to this effect.

The curse makes exact nearest neighbor search computationally infeasible. Brute-force search requires O(Nd) distance computations, which becomes prohibitive for large N and high d.

• No known exact algorithm consistently beats linear scan in high dimensions.
• This intractability is the direct motivation for Approximate Nearest Neighbor (ANN) algorithms.
• Techniques like dimensionality reduction and vector compression are mandatory pre-processing steps.

Space-partitioning data structures like k-d trees fail catastrophically in high dimensions. The number of nodes visited during a query explodes, often requiring traversal of nearly the entire tree.

• The efficiency of Voronoi cell partitioning degrades.
• Inverted File Index (IVF) structures must use a coarse quantizer to group sparse regions.
• Effective indexing requires abandoning strict geometric partitioning for graph-based or hashing approaches.

A graph-based ANN algorithm that constructs a multi-layered proximity graph to achieve logarithmic scaling search complexity. It directly combats the distance concentration effect by using long-range edges in sparse upper layers for rapid coarse navigation.

• Structure: Sparse upper layers for long jumps; dense lower layers for refinement
• Hyperparameter: Graph degree (M) controls memory vs. connectivity tradeoff
• Advantage: No training phase required; incrementally insertable

A hashing-based ANN technique that partitions high-dimensional space using random projection functions. It counters sparsity by ensuring similar vectors collide in the same hash bucket with high probability.

• Hash function design: Maximizes collision probability for near neighbors
• Tradeoff: Requires many hash tables for high recall, increasing memory footprint
• Best for: Datasets where cosine similarity or Jaccard distance is the primary metric

A vector compression technique that decomposes high-dimensional vectors into smaller subvectors, quantizing each independently using a distinct codebook. This dramatically reduces memory footprint, allowing billion-scale indices to fit in RAM.

• Mechanism: Splits a 128-dim vector into 8 subvectors of 16 dimensions each
• Key metric: Quantization error represents the distortion introduced by compression
• Distance computation: Uses Asymmetric Distance Computation (ADC) for higher accuracy

A preprocessing step that projects high-dimensional vectors into a lower-dimensional space before indexing. Techniques like PCA or random projection mitigate the curse of dimensionality by discarding noise dimensions where distance metrics lose discriminative power.

• PCA: Identifies principal components with maximum variance
• Random Projection: Uses the Johnson-Lindenstrauss lemma to preserve pairwise distances
• Benefit: Reduces index build time and memory while improving ANN recall

The choice of distance metric critically impacts behavior in high-dimensional spaces. Cosine similarity measures angular distance (orientation), ignoring magnitude differences that become less meaningful as dimensionality grows. Euclidean distance (L2) is sensitive to both direction and magnitude, making it more susceptible to the curse.

• Cosine range: -1 (opposite) to 1 (identical)
• Euclidean: Straight-line distance; values grow unbounded with dimensionality
• MIPS: Maximum Inner Product Search prioritizes dot product for models where magnitude matters