The Biggest Challenge With Distance Functions

Exact nearest neighbor search is just computationally infeasible. Approximation itself has challenges in high dimensions. Some distant metrics may not have good approximation guarantees for a generic metric. But usually the problems are even even earlier than that.