Nearest neighbour search with arbitrary distance function

I would like to do an efficient nearest neighour search on multidimensional vector spaces with arbitrary distance functions. Kd-trees are a viable alternative but they only work for "coordinate" based metrics. In particular, how would I do an efficient nearest neighbour search with the cosine distance function?

Any pointers would be helpful.

Thanks. Sam.

-- 
Sameer Siruguri			               DH3036/3062, CS, Rice University
siruguri_at_cs.rice.edu        713-348-2842/2282         www.cs.rice.edu/~siruguri