When Is 'Nearest Neighbor' Meaningful?¶
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999). When Is 'Nearest Neighbor' Meaningful?. Proceedings of the 7th International Conference on Database Theory (ICDT '99).
Cited by¶
4 citations across 4 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Curse Of Dimensionality
- The ratio between the nearest and farthest distances among random points approaches one, so "nearest neighbour" loses meaning.
This sourceProves that under broad conditions the ratio of farthest to nearest distance approaches one as dimension grows, so nearest-neighbour loses meaning.
Borderline supportVerified against the publisher's abstract
The abstract states that as dimensionality increases the distance to the nearest point approaches the distance to the farthest, supporting the ratio-to-one and nearest-neighbour claim.
“as dimensionality increases, the distance to the nearest data point approaches the distance to the farthest data point”
Two runs of the same check disagreed on this citation; the later verdict is shown and the citation is queued for review.
- The ratio between the nearest and farthest distances among random points approaches one, so "nearest neighbour" loses meaning.
Mechanisms¶
- Distance-Choice Sensitivity Analysis
- It is especially valuable in high dimensions, where distances tend to concentrate and many formulas produce near-identical, near-meaningless separations
This sourceShows that in high dimensions the distance to the nearest point can approach the distance to the farthest point, making nearest-neighbor distinctions uninformative.
- It is especially valuable in high dimensions, where distances tend to concentrate and many formulas produce near-identical, near-meaningless separations
- Nearest-Neighbor Audit
- Its failure modes: it rests on the reviewer's or oracle's notion of "related," which is subjective and can itself be wrong; sampling can miss bad neighborhoods in regions it never draws from; and in very high-dimensional spaces neighbors are inherently less meaningful, so some noise is unavoidable.
This sourceShows that in high-dimensional spaces the distance to a nearest data point can approach the distance to the farthest point, making nearest-neighbor distinctions unstable or meaningless.
- Its failure modes: it rests on the reviewer's or oracle's notion of "related," which is subjective and can itself be wrong; sampling can miss bad neighborhoods in regions it never draws from; and in very high-dimensional spaces neighbors are inherently less meaningful, so some noise is unavoidable.
- Nearest-Neighbor or Exemplar Classifier
- In high-dimensional feature spaces the curse of dimensionality sets in and "nearest" loses meaning, because almost everything becomes roughly equidistant.
This sourceShows that, under broad high-dimensional conditions, nearest and farthest distances converge and nearest-neighbor distinctions lose meaning.
- In high-dimensional feature spaces the curse of dimensionality sets in and "nearest" loses meaning, because almost everything becomes roughly equidistant.
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 4 citations: 1 borderline. 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:7c868be7c1b9 · see in the full table