I think you are referring to what's known as the "curse of dimensionality," where as dimensionality increases, the distance between points tends to become more uniform and large. However, nearest neighbor search can still work effectively because of several key factors:
1. Real data rarely occupies the full high-dimensional space uniformly. Instead, it typically lies on or near a lower-dimensional manifold embedded within the high-dimensional space. This is often called the "manifold hypothesis."
2. While distances may be large in absolute terms, _relative_ distances still maintain meaningful relationships. If point A is closer to point B than to point C in this high-dimensional space, that proximity often still indicates semantic similarity.
3. The data points that matter for a given problem often cluster in meaningful ways. Even in high dimensions, these clusters can maintain separation that makes nearest neighbor search useful.
Let me give a concrete example: Consider a dataset of images. While an image might be represented in a very high-dimensional space (e.g., thousands of pixels), images of dogs will tend to be closer to other dog images than to images of cars, even in this high-dimensional space. The meaningful features create a structure that nearest neighbor search can exploit.
Spam filtering is another area where nearest neighbor is used to good effect. When you know that a certain embedding representing a spam message (in any medium - email, comments, whatever), then if other messages come along and are _relatively_ close to that one, you may conclude that they are on the right side of the manifold to be considered spam.
You could train a special model to define this manifold, but spam changes all the time and constant training doesn’t work well.