2
$\begingroup$

Say I have 2 permutations of the the same set of elements. I create 2 R-Trees, one for each permutation.

Do I end up with 2 structurally identical R-Trees or not?

PS: My elements are rectangles on a plane.

Edit:

Reformulation of the question: is there an insertion algorithm that reconstructs the same R-Tree regardless of the order of elements in use?

$\endgroup$
  • 2
    $\begingroup$ What is an R-tree? $\endgroup$ – Tyson Williams Oct 15 '12 at 13:58
  • 1
    $\begingroup$ @TysonWilliams en.wikipedia.org/wiki/R-tree I Assume (esp. as elements are rectangle on a plane) $\endgroup$ – jk. Oct 15 '12 at 15:14
  • $\begingroup$ Yes, this R-Tree $\endgroup$ – FearUs Oct 15 '12 at 18:46
  • 1
    $\begingroup$ The answer obviously depends on your insertion/construction algorithm! $\endgroup$ – Jeffε Oct 15 '12 at 22:25
  • $\begingroup$ Yes of course, but I will edit the question to clarify my objective $\endgroup$ – FearUs Oct 16 '12 at 19:36
1
+50
$\begingroup$

the R tree algorithms typically create "R"s (rectangles) iteratively/sequentially based on the order of insertion of the data. the "R"s are built directly out of the coordinates of the data seen so far. it does not appear that there are widely studied R-tree variants that build identical trees no matter what the order is, it does not seem to be a generally desired design criteria for the algorithms, which are judged on other criteria such as performance of search, insertion, overflow splitting etc.

except in artificial/contrived/"pathological" cases, the resulting R-trees will be "close" in structure and performance no matter what order the insertion. however it is not inconceivable that such an algorithm could be devised with the property of "resultant tree invariance" based on adjusting the insertion and overflow splitting logic.

on the other hand if you dont require an online algorithm you could just sort your data according to any criteria beforehand and the R tree will end up with the same structure of course.

a close alternative that can be adjusted to have the "order invariant" property you describe is the Quadtree because it is based on partitioning the overall space (assuming its dimensions are known) in a fractal "4-square" pattern that does not depend on ordering of the input or directly use the individual points for bounding coordinates.

$\endgroup$
  • $\begingroup$ clarification, order invariance as "not generally desired" here does not mean it is "undesirable" just that its apparently not a typical design requirement in the literature. in other words few applications that use R-trees seem to have the requirement that the trees be order invariant. for the questioner however, exceptionally, it is apparently "undesirable" although would like a clarification why that is really so. $\endgroup$ – vzn Oct 21 '12 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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