Performance?

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.