In classical kD-trees, the splitting dimension is chosen using a simple and systematic rule: dimensions are taken in a round-robin fashion.

But extra freedom is available because you could very well choose the splitting dimension at will on every level, and even differently on every node.

Has this been investigated ? Can it yield some gain in performance ? How to efficiently determine an optimal splitting scheme among the exponentially numerous possibilities ?

  • $\begingroup$ Do you have a definition of "optimal"? I imagine it's probably NP-hard to find the optimal splitting, but I'm just speculating. $\endgroup$
    – D.W.
    Commented Sep 11, 2022 at 23:40
  • $\begingroup$ @D.W.: not a formal one. The idea is that there could be splitting schemes that make the nearest-neighbor searches faster. I am essentially asking if there are known results about this. $\endgroup$
    – user16034
    Commented Sep 12, 2022 at 6:49
  • $\begingroup$ Have you searched for papers on the topic? E.g. [this paper on adaptive indexes(scholar.google.com/…)? $\endgroup$
    – TilmannZ
    Commented Sep 12, 2022 at 9:29
  • $\begingroup$ @TilmannZ: you are right, I should have done that in the first place. I was unsure of the terminology, but it turns out that I used the proper terms. $\endgroup$
    – user16034
    Commented Sep 12, 2022 at 9:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.