If the dimensionality gets larger then a better approach is to instead remove overhead and improve parallelism, for example by pushing the problem to the GPU or discretizing the measurement space down to 8-bits or even 1-bit per dimension. I know of products that do both, and solve O(N^2) problems 20x larger than a naïve approach could in the same time. POPCNT runs really fast on GPUs.
Then nearest neighbor itself is rarely what you want: https://link.springer.com/chapter/10.1007%2F3-540-49257-7_15. Quote from abstract:
"We show that under a broad set of conditions (much broader than independent and identically distributed dimensions), as dimensionality increases, the distance to the nearest data point approaches the distance to the farthest data point"
In the end - in the physical world - everything maps to 3D give or take a few dimensions that are very small if we have to believe some physicists. You just have to find the mapping. :-)