# Fast nearest neighbor search, Latitude Longitude

Is there a fast nearest neighbor search algorithm that generates the nearest neighbors, not based on Euclidean distances but based on geographic distances over a set of latitudes/longitudes. The fast nearest neighbor search based on Euclidean distances though is based on spatial indexing using R-Trees, K-D Trees etc. What about for Lat/Long distances?

• For Lat/Long interpolation try GMT (Generic Mapping Tools) – stali Jun 12 '13 at 11:38

• I am not sure if I get you with linear projection. Can expand on what you intend to do? For kNN, you use the embedding space and the euclidean metric of that one. You obtain the order in which all points are closest to your point of interest. The actual geodesic distances are different but their relative ordering with respect to their real distance to the reference point is right and that is what matters for nearest neighbor search. – Bort Jun 13 '13 at 20:21