This issue also gets mentioned in the sklearn documentation [0]. The "curse of dimensionality" explains how high dimensional data tends to be close together, making efficient indexing on a distance metric difficult.

I feel like the poster-child for the frequency illusion. There was an article on 538 a few weeks ago that caught my interest which used cosine similarity (a non-metric distance function). I dove in, and started wondering if there were any ways to find nearest neighbors using cosine similarity efficiently. A week later, Facebook's Faiss implements something of a general purpose toolkit for indexing metric and not metric spaces to minimize storage. And now this. It's like the world is trying to tell me something!

[0] http://scikit-learn.org/stable/modules/neighbors.html#k-d-tr...