Add k-d tree index #8

Activity

1. willirath commented on Jun 29, 2020

   

   willirath

   on Jun 29, 2020

   Contributor

   More actions

   would it make sense to reuse scikit-learn's KDTree instead of Scipy's cKDTree?

   Yes, definitely!

   It would be interesting to test/benchmark the ball tree + haversine approach versus the kd-tree + conversion lat/lon spherical -> xyz cartersian.

   I'm not sure I understand why we should not also do the ball tree benchmark with lat/lon to spherical and the kd-tree with haversine. I'd go for a matrix like

   tree:
     - ball tree
     - kd-tree
   transform_metric:
     - (deg2rad, haversine)
     - (to sphere, euclidian)
   

   (Sorry, hit send to early.)
2. benbovy commented on Jun 29, 2020

   

   benbovy

   on Jun 29, 2020

   MemberAuthor

   More actions

   I don't think we can use k-d tree with lat/lon haversine: https://news.ycombinator.com/item?id=9281998

   The rest of the matrix is valid. Ball tree works with any metric that respects the triangle inequality.
3. benbovy commented on Jun 29, 2020

   

   benbovy

   on Jun 29, 2020

   MemberAuthor

   More actions

   Actually, there is already detailed comparison + benchmarks in Jake's blog post. But it'd still be interesting to see it applied to NEMO/FESOM spatial data patterns and the metrics/conversions used here.
4. benbovy commented on Jun 29, 2020

   

   benbovy

   on Jun 29, 2020

   Last edited by benbovy

   MemberAuthor

   More actions

   Mmm now I'm confused about the validity of kd-tree + haversine. I'm wondering why haversine is not in the list of valid metrics for scikit-learn's KDTree.

   We should might also consider the implementation in pykdtree.