How to choose the cutting dimension properly in building a kd-tree?

Question

recently I am digging into the kd-tree, and have found some interesting thing on choosing the cutting dimension. Through some tech blogs, there are two approaches:

1. If the point dimension is denoted as k, in 0-th depth we choose dimension 1, and 1-th depth we choose dimension 2, and until (k - 1)-th depth we choose dimension k. And then again in k-th depth we choose dimension 1, etc. E.g. in two-dimension space, denoted as (x, y), the cutting dimension will be chosen as x, y, x, y, ...
2. Another way is to calculate the variance of all values in each dimension and the largest one will be chosen as the cutting dimension.

So, I wonder which approach is better to build a kd-tree. Or if they both have their situations, in what situation which one should we use?

Thanks in advance!

Answer 1

I would suggest 2. is better alternative than 1. if you need good balance in the kd tree as more the variance more are the chances that a points are distributed to either side of the cutting dimension. The more balanced the kd tree is the lesser no of comparisons are needed to find the query point. The balance is desired more at the higher levels of tree than lower levels as query time of more points are effected at higher levels hence the highest variance is considered first.

Answer 2

If you just cycle through the dimensions, you can save the storage space for keeping track of which dimension you used. An node-less k-d-tree can perform very well because of memory efficiency, as it has 0 memory overhead.