4

I am with a problem where a high dimension interval tree may help. I can understand how a unidimensional interval tree works. But I can't see how should be implemented in a higher dimension.

Interval Tree and Range Tree

The explanation at Wikipedia says to use a range tree and a interval tree for each dimension. But I can't see how it works! The explanation there is not clear for me... Please, check the "Higher dimensions" section:

First, a range tree in N dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region R. Once the corresponding ranges are found, the only thing that is left are those ranges that enclose the region in some dimension.

If the range tree is more efficient, why do we need Interval Trees??

Going for Range Trees, we can see it was made for query points inside a interval (the tree does not stores intervals). Therefore, I am assuming that Wikipedia means:

First, a range tree in N dimensions is constructed that allows efficient retrieval of all intervals with beginning OR end points inside the query region R.

Then.. What? If I create a Interval Tree for each dimension from this point, any of these intervals will lie over my search box even if the original objects do not intersect my query. Please check the follow image to try to visualize what I am saying.

Example of two dimensions Interval Tree

Maybe, what is not clear for me is: How do I cross the interval results of both Interval Trees to ensure that it lies over an entity?

Could someone give an explanation how to use range trees in this case?

R Tree

Just to mention, I am aware about the existence of R Tree. But I want to understand the Interval Tree in high dimension first. Moreover, just as a note, at Wikipedia they say:

Interval tree – A degenerate R-tree for one dimension (usually time).

What I strongly do not agree. Otherwise, why we should be talking about High Dimension Interval Tree? If I understand both methods well:

R Tree uses MBR to group entities, while Interval Tree uses points.

R Tree may stores any kind of spatial entity, while Interval Tree stores only intervals.

R Tree needs to split nodes from time to time, what seems to be expensive. Interval Tree never splits a node.

Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194
StudentKiddo
  • 41
  • 2
  • Splitting nodes happens on insertion only, and is necessary for a *balanced* tree. These are usually faster to query, so there is nothing wrong with splitting nodes. – Has QUIT--Anony-Mousse Apr 06 '17 at 07:16
  • Also, why do you think it is beneficial to represent an interval as point? MBRs are exactly multidimensional intervals... – Has QUIT--Anony-Mousse Apr 07 '17 at 17:35
  • And if Wikipedia is not detailed enough, read the original publications and textbooks such as Samet. – Has QUIT--Anony-Mousse Apr 07 '17 at 17:37
  • First. Tks @Anony-Mousse for your help so far. So. Basically I want to implement both. R-Tree and High dimension Interval Tree for comparison. Because, in fact, for my specific work, I am more interested in building the tree as fast as I can than in searching it later(of course, searching also influences building). So I want to understand well both before I move on. – StudentKiddo Apr 09 '17 at 09:58
  • If you can share some material detailing more the implementation for high dimension interval tree, I would be very glad. But so far the explanations I found say "use range-tree and 2 interval tree for the rest of segments, and there it is!". And the point is exactly that... how to use 2 interval trees?? It is not clear... For one dimension, ok, it is clear. For 2 dimensions... I am looking for a clear explanation. – StudentKiddo Apr 09 '17 at 10:05
  • What sources except Wikipedia do you use? – Has QUIT--Anony-Mousse Apr 09 '17 at 22:45

0 Answers0