CODEWITHSUNDEEP
spatial-indexr-tree
daydayup
daydayup

Reputation: 2317

what is the best R tree variant

I am recently reading papers and codes on R-tree and its variants: linear, quadratic, R*-tree, and also R tree packing (STR). It seems to me that different techniques are different in the time complexities of tree creation, range search, and knn search. STR tree seems better than others. However, the papers were from last century. I just wonder after almost 20 years, what is the best R-tree variant currently?

Upvotes: 3

Views: 1403

Answers (2)

TilmannZ
TilmannZ

Reputation: 1899

Another more recent tree is the X-tree (also based on R-Tree).

If you are looking for general spatial indexing, not only R-Trees, I can recommend the PH-Tree. It can easily compete with R-Tree variants for rectangle or range-queries, has quite good kNN-query support (only 50% slower than Cover-Tree for 21 dimensions), it scales very nicely with large and/or clustered datasets and is quite space efficient. The best thing is probably that it has excellent update performance, insert/move/remove takes hardly longer than a lookup. Another advantage is that it requires no rebalancing, which means that never more than 2 nodes are affected by any update.

Disadvantages:

  • Implementation for low dimensionality is rather complex, but if you are fine with a Java implementation, here is mine.
  • The implementation for high dimensionality is less complex but slow for less than 10 dimensions, also here.
  • It mostly prefers clustered data, but performance is still okay with more evenly distributed data.

Upvotes: 4

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77474

R*-trees are proven to work very well and continue to be the go-to variant.

Bulk-loading techniques such as STR are great addition to build the initial tree faster (and better) instead of inserting objects one by one.

So usually, you will want a R*-tree with STR bulk load.

Upvotes: 2

Related Questions