What is the “Curse of Dimensionality”?

What goes wrong in high dimensions

In low dimensions (2D, 3D), we’re used to the idea that “near” and “far” are clear: you can partition space with a grid or tree and quickly rule out regions that are far from the query. In hundreds or thousands of dimensions, volume grows so fast that almost all of the space is “in the corners”—points are sparse and distances tend to concentrate around a similar value. So the “nearest” neighbor is often not much closer than a random point, and simple spatial partitioning (like the kind B-trees rely on) doesn’t shrink the search set much. Exact search can degenerate to scanning everything, which doesn’t scale.

Mathematically, in high dimensions the ratio of the distance to the nearest neighbor and the distance to the average point tends to approach 1; that is, “nearest” and “average” become hard to distinguish. This distance concentration is one reason brute-force k-NN in high dimensions is both slow and not much more informative than random sampling unless we use smarter indexing.

Why partitioning fails

In 2D you can split the plane with a line and keep only one half; in 3D you can use a plane. In d dimensions, to reduce the set by half you need a (d−1)-dimensional hyperplane, and the number of cells grows exponentially with d. So grids and simple trees either have too many cells (memory explosion) or cells that still contain too many points (no pruning). That’s the curse: naive space splitting doesn’t scale with dimension.

Tree-based indexes (e.g. k-d trees) that work well in low dimensions become ineffective: the number of boundaries needed to isolate small regions explodes, and query paths often visit most of the tree. That’s why vector databases avoid relying on axis-aligned or tree-style partitioning alone and instead use graph or clustering structures that adapt to the actual distribution of the data.

How ANN indexes cope

That’s why vector DBs use approximate methods: HNSW, IVF, and other indexes exploit structure (e.g. graph neighborhoods or clusters) rather than naive space splitting. They don’t try to partition the whole space; they build a graph or cluster assignment so that “near” in the data sense corresponds to “reachable in few steps” or “in the same bucket.” They trade a bit of recall for practical latency. So the curse of dimensionality isn’t just theory—it’s the reason we need dedicated vector database architecture and can’t rely on simple indexes designed for low-dimensional or one-dimensional data.

ANN algorithms don’t eliminate the curse; they work around it by accepting approximate answers and by using data-dependent structures (neighborhoods, clusters) that reflect how your vectors are actually distributed, rather than assuming a uniform or axis-aligned layout.

Practical implications

When choosing embedding dimensionality, higher d often means better expressiveness but worse curse: more dimensions can hurt recall vs. latency for a given index. Quantization and dimensionality reduction can help in some settings. See also the recall–latency trade-off curve and how HNSW handles high-dimensional data.