Is k-d tree efficient for kNN search. k nearest neighbors search

Question

I have to implement k nearest neighbors search for 10 dimensional data in kd-tree.

But problem is that my algorithm is very fast for k=1, but as much as 2000x slower for k>1 (k=2,5,10,20,100)

Is this normal for kd trees, or am I doing something worng?

Answer 1

I know this question has been answered, but for more detail on KNN searches with k-d trees, see Bentley (1975:514), Communications of the ACM 18(9), September.