distance concentration concept
| Definition | The narrowing of the spread of pairwise distances as dimension grows, read in the book as the reader running out of resolution. Chapter 3. Also runs out of resolution. |
|---|---|
| Example | In 500 dimensions the nearest and the farthest of 1000 random points differ in distance by a few percent. |
| Book | Data Mining as Observation, draft 0.2, commit f3914f0; entry id distance-concentration, kind concept. |
| Status | no ledger row names this entry. Corrections: none recorded. |
| Defining equation | none |
| Assumptions and scope |
|
| Prior art | none recorded |
| Evidence | lean/DataMiningAsObservation/DistanceConcentration.lean |
| Reviewed | not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page. |
Equation
none
Conditions
- When a squared distance is a sum of independent coordinate contributions with a common mean and variance, its relative spread is the variance over the dimension times the squared mean, which falls with the dimension and tends to zero. The independence is the model’s assumption.
- The book reads the narrowing as a property of the reader, the identity reader on all coordinates, and not of the data. A consumer that reads a low-dimensional subspace does not see it, which is why the effective rank and not the ambient dimension is the number that matters.
Conditions are curated in entries.toml rather than read
from a record.
Ledger
none
First stated
The classical result on nearest neighbours in high dimension, as TSK chapter 2 presents it, and chapter 3 section 3.4 of Data Mining as Observation, where it is read as the reader running out of resolution.
Measurements
none
Failures and corrections
none
Invariance envelope
none declared
Machine checked
lean/DataMiningAsObservation/DistanceConcentration.lean,
theorems relSpread_eq, relSpread_antitone,
relSpread_tendsto_zero,
exists_dim_relSpread_lt, at observation-data-mining
f3914f0; what the check covers is stated in the book’s appendix
C.
Used in
Data Mining as Observation chapters 3.
Related
hubness; effective rank; read subspace; rank certificate.
See also
Book equations stated beside the entry’s terms, not defining it: 0.7.
Ledger rows that cite the entry’s records without naming it: NEG-11.
Sources-table rows that share a record with the entry without naming it: chapter 3 section 3.5, chapter 4 section 4.2.
Status
Generated 2026-09-10 by encyclopedia/generate.py; book
at observation-data-mining f3914f0; the commit of every record is listed
in the encyclopedia’s provenance.