In low-dimensional space, distance is intuitive. If you are standing in a room, some objects are clearly "near" and others are "far." This contrast allows algorithms like $k$-means to find clusters by grouping points around a central representative. However, as we move into the high-dimensional latent spaces of modern machine learning—where vectors may have hundreds or thousands of features—this intuition collapses.
This phenomenon is often called the concentration of measure. As dimensionality increases, the distribution of distances between random points narrows significantly. In a high-dimensional hypersphere, almost all the volume is concentrated in a thin shell near the surface. Consequently, the distance between any two points becomes nearly identical. When every point is roughly the same distance from every other point, the very concept of a "cluster" based on spatial proximity begins to vanish.
The Vanishing Contrast
The core problem for high-dimensional clustering is the loss of contrast between the nearest and farthest neighbors. Alexander Hinneburg and Daniel A. Keim noted in their work on OptiGrid that traditional distance-based methods fail because the difference between the maximum and minimum distance to a point effectively drops to zero relative to the distance itself.
This isn't just a theoretical nuisance; it creates "hallucinated" structures. Nicholas P. Hughes and David Lowe demonstrated that certain dimensionality reduction techniques, like Multidimensional Scaling (MDS) using squared distances, will force structureless high-dimensional data into artificial ring-shaped distributions. The algorithm tries so hard to preserve the nearly uniform distances of the high-dimensional space that it creates a hollow shell in low dimensions just to make the math work.
Why Global Centroids Fail
Most classic clustering algorithms, such as $k$-means, rely on global centroids. They assume that a single point (the mean) can represent a cluster. But in high dimensions, the "center" of a cluster is a lonely place. Polina Turishcheva and colleagues, through their MNIST-Nd benchmark, showed that centroid-based methods experience a sharp performance decay as dimensions scale.
The reason is that the Euclidean distance to a global mean becomes less informative than the local relationships between points. When you have 1,000 dimensions, a point might be "close" to a cluster in 950 dimensions but wildly different in the other 50. In a global distance calculation, the cumulative noise from those 50 dimensions can completely mask the signal from the 950. Vincent Gripon and his team addressed this by segmenting high-dimensional vectors into smaller subvectors, performing independent searches, and using a majority vote to find the true neighbors.
Finding Clusters in Subspaces
If global distances are unreliable, the solution is to look for clusters where they actually live: in lower-dimensional subspaces. Charu C. Aggarwal and Philip S. Yu pioneered this with ORCLUS, which identifies clusters hidden in arbitrarily oriented subspaces. Instead of looking at all features at once, these methods find the specific hyperplanes where data points actually condense.
Similarly, Alexander Hinneburg proposed cutting through low-density regions using optimal grids. By identifying where the data isn't, algorithms can partition the space more effectively than by trying to find where the data is using distance alone.
Graph-Based Robustness
One of the most robust ways to "break" the curse of dimensionality is to move from distance-based geometry to graph-based topology. In a graph, we only care about who your closest neighbors are, not exactly how far away they are. Polina Turishcheva found that graph-based methods like Leiden clustering maintain high accuracy even as dimensions increase, because they focus on local connectivity rather than global spatial density.
This shift is also seen in modern deep learning. Xifeng Guo 0001 developed IDEC, which uses an autoencoder to learn a lower-dimensional representation specifically designed to preserve local structure while clustering. By jointly optimizing for reconstruction and clustering, the model ensures the "meaning" of the data isn't lost in the high-dimensional noise.
Geometry in Deep Latent Spaces
In deep learning, we often normalize embeddings to a unit sphere to combat these effects. Sigurd Løkse and Michael Kampffmeyer introduced SEN, which uses "soft" normalization to encourage embeddings to lie on a hypersphere. This constrains the geometry and helps maintain discriminative power.
However, even on a sphere, the concentration of measure persists. R. Manmatha pointed out that most points on a high-dimensional sphere are naturally equidistant, which makes training with triplet or contrastive losses difficult. If you sample points randomly, they will almost all be at the same distance, providing no useful gradient for the model to learn from. This necessitates "distance-weighted sampling" to find the rare pairs that actually provide a signal.
Ultimately, the research direction suggests that to work effectively in high dimensions, we must stop treating space as a uniform container. Whether through subspace projection, graph-based neighborhoods, or learned metrics, the goal is to find the local "pockets" of meaning that global distance metrics are too blunt to see.