On the Surprising Behavior of Distance Metrics in High Dimensional Space.¶
Aggarwal, C. C., Hinneburg, A., & 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 '01).
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Curse Of Dimensionality
- The qualitative-threshold property is visible: at \(d = 2\) or $3$ nearest-neighbour search works fluently, by \(d = 20\) it has degraded, and by \(d = 1000\) raw-distance retrieval is meaningless — a regime change, not a gradual decline.
This sourceDemonstrates the qualitative breakdown of distance discrimination as dimension rises across norms.
Supported in partVerified against the publisher's abstract
The abstract supports only that proximity/nearest-neighbour may cease to be qualitatively meaningful at high dimension; it states no threshold dimensions and no regime-change claim.
“Recent research results show that in high dimensional space, the concept of proximity, distance or nearest neighbor may not even be qualitatively meaningful.”
- The qualitative-threshold property is visible: at \(d = 2\) or $3$ nearest-neighbour search works fluently, by \(d = 20\) it has degraded, and by \(d = 1000\) raw-distance retrieval is meaningless — a regime change, not a gradual decline.
Mechanisms¶
- Distance Metric Audit
- Its central failure mode is diagnosing the symptom (distances concentrate, neighbors are unstable) without recognizing the cause, which is usually many weak or mis-scaled features rather than the metric formula.
This sourceShows that high-dimensional distance concentration can make nearest-neighbor proximity poorly discriminating and unstable.
- Its central failure mode is diagnosing the symptom (distances concentrate, neighbors are unstable) without recognizing the cause, which is usually many weak or mis-scaled features rather than the metric formula.
- K-Nearest-Neighbor Case Matcher
- Its failure mode is the curse of dimensionality — as features multiply, everything becomes roughly equidistant, "nearest" loses meaning, and the neighborhood stops being local at all.
This sourceDocuments as features multiply, everything becomes roughly equidistant; "nearest" loses meaning; the neighborhood stops being local at all.
- Its failure mode is the curse of dimensionality — as features multiply, everything becomes roughly equidistant, "nearest" loses meaning, and the neighborhood stops being local at all.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 1 of 3 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:80c4003135b5 · see in the full table