Question

What do you call a search tree with a split factor of 2^k, where k is the dimensionality of the data points stored within the tree? (The data points are vectors x_1, ... x_k)

For k=1 we would get a normal binary search tree. For k=2 we would split into 4 quadrants in every node in the tree, etc.

What would be the proper name for such a tree for arbitrary k?

Was it helpful?

Solution

There are many data structures like this and I don't know if there's a specific name for it. For example, the quadtree and octree structures have these branching factors for k = 2 and k = 3, and the R-tree data structure does this in higher dimensional spaces (but also has some extra structure layered on top).

Typically, high-dimensional data structures don't have huge branching factors like this. Data structures like the k-d tree (or, more generally, BSP trees) store high-dimensional data but have a fixed branching factor of two to avoid exponentially increasing the space usage for high dimensions. Segment trees in high dimensions often use fractional cascading, which lets them use a low branching factor without sacrificing performance.

Hope this helps!

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top