python sklearn KDTree with haversine distance

Question

I try to create a KD tree of WGS84 coordinates and find neighbors within a certain radius

from sklearn.neighbors.dist_metrics import DistanceMetric
from sklearn.neighbors.kd_tree import KDTree    
T = KDTree([[47.8665, 8.90123]], metric=DistanceMetric.get_metric('haversine'))

But get the following error:

ValueError: metric HaversineDistance is not valid for KDTree

How can I use haversine distance in a KD-Tree?

Variorum

Answer 1

The k-d-tree can (to the best of my knowledge) only be used with Minkowski norms.

There are other trees such as the ball tree in sklearn, or the covertree in ELKI that work with Haversine distance because it is a metric.

Benedetta

You can also use the KDTree but then you have to convert your longitude, latitude pairs to carthesian/euclidean values and convert the distance value back to miles or kilometers than. As far as I know you can also convert longitude and latitude to radians which gives you the distances directly in kilometers. But haven't tested that. – Lilias

@Matthias: That doesn't work for large distances, though. Points [0km, 40 000km] and [0km, -40 000km] are very close to each other on a globe, but not according to the KDTree you propose. – Secant

Answer 2

KDTree.valid_metrics

Output -

['p',
 'l1',
 'chebyshev',
 'manhattan',
 'minkowski',
 'cityblock',
 'l2',
 'euclidean',
 'infinity']

Which tells, you can't use haversine with KDTree. The reason behind it is haversine distance gives you Orthodromic distance which is the distance measure used when your points are represented in a sphere. But in a kdTree the points are organised in a tree which makes it invalid to use.

Jabberwocky

Thanks for the explanation. Any idea to how to make it run faster than in O(n^2) (calculating all distance pairs) ? – Variorum

There are trees which work with haversine. But the kd-tree doesn't. In python, the ball-tree is an example. – Benedetta

Oh I was totally unaware of that. Thanks for the info. I'll read about it. – Jabberwocky