Performance?

I'm curious, have you measured the performance of this r-tree? During my extensive nearest neighbor search experiments in the past, I did make an attempt at an r-tree, but I found at least my impelementation to provide far inferior performance to my bucket kd-tree.

How about seeing how many points are returned by the RS, and seeing how long it takes with that many points for kNN in comparison?

I've been considering testing RS in DrussGT instead of all of those movement buffers, but I'm too busy at the moment...

I did the exactly same. Something like this: E[] arr1 = rTree.rangeSearch(getRange(currentLoc)); E[] arr2 = kDTree.nearestNeighbor(currentLoc, arr1.length)

I'm curious, the does the RS give the same results? Or does the kNN return points in a hypersphere, whereas the RS gives results in a hypercube?

Now i'm curious too, but i hope, that results will pretty same:) I will publish results, when i will try it

Hmm... that performance difference is fairly expected. kNN spends a lot of time doing distance calculations that RS doesn't need to do. Also, just a note.... I think the questions of using r-trees vs kd-trees should be separate from whether RS or kNN is used. I say that because well... both types of trees can do both types of searches.

I completely agree with you. But i think, that r-tree is faster with RS, but kD-tree is faster with kNN

That's an interesting theory, could perhaps be the case. I might test that some time.

I think that range searches would definitely be faster using R-trees. In a range search, you could add every point within the rectangle of an R-tree without calculating any distances for those points. Of course, your tree uses minimum bounding rectangles so you could do that too, but a normal kd-tree couldn't. For a kNN search the main advantage of an R-tree is probably the ease with which you can rebalance the tree.

Good point about the minimum bounding rectangles. Thinking about it some more, I suspect that the RS speed of a kd-tree that uses minimum bounding rectangles, would be extremely similar to that of a R-tree really. Sure, the partitioning is a bit different but both have reasonable enough partitioning and with the minimum bounding rectangles the search algorithm would basically be the same.

Yeah, that rebalancing aspect is what prompted me to do some r-tree experiments in the past.