High Dimensional Data & The Curse of Dimensionality
High Dimensional Data & The Curse of Dimensionality¶

Computer Science Dept, Ferdowsi University of Mashhad
Introduction¶
In modern data mining and machine learning, we often deal with data in very high-dimensional spaces (e.g., images, text embeddings, genomic data). A dataset is typically represented as an matrix .
Understanding the nature of high-dimensional space, or hyperspace, is very important because it does not behave like the more familiar geometry in two or three dimensions. This phenomenon is often referred to as the Curse of Dimensionality.
Key phenomena we will explore:
Volume Concentration: The volume of a hypersphere vanishes relative to the hypercube.
The Problem of Local Neighborhoods: Why “local” methods like k-NN fail (based on Elements of Statistical Learning).
The Thin Shell: Most of the volume concentrates near the surface (measured on the sampling page).
Orthogonality: Random vectors in high dimensions are nearly orthogonal.
Gaussian Behavior: Points concentrate in a thin ring around radius — also measured on the sampling page.
Geometry of Hyperspace: Cubes and Spheres¶
Let’s define the two most basic shapes in -dimensions.
The Hypercube¶
The data space is often viewed as a -dimensional hyper-rectangle or hypercube. For a hypercube with side length , the volume is:
The Hypersphere¶
We write for the solid ball and for its surface. The distinction matters: the volume below is a property of the ball, and its boundary is a single layer of measure zero. The volume of the -dimensional ball of radius is:
Where is the Gamma function.
Figure 6.4. Hypersphere inscribed inside a hypercube: in (a) two and (b) three dimensions
The Empty Center (The “Porcupine” Effect)¶
Consider the space enclosed within the largest hypersphere that can be accommodated within a hypercube of side length . The ratio of their volumes is:
Implication: As dimensionality increases, the volume of the hypersphere becomes negligible compared to the hypercube. Most of the volume of the hypercube is in the corners, whereas the center is essentially empty.

Conceptual view of high-dimensional space: (a) two, (b) three, (c) four, and (d) higher dimensions. In d dimensions there are “corners” and diagonals. The radius of the inscribed circle accurately reflects the difference between the volume of the hypercube and the inscribed hypersphere in dimensions.
Source
import math
import matplotlib.pyplot as plt
import numpy as np
def hypersphere_volume(d, R):
"""Volume of the solid ball of radius R in d dimensions."""
return (math.pi ** (d / 2)) * (R ** d) / math.gamma(d / 2 + 1)
dimensions = list(range(1, 30))
volumes = [hypersphere_volume(d,1) for d in dimensions]
plt.figure(figsize=(10, 6))
plt.plot(dimensions, volumes, marker='o', linestyle='-', color='b', label='volume of the unit ball')
plt.xlabel('dimension d')
plt.ylabel('Volume')
plt.title("Volume of a unit hypersphere in various dimensions")
plt.legend()
plt.grid(True)
plt.show()
The Problem of Local Neighborhoods (k-NN)¶
One of the most significant manifestations of the curse of dimensionality affects “local” methods like k-Nearest Neighbors (k-NN).
Edge Length of Neighborhoods¶
Suppose we have inputs uniformly distributed in a -dimensional unit hypercube. We want to form a local neighborhood that captures a fraction of the observations. Since this corresponds to a fraction of the unit volume, the expected edge length of this neighborhood is:

FIGURE 2.6. The curse of dimensionality is well illustrated by a subcubical neighborhood for uniform data in a unit cube. The figure on the right shows the side-length of the subcube needed to capture a fraction r of the volume of the data, for different dimensions p. In ten dimensions we need to cover 80% of the range of each coordinate to capture 10% of the data
Let’s visualize this for different dimensions () and fractions ().
Source
import numpy as np
import matplotlib.pyplot as plt
def edge_length(fraction_volume, p):
return fraction_volume ** (1/p)
fractions = np.linspace(0.001, 1.0, 100)
dims_esl = [1, 2, 3, 10]
plt.figure(figsize=(8, 6))
for p in dims_esl:
plt.plot(fractions, edge_length(fractions, p), label=f'p={p}')
# Highlighting the case for p=10, r=0.1
plt.plot(0.1, 0.1**(1/10), 'ro')
plt.xlabel('Fraction of Volume ($r$)')
plt.ylabel('Edge Length of Subcube: $e_p(r)$')
plt.title('Edge Length required to capture fraction of Volume')
plt.legend()
plt.grid(True)
plt.show()
Analysis: In 10 dimensions (), to capture just 10% () of the data, we need to cover 80% of the range of each input variable. Such neighborhoods are no longer “local”. To find neighbors, we must look very far away.
Distance to Boundary¶
Another consequence is that sampling density is sparse. For data points in a -dimensional unit ball, the median distance from the origin to the closest data point is:
For and , this distance is , which is more than halfway to the boundary. Hence, most data points are closer to the boundary of the sample space than to any other data point. This makes prediction a problem of extrapolation rather than interpolation.
Orthogonality: Random Directions Are Nearly Perpendicular¶
Another counter-intuitive property: in high dimension every direction is nearly orthogonal to every other direction. Two vectors drawn at random are almost always almost perpendicular.
The diagonal of the cube versus an axis¶
Consider the diagonal vector in a hypercube . The angle between this diagonal and any coordinate axis is:
As , , which means . The diagonal is effectively orthogonal to the axes!
Furthermore, random vectors in high dimensions are nearly orthogonal to each other.
Source
dim = 200
# Generate random vectors
x = np.random.randn(4, dim)
# Normalize
x_norm = x / np.linalg.norm(x, axis=1)[:, np.newaxis]
print(f"Dot products of random pairs in {dim}-D:")
for i in range(len(x_norm)):
for j in range(i+1, len(x_norm)):
dp = np.dot(x_norm[i], x_norm[j])
print(f"Vector {i} . Vector {j} = {dp:.4f}")Dot products of random pairs in 200-D:
Vector 0 . Vector 1 = -0.0227
Vector 0 . Vector 2 = 0.0015
Vector 0 . Vector 3 = 0.0229
Vector 1 . Vector 2 = -0.0327
Vector 1 . Vector 3 = 0.0843
Vector 2 . Vector 3 = 0.0176
Summary¶
High-dimensional space is empty in the center.
Volume is in the corners or a thin shell at the surface.
Neighbors are far away (breaking local methods like k-NN).
Random vectors are orthogonal.
The computations behind these statements — the shell volume, rejection sampling, uniform points on the sphere and inside the ball, and the Gaussian annulus — are on Sampling in High Dimensional Spaces.
References¶
Zaki & Meira (2020), Chapter 6 (high-dimensional space).
Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of Data Science. Cambridge University Press.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning.
Exercises¶
Compute the ratio of the volume of the unit ball to the volume of the cube for . At which dimension does the ball hold less than of the cube?
For two random unit vectors in , show that and plot the histogram of for and . What does the concentration mean for the words nearest and farthest?
Compute the fraction of the ball’s volume in the shell as a function of , and explain the consequence for sampling points uniformly in a high-dimensional ball.
Using the notebook’s neighbourhood argument, show that the edge length of a cube holding a fixed fraction of the points grows like , and evaluate it for and .
- Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367