Why may a KD-tree fail to beat brute-force nearest-neighbor search in high dimension?
Classic MLLevel: IntermediateTree-index degradation
Why may a KD-tree fail to beat brute-force nearest-neighbor search in high dimension?
Hints
- An index helps only if it prunes much of the search.
- Dimensionality changes geometric concentration.
Answer
Axis-aligned partitions become less effective at pruning candidate regions, so traversal approaches exhaustive work plus index overhead. Benchmark realistic dimensions and query batches.
Source and licence: scikit-learn 1.7.2 — neighbors · BSD-3-Clause · answer: Quantoros editorial