curse of dimensionality

The curse of dimensionality is the family of problems that appear when each data point carries a large number of dimensions, or features, where the space grows too fast for any realistic sample of points to fill it. The volume of a vector space rises exponentially with each added dimension, so the points end up scattered thinly across a mostly empty space.

Richard Bellman coined the phrase in his 1957 book Dynamic Programming, and the arithmetic behind it is blunt. Covering a unit line segment at a spacing of 0.01 takes 100 sample points, while covering a ten-dimensional unit cube at that same spacing takes 100 to the tenth power, or 10^20 points. Data that looks dense in two or three dimensions is almost entirely empty space once the count reaches the hundreds.

A second consequence falls on similarity search. Beyer and colleagues showed in 1999 that across a broad class of data distributions the distance to the nearest point and the distance to the farthest point converge as dimensions grow. That leaves nearest neighbor queries unable to tell close matches from distant ones. Later work narrowed the result to dimensions that vary independently, since correlated features retain some contrast.

The widget below runs that experiment on 300 random points in a unit cube. Drag the dimension count up, or press Sweep, and watch the band between the nearest and the farthest point collapse while the ratio between them falls toward 1.

Embeddings carry hundreds or thousands of dimensions, which is one reason a vector database relies on approximate nearest neighbor indexes instead of exact tree search. Scikit-learn makes the same retreat, switching its neighbor estimators to brute force above roughly 15 features. Embedding search still works because real text has a much lower intrinsic dimensionality, the number of directions it varies along, than its coordinate count suggests.

Adding features to a fixed training set lifts a model’s accuracy up to a point and then degrades it, an effect named the Hughes phenomenon. The usual answers are feature selection, dimensionality reduction with methods such as principal component analysis, and collecting more data.

Related Resources

Tutorial

The k-Nearest Neighbors (kNN) Algorithm in Python

In this tutorial, you'll learn all about the k-Nearest Neighbors (kNN) algorithm in Python, including how to implement kNN from scratch, kNN hyperparameter tuning, and improving kNN performance using bagging.

intermediate algorithms data-science machine-learning

For additional information on related topics, take a look at the following resources:

• ChromaDB: Embeddings and Vector Databases in Python (Tutorial)
• K-Means Clustering in Python: A Practical Guide (Tutorial)
• Using k-Nearest Neighbors (kNN) in Python (Course)
• Vector Databases and Embeddings With ChromaDB (Course)
• Split Your Dataset With scikit-learn's train_test_split() (Tutorial)
• Embeddings and Vector Databases With ChromaDB (Quiz)
• K-Means Clustering in Python: A Practical Guide (Quiz)
• Splitting Datasets With scikit-learn and train_test_split() (Course)
• Split Your Dataset With scikit-learn's train_test_split() (Quiz)