NearestNeighbours.jl allows any metric from Distances.jl, now supporting Haversine distance. It would make sense to add it as an option. Having a dataset to test this with would be helpful in seeing how often using Euclidean distance causes errors. If the errors are common, using Haversine should be the default.