R2.4 · LESSON 4 OF 6

High dimensions

Implement an exact baseline, compute recall at k and explain approximate search and high-dimensional difficulty.

THE IDEA

Why high dimensions are hard

Space grows explosively with dimension. A sub-box covering 0.1 of each axis holds 0.01 of the unit box in 2 dimensions but only 10⁻¹⁰ in 10. In high dimension random points are nearly all about the same distance apart (distance concentration), so ideas like "skip the far regions" prune less. Real data is usually structured and lower-dimensional than its raw size, so the effect varies, but noise dimensions only make it worse.

dimension2

a box covering 0.1 of every axis holds 1.00e-2 of the unit box's volume 300 random points: nearest distance 0.017, farthest 0.972 relative contrast (far − near) / near = 57.56

As the dimension grows, regions shrink to almost nothing and distances to different points become nearly equal, which weakens simple pruning. How strongly this bites depends on the geometry of real data, which is often lower-dimensional than its raw size. Adding noisy dimensions makes search harder, not easier.

Increase the dimension and watch the contrast between nearest and farthest fall.

Predict first. Does merely adding empty or noisy dimensions guarantee easier search?

Chapter context

An exact search compares every candidate under a defined metric. Approximate indexes reduce work by choosing promising candidates, accepting that some true nearest neighbors may be missed.

TRY IT YOURSELF

Part 1. Do it hands-on

Compute how fast sub-box volume shrinks, then measure distance concentration and noise effects in code.

dimension2

a box covering 0.1 of every axis holds 1.00e-2 of the unit box's volume 300 random points: nearest distance 0.017, farthest 0.972 relative contrast (far − near) / near = 57.56

volume fraction in 2 dimensions in 10 dimensions do 1000 noise dimensions make search easier? (yes/no)

To do: A sub-box covering 0.1 of each axis of the unit box. In 2 dimensions it covers what fraction of the box's volume?
To do: In 10 dimensions? (type like 1e-10)
To do: Adding 1000 extra dimensions of pure noise to every vector makes the real neighbours easier to find. Type yes or no

Part 2. Do it in code

box_fraction(d, side=0.1): the volume fraction of a sub-box with the given side length on each of d axes of the unit box: side ** d.
relative_contrast(X, q): (farthest distance − nearest distance) / nearest distance from the query to the rows of X. A small value means everything is almost equally far away.
contrast_by_dimension(dims, n, seed): for each dimension d in dims draw n uniform random points and one random query with np.random.default_rng(seed) and return the list of relative contrasts.
noisy_extension(X, extra, seed): append `extra` columns of standard-normal noise to every row (np.random.default_rng(seed)).
nn_changes(X, Xn, q, qn): True if the nearest neighbour of q in X differs from the nearest neighbour of qn in Xn (the same points with noise added).

import numpy as np

def box_fraction(d, side=0.1):
    pass

def relative_contrast(X, q):
    pass

def contrast_by_dimension(dims, n, seed):
    pass

def noisy_extension(X, extra, seed):
    pass

def nn_changes(X, Xn, q, qn):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does merely adding empty or noisy dimensions guarantee easier search?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

An exact dense dot-product scan over N vectors of dimension d needs Nd coordinate products plus reductions.

\operatorname{recall@k}=\frac{|R_k\cap G_k|}{k}.

This assumes k ground-truth eligible neighbors. In a d-dimensional unit box, a sub-box spanning fraction r of every axis occupies fraction $r^d$ of the volume.

Worked example

Scanning 1000 vectors of dimension 128 uses 128,000 coordinate products, before selection and other overhead. If the true three neighbors are {A,B,C} and the returned set is {A,C,E}, recall@3 is 2/3. A sub-box spanning 0.1 of each of ten axes occupies only 10^-10 of the unit-box volume.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
assert 1000*128 == 128000
truth,returned={'A','B','C'},{'A','C','E'}
assert isclose(len(truth & returned)/3,2/3)
assert isclose(.1**10,1e-10)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Index recall is not the same as judged semantic relevance. High-dimensional behavior depends on the data manifold. Tie policies can affect reported recall for identical distances.