A vantage point tree allows to do fast but exact nearest neighbor searches in any space provided that you have a metric (function) to measure the distance between any two points in that space.

Bibliography

Yianilos, P. N. (1993, January). Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda (Vol. 93, No. 194, pp. 311-21). http://dx.doi.org/10.1145/313559.313789