Performance?

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.