Question

What is the steps of the insertion algorithm of R* Tree?

Note: I want to be able to construct the tree by insertion. IT ALWAYS GIVES ME CRAP TREES with maximum overlap and maximum area cover not matter what condition I choose for selecting the best leaf (test minimum overlap area after adding at each level of the tree, minimum expansion ration at each level of the tree, etc).

Now how this R* Tree is constructed by insertion so beautifully (from Wikipedia):

enter image description here

Was it helpful?

Solution

The R*-Tree is not just a different insertion leaf strategy.

The spitting strategy (perimeter!) is just as important, as it prefers "quadratic" pages, as opposed to the slices produced by other strategies such as Ang-Tan.

Furthermore, and this is maybe the key to getting prettier trees, the R*-tree performs a kind of rebalancing to actively avoid bad splits. Instead of splitting, when a node is overfull, it also removes the least central elements (or subtrees - you need this at all levels) and reinserts them. This doesn't always prevent the overflow, but it may reduce overlap in a tree.

But of course you can do various mistakes in implementing, and the R-tree will still work, just not perform well because of the bad structure. How bad is your tree, do you have a screenshot?

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