4 ms·

Nice algorithm. I am curious what happens when the dimension becomes really large (more than 100). I have heard about kd tree but as far as I know the performan

Nice algorithm. I am curious what happens when the dimension becomes really large (more than 100). I have heard about kd tree but as far as I know the performance becomes really bad for d > 16. What should be the strategy of finding nearest neighbours for such high dimensions?

snovv_crash 9y ago
It often depends on what the actual dimensionality of the problem is. If it can be embedded in a lower dimensional space, as many problems are, then a well tuned kD-Tree can still do a good job up to about 16 dimensions of used space, as you say. Cover trees also work well in this case, and are better at extracting just the salient dimensions than kD-Trees are, especially as the discrepancy between the subspace and data space grows. 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.
MrQuincle 9y ago
Euclidean? Then nearest neighbor itself is rarely what you want: https://link.springer.com/chapter/10.1007%2F3-540-49257-7_15 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. :-)
argonaut 9y ago
For large dimensions, a normal linear search.

snovv_crash 9y ago

It often depends on what the actual dimensionality of the problem is. If it can be embedded in a lower dimensional space, as many problems are, then a well tuned kD-Tree can still do a good job up to about 16 dimensions of used space, as you say. Cover trees also work well in this case, and are better at extracting just the salient dimensions than kD-Trees are, especially as the discrepancy between the subspace and data space grows. 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.

MrQuincle 9y ago

Euclidean? Then nearest neighbor itself is rarely what you want: https://link.springer.com/chapter/10.1007%2F3-540-49257-7_15 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. :-)

argonaut 9y ago

For large dimensions, a normal linear search.