High dimensional nearest neighbor search scales very poorly with dimensions and/or number of examples IIRC, so approximate methods are best for time/value trade

High dimensional nearest neighbor search scales very poorly with dimensions and/or number of examples IIRC, so approximate methods are best for time/value tradeoffs. Oftentimes the applications don't require a perfect match anyways, just something 'close enough'. Because things live in high dimensions, and they're often related to each other, this results in these vast 'sparse' gaps where no data really generally lives. Hence allowing for good speed of approximate methods, and a good tradeoff of information-per-FLOP when compared to the full scale search itself.