# Curse of Dimensionality

> Source: https://aiwiki.ai/wiki/curse_of_dimensionality
> Updated: 2026-06-23
> Categories: Machine Learning, Mathematics, Statistics
> From AI Wiki (https://aiwiki.ai), a free encyclopedia of artificial intelligence. Quote with attribution.

*See also: [Machine learning](/wiki/machine_learning), [Feature engineering](/wiki/feature_engineering), [Dimensionality reduction](/wiki/dimensionality_reduction)*

The **curse of dimensionality** is the set of problems that arise when data has a large number of features (dimensions): as dimensions increase, the volume of the space grows exponentially, the available data becomes extremely sparse, and the geometric and statistical intuitions that hold in two or three dimensions break down. The phrase was coined by the American mathematician [Richard Bellman](/wiki/richard_bellman), who introduced the concept in his 1957 book *Dynamic Programming* and popularized the exact term in his 1961 book *Adaptive Control Processes: A Guided Tour*.[1][2] Its single most consequential effect is **distance concentration**: as dimensionality grows, the distance to the nearest data point approaches the distance to the farthest one, so the notion of a "nearest neighbor" loses meaning, an effect that empirical studies have observed with as few as 10 to 15 dimensions.[6]

The curse affects nearly every area of data analysis and [machine learning](/wiki/machine_learning). Algorithms that work well in two or three dimensions often fail in hundreds or thousands of dimensions because the geometric and statistical properties of high-dimensional spaces differ dramatically from our low-dimensional intuitions. Understanding the curse of dimensionality is essential for practitioners who work with high-dimensional datasets, and it motivates many of the techniques used in modern machine learning, including [feature selection](/wiki/feature_selection), [dimensionality reduction](/wiki/dimensionality_reduction), and [regularization](/wiki/regularization).

## Introduction

The curse of dimensionality refers to a collection of phenomena that arise when analyzing and organizing data in high-dimensional spaces. As the number of dimensions (features, variables, or attributes) increases, the volume of the space grows so rapidly that the available data becomes sparse. This sparsity makes it difficult for statistical and machine learning methods to find patterns, estimate densities, or measure distances reliably. The term was coined by the American mathematician Richard Bellman while studying optimization problems in [dynamic programming](/wiki/dynamic_programming).

The curse affects nearly every area of data analysis and machine learning. Algorithms that work well in two or three dimensions often fail in hundreds or thousands of dimensions because the geometric and statistical properties of high-dimensional spaces differ dramatically from our low-dimensional intuitions. Understanding the curse of dimensionality is essential for practitioners who work with high-dimensional datasets, and it motivates many of the techniques used in modern machine learning, including feature selection, dimensionality reduction, and regularization.

## Who coined the term and when?

### Bellman and dynamic programming

Richard Bellman introduced the concept of the curse of dimensionality in his 1957 book *Dynamic Programming*, where he laid out the mathematical framework for multi-stage decision processes and identified the explosion of the state space as the central obstacle to applying that framework to real-world problems.[1] He stated the famous phrasing a few years later, in his 1961 book *Adaptive Control Processes: A Guided Tour*. On page 97, he wrote: "In view of all that we have said in the foregoing sections, the many obstacles we appear to have surmounted, what casts the pall over our victory celebration? It is the curse of dimensionality, a malediction that has plagued the scientist from the earliest days."[2]

Bellman's concern was computational. In [dynamic programming](/wiki/dynamic_programming), solving an optimization problem requires evaluating a value function over a discretized state space. If the state has d dimensions and each dimension is discretized into m levels, the total number of grid points is m^d. Even a modest discretization (m = 100) in d = 10 dimensions yields 100^10 = 10^20 grid points, a number far beyond the capacity of any computer. The exponential growth of the state space with dimensionality made many practically important control problems intractable, and Bellman recognized this as a fundamental obstacle rather than a temporary limitation of computing hardware.

The 1957 *Dynamic Programming* book was where Bellman laid out the framework; the curse of dimensionality was the central obstacle he identified for applying that framework to real-world problems with many state variables. This is why most references credit the 1957 work with introducing the idea, while the memorable "malediction" phrasing dates to the 1961 book.[1][2]

### From combinatorics to geometry

Between 1957 and 1977, the curse of dimensionality was understood primarily in Bellman's original combinatorial sense: exponential growth in the number of states or grid points. In 1977, Jerome Friedman, Jon Bentley, and Raphael Finkel published work on nearest-neighbor algorithms that helped introduce a geometric perspective.[5] In high-dimensional spaces, the distances between data points behave in counterintuitive ways that undermine distance-based methods. This geometric view broadened the concept beyond optimization and into statistics and pattern recognition.

### The Hughes effect

In 1968, Gordon F. Hughes published a paper demonstrating what is now called the Hughes phenomenon (or Hughes effect).[3] Hughes studied the relationship between the number of features used by a classifier and its classification accuracy, given a fixed training set size. He showed that accuracy initially improves as more features are added, but beyond a certain point, adding features causes accuracy to decline. This happens because, with a fixed amount of training data, additional features increase the dimensionality of the space faster than the data can fill it. The classifier begins to overfit to noise in the sparse high-dimensional space rather than learning genuine patterns.

The peak in the accuracy curve, where performance begins to degrade, is sometimes called the "peaking phenomenon." The location of this peak depends on the ratio of training samples to features. The Hughes effect provided one of the earliest empirical demonstrations that more features do not always lead to better models.

## Why does high-dimensional space behave so strangely?

### Volume of a hypercube

A unit hypercube in d dimensions has side length 1 along each axis. Its volume is always 1, regardless of dimension. However, the way points fill that volume changes dramatically. To place sample points at intervals of 0.01 along each axis requires:

| Dimensions (d) | Points needed (spacing = 0.01) |
|---|---|
| 1 | 100 |
| 2 | 10,000 |
| 3 | 1,000,000 |
| 10 | 10^20 |
| 100 | 10^200 |

The number of points grows as 100^d. In 10 dimensions, uniformly sampling the unit hypercube at this resolution would require more points than there are atoms in Earth's oceans. In 100 dimensions, the number exceeds any physically meaningful quantity. This exponential scaling is the most direct expression of the curse.

### Volume of a hypersphere

The volume of a d-dimensional hypersphere with radius r is given by:

V_d(r) = (pi^(d/2) / Gamma(d/2 + 1)) * r^d

where Gamma is the gamma function. For integer dimensions, this produces familiar results: V_1 = 2r (a line segment), V_2 = pi * r^2 (a circle), V_3 = (4/3) * pi * r^3 (a sphere).

A surprising property is that the volume of a unit hypersphere (r = 1) initially increases with dimension, reaches its maximum at exactly d = 5, and then decreases monotonically toward zero as d grows.[16] The ratio of the hypersphere's volume to the enclosing hypercube's volume (2^d, since the hypercube has side length 2r = 2) shrinks rapidly:

| Dimension | Volume of unit hypersphere | Fraction of enclosing hypercube |
|---|---|---|
| 1 | 2.000 | 100% |
| 2 | 3.142 | 78.5% |
| 3 | 4.189 | 52.4% |
| 5 | 5.264 | 16.4% |
| 10 | 2.550 | 0.249% |
| 20 | 0.0258 | 0.00000246% |
| 50 | ~5.28 x 10^-23 | negligible |

This means that in high dimensions, a sphere inscribed in a cube occupies a vanishingly small fraction of the cube's volume. Most of the space in a high-dimensional cube is concentrated in the corners, far from the center. Algorithms that rely on spherical neighborhoods (such as [k-nearest neighbors](/wiki/k-nearest_neighbors)) are affected by this, because a sphere large enough to contain a reasonable number of neighbors may extend well beyond the local region of interest.

### Concentration of volume near the surface

In high dimensions, almost all the volume of a hypersphere is concentrated in a thin shell near its surface. The fraction of the volume of a unit sphere contained in an outer shell of thickness epsilon is:

fraction_shell = 1 - (1 - epsilon)^d

For epsilon = 0.05 (a shell that is 5% of the radius):

| Dimension | Fraction of volume in outer 5% shell |
|---|---|
| 2 | 9.8% |
| 3 | 14.3% |
| 5 | 22.6% |
| 10 | 40.1% |
| 50 | 92.3% |
| 100 | 99.4% |
| 500 | ~100% |

In 100 dimensions, over 99% of the sphere's volume lies within the outermost 5% of its radius. This means that random points drawn uniformly from a high-dimensional sphere are almost all located near the surface. The interior of the sphere is essentially empty. This concentration effect has direct consequences for density estimation: in high dimensions, uniform distributions are effectively concentrated on thin shells rather than spread throughout the volume.

## Distance concentration

One of the most consequential effects of high dimensionality is the concentration of distances. As the number of dimensions grows, the ratio of the maximum pairwise distance to the minimum pairwise distance converges to 1 for many common distributions. Formally, for n random points in d dimensions drawn from a broad class of distributions:

lim (d -> infinity) [max distance / min distance] -> 1

This was studied rigorously by Beyer, Goldstein, Ramakrishnan, and Shaft (1999) and by Aggarwal, Hinneburg, and Keim (2001).[6][7] The practical consequence is that in very high dimensions, all points tend to be approximately equidistant from one another. The concept of a "nearest neighbor" becomes nearly meaningless because the nearest point is barely closer than the farthest point. Beyer and colleagues framed the central question directly in the title of their paper, "When Is 'Nearest Neighbor' Meaningful?", and showed empirically that distances begin to lose contrast at remarkably low dimensionality, with the effect visible in datasets of as few as 10 to 15 dimensions.[6]

To illustrate: consider 500 random points uniformly distributed in a d-dimensional unit hypercube. In d = 2 dimensions, the distance from a query point to its nearest neighbor is typically about 0.04 (very close). In d = 10 dimensions, the median nearest-neighbor distance grows to approximately 0.52, which is more than halfway to the boundary. In d = 100 dimensions, nearest-neighbor distances cluster around values that are nearly indistinguishable from the average pairwise distance.

This distance concentration undermines any algorithm that relies on meaningful distance comparisons, including nearest-neighbor classifiers, distance-based clustering methods such as [k-means](/wiki/k-means_clustering), and kernel methods that depend on distance-based similarity measures.

## Why does the curse of dimensionality break machine learning?

### k-nearest neighbors

The [k-nearest neighbors](/wiki/k-nearest_neighbors) (k-NN) algorithm classifies a test point by finding the k closest training points and assigning the majority label. The algorithm rests on the assumption that nearby points have similar labels. Cover and Hart (1967) proved that as the training set size n approaches infinity, the error rate of the 1-NN classifier is at most twice the Bayes optimal error rate.[4]

However, this asymptotic guarantee requires enough data to ensure that the nearest neighbor is actually close. In d dimensions, with n training points uniformly distributed in the unit hypercube, the edge length of the smallest hypercube containing k neighbors scales as:

l = (k / n)^(1/d)

For k = 10 and n = 1000:

| Dimensions (d) | Edge length l |
|---|---|
| 2 | 0.10 |
| 10 | 0.63 |
| 100 | 0.955 |
| 1000 | 0.995 |

In 100 dimensions, finding just 10 nearest neighbors requires searching 95.5% of the range of each feature. The "nearest" neighbors are effectively spread across almost the entire space, making the assumption that they share the test point's label unreliable. To maintain a fixed neighborhood size relative to the data range, the required number of training samples grows exponentially with dimension.

### Clustering

Clustering algorithms such as [k-means](/wiki/k-means_clustering), DBSCAN, and hierarchical clustering rely on distance or density to group similar points. In high dimensions, distance concentration makes it harder to distinguish between points that belong to the same cluster and points that belong to different clusters. All pairwise distances become similar, so cluster boundaries become ambiguous.

DBSCAN, which identifies clusters as regions of high density separated by regions of low density, is particularly affected. Its key parameter, epsilon (the neighborhood radius), becomes difficult to set because the distinction between local densities blurs as dimensionality increases.

### Density estimation

Non-parametric density estimation methods, such as kernel density estimation and histograms, attempt to estimate the probability density function of data. In d dimensions, a histogram with m bins per dimension requires m^d bins total. For m = 10 and d = 20, this yields 10^20 bins. With any realistic dataset, almost all bins will be empty, making the density estimate useless.

Kernel density estimation faces a similar problem. The bandwidth (smoothing parameter) must be large enough to include sufficient data points in each kernel neighborhood, but in high dimensions this means the kernel becomes so wide that it loses the ability to resolve local structure.

The rate at which density estimates converge to the true density slows dramatically with dimension. For a kernel density estimator with optimal bandwidth, the mean integrated squared error decreases as O(n^(-4/(d+4))). In d = 1 dimension this gives a rate of O(n^(-4/5)), which is near-parametric. In d = 20 dimensions the rate drops to O(n^(-4/24)) = O(n^(-1/6)), requiring enormously more data for the same accuracy.

### Sample complexity

The curse of dimensionality directly affects how many training samples are needed to learn a function reliably. For a function of d variables, the number of samples needed to achieve a given approximation accuracy typically grows exponentially with d. A common rule of thumb, though not universally applicable, suggests that at least 5 to 10 training examples per dimension are needed for reliable results.

More formally, for a Lipschitz-continuous function on the unit hypercube, achieving a uniform approximation error of epsilon requires O((1/epsilon)^d) sample points. This exponential dependence on d is a direct manifestation of the curse.

The following table illustrates the sample requirements for different dimensionalities, assuming a modest density of 10 samples per unit interval along each axis:

| Dimensions | Samples needed (10 per axis) |
|---|---|
| 2 | 100 |
| 5 | 100,000 |
| 10 | 10^10 |
| 20 | 10^20 |
| 50 | 10^50 |

### Support vector machines and kernel methods

[Support vector machines](/wiki/support_vector_machine_svm) (SVMs) and other kernel methods map data into high-dimensional (sometimes infinite-dimensional) feature spaces using kernel functions. While the kernel trick avoids explicitly computing in the high-dimensional space, the statistical challenges of the curse still apply. The [Gaussian (RBF) kernel](/wiki/radial_basis_function_kernel), which computes similarity as exp(-gamma * ||x - z||^2), is sensitive to the choice of gamma. In high dimensions, all pairwise distances ||x - z||^2 tend to concentrate around the same value, making the kernel matrix nearly uniform and reducing the SVM's ability to discriminate between classes.

## The Hughes effect in detail

The Hughes effect can be understood as follows. Consider a classification problem with a fixed training set of n samples. As features are added:

1. Initially, each new feature provides additional discriminative information, and classification accuracy improves.
2. At some point, the number of parameters the classifier must estimate (which grows with the number of features) exceeds what the training data can support.
3. The classifier begins to overfit: it models noise and sampling artifacts rather than the true underlying distribution.
4. Accuracy declines even though, in principle, the additional features carry useful information.

The peak of the accuracy curve shifts to the right (toward more features) as the training set size increases. With infinite training data, more features always help. The Hughes effect is therefore a finite-sample phenomenon, not a property of the features themselves.

Hughes's original analysis focused on the Gaussian maximum-likelihood classifier, but the peaking phenomenon has been observed across many different classifier types, including [naive Bayes](/wiki/naive_bayes), [decision trees](/wiki/decision_tree), and [neural networks](/wiki/neural_network).[3]

## How do you mitigate the curse of dimensionality?

### Dimensionality reduction

[Dimensionality reduction](/wiki/dimensionality_reduction) techniques project high-dimensional data into a lower-dimensional space while attempting to preserve important structure. Two broad categories exist:

**Linear methods:**

| Method | Key idea | Preserves |
|---|---|---|
| [PCA](/wiki/principal_component_analysis) (Principal Component Analysis) | Projects onto directions of maximum variance | Global variance structure |
| LDA (Linear Discriminant Analysis) | Projects onto directions that maximize class separation | Between-class vs. within-class scatter |
| Random projection | Projects using random matrices (Johnson-Lindenstrauss lemma) | Pairwise distances (approximately) |

**Nonlinear methods:**

| Method | Key idea | Preserves |
|---|---|---|
| [t-SNE](/wiki/t-sne) | Matches pairwise probability distributions in low and high dimensions | Local neighborhood structure |
| [UMAP](/wiki/umap) | Constructs fuzzy topological representations and optimizes layout | Local and some global structure |
| Isomap | Computes geodesic distances on a neighborhood graph | Geodesic distances |
| [Autoencoders](/wiki/autoencoder) | Learns a compressed representation through a neural network bottleneck | Reconstruction accuracy |

[PCA](/wiki/principal_component_analysis) is the most widely used linear method. It finds orthogonal directions (principal components) along which the data has the greatest variance and projects the data onto the top k components. PCA is computationally efficient, well understood, and effective when the data lies near a linear subspace. However, it cannot capture nonlinear relationships.

[t-SNE](/wiki/t-sne) (van der Maaten and Hinton, 2008) is popular for visualization in 2 or 3 dimensions.[11] It excels at revealing cluster structure but is computationally expensive (O(n^2) in its naive implementation) and does not preserve global distances.

[UMAP](/wiki/umap) (McInnes, Healy, and Melville, 2018) is faster and more scalable than t-SNE while preserving both local and some global structure.[14] It has become the default choice for visualizing high-dimensional data in many fields, including single-cell genomics and [natural language processing](/wiki/natural_language_processing).

### Feature selection

[Feature selection](/wiki/feature_selection) addresses the curse by removing irrelevant or redundant features rather than transforming them. The goal is to find a subset of the original features that retains most of the predictive information while reducing dimensionality. Feature selection methods fall into three categories:

| Category | Description | Examples |
|---|---|---|
| Filter methods | Evaluate features independently of the learning algorithm using statistical tests | Correlation, mutual information, chi-squared test, variance threshold |
| Wrapper methods | Evaluate feature subsets by training a model and measuring performance | Forward selection, backward elimination, recursive feature elimination |
| Embedded methods | Perform feature selection as part of the model training process | [LASSO](/wiki/lasso_regression) (L1 regularization), decision tree feature importance, [random forest](/wiki/random_forest) importance |

Filter methods are computationally cheap but may miss feature interactions. Wrapper methods capture interactions but are expensive, especially with many features. Embedded methods offer a balance, using the structure of the learning algorithm to identify important features during training.

### Regularization

[Regularization](/wiki/regularization) techniques constrain the complexity of a model, reducing its tendency to overfit in high-dimensional settings. Common approaches include:

- **L1 regularization (LASSO):** Adds a penalty proportional to the sum of absolute values of the model's coefficients. This encourages sparsity, effectively performing feature selection by driving some coefficients to zero.
- **L2 regularization (Ridge):** Adds a penalty proportional to the sum of squared coefficients. This shrinks all coefficients toward zero without eliminating them, reducing variance at the cost of a small increase in bias.
- **Elastic net:** Combines L1 and L2 penalties, offering both sparsity and grouping of correlated features.
- **[Dropout](/wiki/dropout):** In [neural networks](/wiki/neural_network), randomly sets a fraction of activations to zero during training, preventing co-adaptation of neurons.

### Distance metric learning

Since the curse of dimensionality degrades the usefulness of standard distance metrics like Euclidean distance, one approach is to learn a task-specific distance metric. Metric learning algorithms, such as Large Margin Nearest Neighbor (LMNN) and Mahalanobis distance learning, optimize a distance function so that points of the same class are pulled closer together while points of different classes are pushed apart. This can partially restore the meaningfulness of nearest-neighbor queries in high-dimensional spaces.

## What is the manifold hypothesis?

The [manifold hypothesis](/wiki/manifold_hypothesis) proposes that real-world high-dimensional data (images, text, audio, sensor readings) typically does not fill the entire ambient space uniformly. Instead, the data lies on or near a low-dimensional manifold embedded within the high-dimensional space. For example, images of human faces might exist in a space with millions of pixel dimensions, but the actual variation in faces can be described by a much smaller number of factors: pose, lighting, expression, identity, and so on. Estimates suggest that natural images of faces vary along roughly 50 independent dimensions, even though each image may contain millions of pixels.

If the manifold hypothesis holds, then the effective (intrinsic) dimensionality of the data is much lower than the ambient dimensionality, and the curse is less severe than it appears. Empirical studies that estimate the intrinsic dimension of commonly used image datasets have repeatedly found it to be far lower than the ambient pixel dimension, which is the central reason the hypothesis is taken seriously.[17] Algorithms that can discover and exploit this low-dimensional structure can avoid the exponential data requirements implied by the full ambient dimension.

[Deep learning](/wiki/deep_learning) models are often credited with implicitly exploiting the manifold hypothesis. In their 2016 textbook *Deep Learning*, Ian Goodfellow, Yoshua Bengio, and [Aaron Courville](/wiki/aaron_courville) argued that the manifold hypothesis is at least approximately correct for natural data such as images, and that this low-dimensional structure is what allows the curse of dimensionality to be sidestepped for most real datasets.[13] Successive layers of a deep network learn increasingly abstract representations that progressively "unfold" the data manifold into a space where the task (classification, generation, and so on) becomes easier.

Manifold learning algorithms such as Isomap (Tenenbaum, de Silva, and Langford, 2000), Locally Linear Embedding (Roweis and Saul, 2000), and [UMAP](/wiki/umap) explicitly attempt to discover the low-dimensional manifold structure in data.[9][10][14]

## What is the blessing of dimensionality?

While the curse of dimensionality highlights the difficulties of high-dimensional spaces, researchers have also identified situations where high dimensionality is beneficial. David Donoho, in his 2000 lecture "High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality" at the American Mathematical Society, coined the complementary term "blessing of dimensionality" and described several scenarios where adding dimensions helps rather than hurts.[8]

The key mechanism is the **concentration of measure** phenomenon. In high-dimensional spaces, many quantities (distances, projections, volumes) concentrate tightly around their expected values. While this concentration is harmful when it makes distances indistinguishable, it can be helpful in other contexts:

- **Linear separability:** Random points in high dimensions become increasingly easy to separate by hyperplanes. A result from the theory of random polytopes shows that n points in d dimensions (with d large relative to n) can be linearly separated with high probability, even if they are drawn from a single distribution. This partly explains why linear classifiers can work surprisingly well in high-dimensional spaces.
- **Random projection:** The Johnson-Lindenstrauss lemma (1984) states that n points in high-dimensional space can be projected into O(log n / epsilon^2) dimensions while preserving all pairwise distances within a factor of (1 +/- epsilon).[12] Crucially, the required target dimension depends only logarithmically on the number of points and not at all on the original ambient dimension, so meaningful low-dimensional representations often exist and random projection provides a computationally cheap way to find them.
- **Compressed sensing:** Donoho (2006) and Candes, Romberg, and Tao (2006) showed that sparse high-dimensional signals can be exactly recovered from a small number of random linear measurements, far fewer than the ambient dimension would suggest. This exploits the fact that the signal is sparse (has low intrinsic complexity) even though it lives in a high-dimensional space.

The distinction between curse and blessing often comes down to signal versus noise. When additional dimensions carry discriminative information, they help. When they carry noise, they hurt. The challenge is to identify which dimensions (or combinations of dimensions) are informative.

## Practical guidelines

The following recommendations can help practitioners manage the curse of dimensionality in applied machine learning projects:

1. **Monitor the ratio of samples to features.** As a rough guideline, aim for at least 5 to 10 samples per feature. If this ratio is small, consider reducing dimensionality before training.
2. **Visualize in low dimensions.** Use [PCA](/wiki/principal_component_analysis), [t-SNE](/wiki/t-sne), or [UMAP](/wiki/umap) to project data into 2D or 3D. This can reveal whether meaningful structure exists and how features relate to targets.
3. **Apply feature selection.** Remove features that have low variance, high correlation with other features, or low mutual information with the target variable.
4. **Prefer models with built-in regularization.** [Random forests](/wiki/random_forest), [gradient boosting](/wiki/gradient_boosting), and regularized linear models (LASSO, Ridge) handle high-dimensional data better than unregularized methods.
5. **Be cautious with distance-based methods.** k-NN, k-means, and DBSCAN may not work well in high dimensions without prior dimensionality reduction or careful metric selection.
6. **Use domain knowledge.** Expert knowledge about which features are likely informative can guide feature selection more effectively than purely data-driven methods, especially when data is scarce.
7. **Consider the intrinsic dimensionality.** Techniques such as the correlation dimension, PCA scree plots, and intrinsic dimensionality estimators can help assess how many effective dimensions the data occupies, even if the ambient dimension is high.
8. **Scale data consistently.** In high dimensions, features with different scales can dominate distance computations. Standardize or normalize features before applying distance-based algorithms.

## Explain like I'm 5 (ELI5)

Imagine you are looking for your friend in a hallway (1 dimension). You just walk forward or backward, and you will find them quickly. Now imagine looking for your friend in a giant football field (2 dimensions). It takes longer because there is more ground to cover. Now imagine looking for your friend in a huge building with many floors, rooms, and hallways (3 dimensions). It takes even longer.

The curse of dimensionality says that every time you add a new "direction" to search in, the space you have to search grows enormously. By the time you have 100 different directions, the space is so unbelievably large that you could search forever without finding anything, even if your friend is technically "nearby." To handle this, you need either an enormous number of searchers (data points) or a clever way to figure out which directions actually matter and ignore the rest.

## References

1. Bellman, R. (1957). *Dynamic Programming*. Princeton University Press.
2. Bellman, R. (1961). *Adaptive Control Processes: A Guided Tour*. Princeton University Press.
3. Hughes, G. F. (1968). "On the mean accuracy of statistical pattern classifiers." *IEEE Transactions on Information Theory*, 14(1), 55-63.
4. Cover, T. and Hart, P. (1967). "Nearest neighbor pattern classification." *IEEE Transactions on Information Theory*, 13(1), 21-27.
5. Friedman, J. H., Bentley, J. L., and Finkel, R. A. (1977). "An algorithm for finding best matches in logarithmic expected time." *ACM Transactions on Mathematical Software*, 3(3), 209-226.
6. Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. (1999). "When is 'nearest neighbor' meaningful?" *Proceedings of the 7th International Conference on Database Theory (ICDT)*, 217-235.
7. Aggarwal, C. C., Hinneburg, A., and Keim, D. A. (2001). "On the surprising behavior of distance metrics in high dimensional space." *Proceedings of the 8th International Conference on Database Theory (ICDT)*, 420-434.
8. Donoho, D. L. (2000). "High-dimensional data analysis: The curses and blessings of dimensionality." Lecture at the AMS Conference on Math Challenges of the 21st Century, Los Angeles.
9. Tenenbaum, J. B., de Silva, V., and Langford, J. C. (2000). "A global geometric framework for nonlinear dimensionality reduction." *Science*, 290(5500), 2319-2323.
10. Roweis, S. T. and Saul, L. K. (2000). "Nonlinear dimensionality reduction by locally linear embedding." *Science*, 290(5500), 2323-2326.
11. van der Maaten, L. and Hinton, G. (2008). "Visualizing data using t-SNE." *Journal of Machine Learning Research*, 9, 2579-2605.
12. Johnson, W. B. and Lindenstrauss, J. (1984). "Extensions of Lipschitz mappings into a Hilbert space." *Contemporary Mathematics*, 26, 189-206.
13. Goodfellow, I., Bengio, Y., and Courville, A. (2016). *Deep Learning*. MIT Press.
14. McInnes, L., Healy, J., and Melville, J. (2018). "UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction." *arXiv preprint arXiv:1802.03426*.
15. Verleysen, M. and Francois, D. (2005). "The curse of dimensionality in data mining and time series prediction." *Proceedings of the 8th International Work-Conference on Artificial Neural Networks (IWANN)*, 758-770.
16. Smith, D. J. and Vamanamurthy, M. K. (1989). "How small is a unit ball?" *Mathematics Magazine*, 62(2), 101-107. (On the volume of the unit n-ball peaking at dimension 5.)
17. Pope, P., Zhu, C., Abdelkader, A., Goldblum, M., and Goldstein, T. (2021). "The Intrinsic Dimension of Images and Its Impact on Learning." *International Conference on Learning Representations (ICLR)*.