Why does high-dimensional geometry break traditional search structures?

High-dimensional geometry breaks traditional search structures because several assumptions that hold comfortably in two or three dimensions — that points can be meaningfully closer or farther apart, that splitting space into regions actually isolates nearby points, that most of a space’s volume sits somewhere in the middle of it — stop being true as the number of dimensions grows, and every one of the structures built on those assumptions degrades along with them.

What actually happens to distances as dimensionality increases?

Picture picking many random points inside a space and measuring the distance from one fixed query point to every other point. In two or three dimensions, those distances vary a lot — some points land close by, others land far away, and that spread is exactly what lets a search algorithm tell “near” from “far.” As the number of dimensions grows, though, the distances to a random query start clustering more and more tightly around a single typical value, so the gap between the nearest point and the farthest point shrinks relative to that value. Taken to an extreme, in very high dimensions almost every point ends up looking roughly equally distant from the query, and a ranking that’s supposed to separate close matches from irrelevant ones has less and less real signal to work with. This effect is usually called distance concentration, and it’s the mathematical core of what people mean when they talk about the curse of dimensionality.

Why does volume behave so strangely in high-dimensional space?

A closely related effect shows up when thinking about volume instead of distance. In three dimensions, most of the volume of a solid ball sits reasonably close to its center. In high dimensions, that stops being true: the volume of a high-dimensional ball concentrates overwhelmingly in a thin shell near its outer surface, with almost nothing left near the center. A similar thing happens with cubes — most of a high-dimensional cube’s volume sits near its corners rather than spread evenly through the middle. Both effects come from the same underlying cause as distance concentration: with many independent dimensions each contributing a little bit of spread, the combined effect pushes typical points toward the extremes rather than the center, in ways that have no equivalent in the two- or three-dimensional spaces human intuition is built around.

Why does this break branch-and-bound pruning in structures like k-d trees?

Tree-based exact search methods rely on being able to rule out entire regions of space without checking every point inside them — a k-d tree, for example, compares a query only against the boundary of a region, and if that boundary is already farther away than the best candidate found so far, the whole region can be skipped. That shortcut depends on there being a meaningful difference between “close” boundaries and “far” boundaries in the first place. Once distance concentration sets in, most region boundaries end up looking similarly distant from the query, so the pruning test almost never succeeds, and the search ends up visiting nearly every region anyway. At that point the tree has all the bookkeeping overhead of maintaining a hierarchical structure with none of the benefit, and a plain linear scan across the same data can end up faster simply because it skips that overhead entirely.

Does every high-dimensional dataset suffer from this equally?

Not necessarily, and this distinction matters a great deal in practice. The number of dimensions a vector is stored in — its ambient dimension — is not always the same as its intrinsic dimensionality, which describes how many degrees of freedom the data actually varies along once its real structure is accounted for. A dataset of 1,536-dimensional embeddings might still lie close to some much lower-dimensional surface within that space, if the process that generated the embeddings only really varies along a limited number of independent factors. Data like this can behave noticeably better than the worst-case picture painted above, which is part of why approximate methods tuned on real embeddings sometimes perform far better than the raw dimension count would suggest, and why intrinsic dimensionality — rather than ambient dimensionality alone — is often the more useful number to reason about when predicting how hard a given search problem will actually be.

The next page pulls together the specific algorithmic and systems ideas — priority queues, visited sets, skip lists, and the rest — that every practical answer to this problem, including HNSW, ends up relying on. If the volume and distance effects described here feel counterintuitive, the curse-of-dimensionality and intrinsic-dimensionality glossary pages work through the same ideas with more room to build up the underlying math from first principles.