Use BallTree for getting values at nearest neighbor points

blaylockbk / Herbie

Download numerical weather prediction datasets (HRRR, RAP, GFS, IFS, etc.) from NOMADS, NODD partners (Amazon, Google, Microsoft), ECMWF open data, and the University of Utah Pando Archive System.

https://herbie.readthedocs.io/

MIT License

424 stars 70 forks source link

Use BallTree for getting values at nearest neighbor points #296

Closed blaylockbk closed 2 months ago

blaylockbk commented 3 months ago

Implement the BallTree algorithm for nearest neighbor searches to extract data from specific locations.

[x] User supplies a DataFrame with, at minimum, columns 'latitude' and 'longitude'
[x] Default will match nearest grid point
[x] Option to compute distance-weighted interpolated value from nearest 4 points.
[x] Write tests for several different types of cases, inputs.
[x] Benchmark against Herbie's original implementation.
[x] Retain legacy accessor as herbie.nearest_points_legacy for now.

BallTree nearest neighbor lookup is much faster than what I had cooked up before...

blaylockbk commented 3 months ago

Latest timing for the two methods

Nearest simply returns the value at the nearest neighbor point
Weighted gets the 4 nearest neighbors and computes the inverse-distance weighted mean

Note: This is assummeing the BallTree object is cached.

blaylockbk commented 3 months ago

This PR is nearly ready for the real world. I can't wait to share it with everyone and let them try this new feature, which I think will be really helpful for many people.

blaylockbk commented 3 months ago

I updated the, now deprecated, nearest_points accessor (using cartopy transform and metpy method) to take advantage of the advanced xarray selection. It's performance greatly improved, but is still not as effective as the BallTree algorithm.