K Nearest Neighbor using K-D Tree (What ratio makes K-D beneficial)?

Question

I'm trying to implement a KNearestNeighbor model and came across the fact that many professional models use a K-D tree to index the K Nearest Neigbors. I also read that high-dimensional data makes a K-D tree less useful because you don't eliminate as many vectors for every branch in the tree when traversing it. All of that makes sense, but my question is at what ratio is there any benefit made of using a K-D tree?

For instance, I have a training set of shape (50000, 3072) but I am feeding only 10000 points to the model so the shape the model gets is (10000, 3072)... anyways, I assume these are the only two numbers which are relevant for the model to determine if a K-D would benefit it's runtime.

So in my fit method, I am making an if statement to either make a K-D model or not to make a K-D model for indexing, but I'm not sure what the condition should be. Given

n_data, n_dim = x.shape

I imagine the condition could be

if n_data / n_dim >= 1:
    pass

This is where my knowledge stops. I would be grateful if someone could propose a condition, and educate me about what makes a good condition.

Answer 1

There's no way to tell for sure without trying out. That said, a crude rule of thumb is that k-d trees tend to be useful when the number of dimensions is up to about 10-20, but in higher dimensions, often they are little better than a naive linear search over all points.

See also Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?, How can I make k nearest neighbor queries fast on unit hypersphere?, https://en.wikipedia.org/wiki/K-d_tree#Degradation_in_performance_with_high-dimensional_data