0
$\begingroup$

Let's say for example we have 1000 points and 50 dimensions.

And we build a quadtree where each node represents a 50-dimensional box and is divided by splitting the box into smaller boxes that are half the size in every dimension? How would i calculate how many children each internal node has?

Improve this question
$\endgroup$
1
  • $\begingroup$ If you are interested in high-dimensional quadtree-type indexes, have a look at my PH-Tree. It is a somewhat optimized quadtree that works well with 50 dimensions, it was comparable to R-Tree performance for up to 1000 dimensions. Especially for highly clustered data (I tested with 40 dimensions) it seems to have much faster k-nearest-neighbor queries than kd-trees. The original paper (see link above) also discusses the number of subnodes in a quadtree. $\endgroup$
    – TilmannZ
    Commented Jul 4, 2021 at 17:32

1 Answer 1

Reset to default
2
$\begingroup$

If you split along each dimension into two parts, then in two dimensions you have $2\cdot 2 = 4$ children (that's why it's called a quadtree), in three dimensions you have $2\cdot 2\cdot 2 = 8$ children (that's why three-dimensional quadtrees are called octtrees), and for $k$ dimensions you have $2^k$ children.

That's independent of the numbers of points in your tree - each internal node in a quadtree splits in the same way.

And for higher dimensions that's a lot of children, and therefore you don't want to use a quadtree in that case, but something else, for example a k-d tree.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Quadtrees can actually work quite well with 50+ dimensions if child nodes are only created when they are actually required. At least with the datasets that I tested, such a tree (called PH-Tree <-- self advertisement) they worked either as good (normal data) or a lot better )clustered data) than kd-trees, see here. $\endgroup$
    – TilmannZ
    Commented Jul 4, 2021 at 17:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.