Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

API design for pointwise indexing #475

Open
jhamman opened this issue Jul 15, 2015 · 35 comments

Comments

@jhamman
Copy link
Member

commented Jul 15, 2015

There have been a number of threads discussing possible improvements/extensions to xray indexing. The current indexing behavior for isel is orthogonal indexing - in other words, each coordinate is treated independently (see #214 and #411 for more discussion).

So the question: what is the best way to incorporate diagonal or pointwise indexing in xray? I see two main goals / applications:

  1. support simple form of numpy style integer array indexing
  2. support pointwise array indexing along coordinates via computation of nearest-neighbor indexes - I think this can also be thought of as a form of resampling.

Input from @WeatherGod, @wholmgren, and @shoyer would be great.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 15, 2015

So, the good news is that once we figure out the API for pointwise indexing, I think the nearest-neighbor part could be as simple as supplying method='nearest'.

The challenge is that we want to go from an DataArray that looks like this:

In [4]: arr = xray.DataArray([[1, 2], [3, 4]], dims=['x', 'y'])

In [5]: arr
Out[5]:
<xray.DataArray (x: 2, y: 2)>
array([[1, 2],
       [3, 4]])
Coordinates:
  * x        (x) int64 0 1
  * y        (y) int64 0 1

To one that looks like that:

In [6]: xray.DataArray([1, 4], {'x': ('c', [0, 1]), 'y': ('c', [0, 1])}, dims='c')
Out[6]:
<xray.DataArray (c: 2)>
array([1, 4])
Coordinates:
    y        (c) int64 0 1
    x        (c) int64 0 1
  * c        (c) int64 0 1

Somehow, we need to figure out the name for the new dimension (c in this example).

My thought would be to have methods sel_points and isel_points that work similarly to sel and isel. This is straightforward if you already have xray 1D objects with a labeled dimension: arr.sel_points(x=x, y=y), where x and y are along the c dimension.

If you don't already have 1D xray objects, I suppose we could also allow arr.sel_points(x=('c', [0, 1]), y=('c', [0, 1])) or arr.sel_points('c', x=[0, 1], y=[0, 1]).

@wholmgren

This comment has been minimized.

Copy link

commented Jul 15, 2015

Seems like if your method is going to be named sel_points then points is a reasonable dimension name. Maybe support a name kwarg?

One thing to keep in mind is that for many of us the "nearest-neighbor" part isn't really method='nearest', but instead more like, method='ingridcell' where the grid cell might be roughly square or might be something pretty different. At least that's how I think of my data. Maybe what I really want is some other kind of more explicit support for gridded data, although my thoughts on this are too half-baked to clearly write down. I thought there was another issue related to this, but I couldn't find it.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 15, 2015

Seems like if your method is going to be named sel_points then points is a reasonable dimension name.

Yes, this is a reasonable choice for the case of 1d indexers.

Maybe support a name kwarg?

This is also a good idea, though I would probably call the parameter dim, not name.

One thing to keep in mind is that for many of us the "nearest-neighbor" part isn't really method='nearest', but instead more like, method='ingridcell' where the grid cell might be roughly square or might be something pretty different.

Indeed. As a start, we should be able to do nearest neighbor lookups with a tolerance soon -- I have a pandas PR that should add some of that basic functionality (pandas-dev/pandas#10411). In the long term, it would be useful to have some sort of representation of grid cells in the index itself, possibly something similar to IntervalIndex (pandas-dev/pandas#8707).

@jhamman jhamman changed the title api design for pointwise indexing API design for pointwise indexing Jul 15, 2015

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jul 15, 2015

I like:

DataArray.isel_points(x=[1, 2, 3], y=[0, 1, 2], dim='points')

I also like the nearest-neighbor / resample API of:

DataArray.sel_points(lon=[-123.25, -140.0, 72.5], lat=[45.0, 72.25, 65.75],
                     dim='points', method='nearest')

How do we want to do the nearest-neighbor selection? The simplest case would be to follow the cKDTree example from #214. However, when you're using lat/lon coordinates, it is usually best to map these coordinates from the spherical coordinates to a Cartesian coordinates (see here for a simple example using cKDTree. Is that a road we want to go down here?

Further along that subject, but not directly relate - has anyone used pyresample.

@wholmgren

This comment has been minimized.

Copy link

commented Jul 16, 2015

Unidata also has a blog post benchmarking cKDTree and other methods and concludes "Your Mileage May Vary". I'd probably just go with a KDTree, but something to aware of.

@rabernat

This comment has been minimized.

Copy link
Contributor

commented Jul 16, 2015

There is a great kdtree-based geospatial resampling package you might want to consider building on:
https://github.com/pytroll/pyresample
It is fast (multithreaded) and has support for different map projections.

@rabernat

This comment has been minimized.

Copy link
Contributor

commented Jul 16, 2015

Maybe this is off topic, but are the plans to support more general spatial resampling / regridding? Like if I have two DataArrays a and b with different spatial coords, it would be great to be able to do

c = a.regrid_like(b)

This is a pretty common practice in climate science, since different datasets are provided on different grids with different resolutions.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 16, 2015

I agree that regridding and resample would be very nice, and pyresample looks like a decent option. I have no immediate plans to implement these features but contributions would be very welcome.

For n-dimensional indexing, kdtree seems sensible, especially if we can cache it on the coordinates. We probably want an explicit API for methods that add new coordinates -- something like ds.set_kdtree(['latitude', 'longitude']).

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jul 16, 2015

As a first step, I'll volunteer (unless someone else is more keen on doing this work) to put together a pull request for isel_points.

After that, we'll want to add the sel_points and kdtree API, which will depend on isel_points.

Later on, I'm also interested in regridding and resampling between grids - let's open another issue for that. Maybe we use pyresample for that.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 16, 2015

@jhamman it would be great if you could put together a PR for isel_points. The main complexity is that you'll want to write a version that also works with dask arrays. Let me know if that part is confusing, I can certainly help with that.

As for sel_points, we only need a kdtree if the underlying coordinates are 2D. If latitude and longitude (for example) are 1d, we can just use the existing machinery for remapping label based indexers to integers. This should be pretty straightforward, following the example of isel:
https://github.com/xray/xray/blob/v0.5.1/xray/core/dataset.py#L1024
https://github.com/xray/xray/blob/v0.5.1/xray/core/indexing.py#L157

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jul 17, 2015

Good point on the dask array business. From the dask docs:

Dask.array supports most of the NumPy slicing syntax.
...
It does not currently support the following:

Slicing one dask.array with another x[x > 0]
Slicing with lists in multiple axes x[[1, 2, 3], [3, 2, 1]]

Both of these are straightforward to add though. If you have a use case then raise an issue.

So, from browsing the closed dask issues, it seems like dask has similar support for multi-dimension slicing and indexing as xray. This throws a bit of a wrench in my plan for how I was going to implement isel_points as I had not fully considered the dask array complexities.

I'll have to put a bit more thought into this. Any suggestions on how to index the dask array without looping through individual points would be great.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 17, 2015

Any suggestions on how to index the dask array without looping through individual points would be great.

For now, I actually think selecting individual points and then concatenating the resulting arrays together would be a reasonable start. Yes, it's kind of slow, but once you have a first draft put together that way with the right API we can optimize later.

jhamman added a commit to jhamman/xarray that referenced this issue Jul 20, 2015
Add pointwise indexing via isel_points method
This provides behavior equivalent to numpy slicing with multiple lists.

Example
-------

>>> da = xray.DataArray(np.arange(56).reshape((7, 8)), dims=['x', 'y'])
>>> da
<xray.DataArray (x: 7, y: 8)>
array([[ 0,  1,  2,  3,  4,  5,  6,  7],
       [ 8,  9, 10, 11, 12, 13, 14, 15],
       [16, 17, 18, 19, 20, 21, 22, 23],
       [24, 25, 26, 27, 28, 29, 30, 31],
       [32, 33, 34, 35, 36, 37, 38, 39],
       [40, 41, 42, 43, 44, 45, 46, 47],
       [48, 49, 50, 51, 52, 53, 54, 55]])
Coordinates:
  * x        (x) int64 0 1 2 3 4 5 6
  * y        (y) int64 0 1 2 3 4 5 6 7
>>> da.isel_points(x=[0, 1, 6], y=[0, 1, 0])
<xray.DataArray (points: 3)>
array([ 0,  9, 48])
Coordinates:
    y        (points) int64 0 1 0
    x        (points) int64 0 1 6
  * points   (points) int64 0 1 2

related: pydata#475
@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jul 27, 2015

Now that the isel_points method is implemented, I think it makes sense to discuss the sel_points method in a bit more detail. The main outstanding question is - do we want to support spherical nearest neighbor mapping. The use case is when you are searching for the nearest neighbor using longitudes and latitudes. This example shows an example of to do this by projecting the coordinates onto a sphere. If we go this route, which is probably the most common use case here, we are committing to the coordinates being latitudes and longitudes. Maybe it is better to use a method='spherical' keyword to fall into this path.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 27, 2015

I would start with the easiest case -- lookups of 1d orthogonal arrays, e.g., grid.sel(latitude=stations.latitude, longitude=stations.longitude, method='nearest'). This would very straightforwardly leverage our current machinery.

For 2D lookups, we need a KDTree. Here are some API ideas, just tossing things around...

>>> ds
<xray.Dataset>
Dimensions:      (x: 4, y: 5)
Coordinates:
    latitude     (x, y) float64 0.49 0.5682 -0.3541 -0.9305 -0.9669 0.01558 ...
    longitude    (x, y) float64 0.3758 1.429 -1.698 -1.344 0.5237 0.6152 ...
  * x            (x) int64 0 1 2 3
  * y            (y) int64 0 1 2 3 4
Data variables:
    temperature  (x, y) float64 0.5735 -0.4871 0.4708 0.4907 -0.3318 0.2883 ...

# perhaps set_ndindex is a better name?
>>> ds = ds.set_kdtree(['latitude', 'longitude'], name='latlon_index', method='spherical')
>>> ds
<xray.Dataset>
Dimensions:      (x: 4, y: 5)
Coordinates:
    latitude     (x, y) float64 0.49 0.5682 -0.3541 -0.9305 -0.9669 0.01558 ...
    longitude    (x, y) float64 0.3758 1.429 -1.698 -1.344 0.5237 0.6152 ...
  * latlon_index (x, y) float64 (0.49, 0.3758) (0.5682, 1.429) ...
  * x            (x) int64 0 1 2 3
  * y            (y) int64 0 1 2 3 4
Data variables:
    temperature  (x, y) float64 0.5735 -0.4871 0.4708 0.4907 -0.3318 0.2883 ...

result = ds.sel_points(latitude=other.latitude, longitude=other.longitude, method='nearest')
@shoyer

This comment has been minimized.

Copy link
Member

commented Jul 28, 2015

I started playing around with making an array wrapper for KDTree this evening:
https://gist.github.com/shoyer/ae30a1200f749c84b4c4

I think it has most of the necessary indexing machinery and you can put it in an xray.Dataset like an array. You could easily imagine hooking in a transform argument to KDTreeIndex to handle projection. But of course it hasn't been hooked up to any API yet.

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jul 29, 2015

Very nice. This is the sort of API I was hoping for. It will be a while before I can come back around on this. In the meantime, if someone else wants to take the sel_points method on, that is fine by me.

@shoyer

This comment has been minimized.

Copy link
Member

commented Aug 1, 2015

PR #507 implements the my suggested 1d version of sel_points. Maybe we also want reindex_points, i.e., pointwise indexing by label that is gauranteed to succeed even if some labels are missing?

@shoyer

This comment has been minimized.

Copy link
Member

commented Aug 23, 2016

A few recent developments relevant to this issue:

  • #974 discusses how we could add multi-dimensional indexing with broadcasting. This would subsume the need for separate methods like sel_points and allow also handle indexing grids with grids.
  • #947 adds first class support for MultiIndex coordinates into xarray. This is good model for how a KDTree could work.

So I'm now thinking an API more like this:

>>> ds = ds.set_kdtree(spatial_index=['latitude', 'longitude'])

>>> ds
<xray.Dataset>
Dimensions:        (x: 4, y: 5)
Coordinates:
  * x              (x) int64 0 1 2 3
  * y              (y) int64 0 1 2 3 4
  * spatial_index  (x, y) KDTree
    - latitude     (x, y) float64 0.49 0.5682 -0.3541 -0.9305 -0.9669 0.01558 ...
    - longitude    (x, y) float64 0.3758 1.429 -1.698 -1.344 0.5237 0.6152 ...
Data variables:
    temperature    (x, y) float64 0.5735 -0.4871 0.4708 0.4907 -0.3318 0.2883 ...

>>> result = ds.sel(latitude=other.latitude, longitude=other.longitude,
...                 method='nearest')

For building a tree with lat/lon remapped to spherical coordinates, we should write a method that converts lat and lon arrays into a tuple of x, y, z arrays (e.g., using apply_ufunc from #964). Then this looks like ds.set_kdtree(spatial_index=latlon_to_xyy(ds.latitude, ds.longitude)). Conceivably, we could add some sugar for this, e.g., ds.geo.set_kdtree(spatial_index=['latitude', 'longitude']).

@burnpanck

This comment has been minimized.

Copy link
Contributor

commented Oct 25, 2016

Without following the discussion in detail, what is the status here? In particular, I would like to do pointwise selection on multiple 1D coordinates using multidimensional indexer arrays. I can do this with the current isel_points:

  1. construct the multidimensional indexers
  2. flatten them
  3. create a corresponding MultiIndex
  4. apply the flattened indexers using isel_points, and assign the multi-index as the new dimension
  5. use unstack on the newly created dimension
    The first three points can be somewhat simplified by instead putting all of the multidimensional indexer into a Dataset and then stack it to create consistent flat versions and their multi-index.

Given this conceptually easy but somewhat tedious procedure, couldn't that be something that could quite easily be implemented into the current isel_points? Would a PR along that direction have a chance of being accepted?

@shoyer

This comment has been minimized.

Copy link
Member

commented Oct 25, 2016

@burnpanck I don't think you need to do the flattening/multi-index bit. I believe isel_points/sel_points should just work for you already.

At this point we're really just talking about design refinements (I'll rename the topic).

@burnpanck

This comment has been minimized.

Copy link
Contributor

commented Oct 25, 2016

Really? I get a ValueError: Indexers must be 1 dimensional (xarray/core/dataset.py:1031 in isel_points(self, dim, **indexers) when I try. That is xarray 0.8.2, in fact from my fork recently cloned (~2-3 weeks ago), where I changed one or two asarray to asanyarray to work with units. Was there a recent change in this area?
EDIT: xarray/core/dataset.py looks very similar also here on master, and there are quite a few lines hinting that really only 1D indexers are supported.

@shoyer

This comment has been minimized.

Copy link
Member

commented Oct 25, 2016

@burnpanck Nevermind, you are correct! I misread your comment. This cannot be done currently.

You certainly could try to put this into isel_points, and if you can do it in a clean fashion I an open to accepting it, but keep in mind that the method is going to go away when we finally get around to implementing #974. Work on #974 would probably be more productive, ultimately.

@WeatherGod

This comment has been minimized.

Copy link
Contributor

commented Nov 7, 2017

So, what has become the consensus for performing regridding/resampling? I see a lot of suggestions, but I have no sense of what is mature enough to use in production-level code. I also haven't seen anything in the documentation about this topic, even if it just refers people to another project.

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Nov 7, 2017

@WeatherGod

Short answer. We don't have a tool that is production ready.

Longer answer: xESMF may be the best prospect in the near term. There are two main issues with its current implementation. 1) Lack of out-of-core abilities / integration with dask, and 2) lack of a test suite. Conceptually, it would be great to leverage the low-level remapping tools of ESMPy so I think this is a nice way to move forward as a community but I think everyone agrees it isn't ready for use in any sort of production environment.

This issue introduces the concept of point-wise indexing using nearest neighbor lookups on ND coordinates. @shoyer has an example implementation here but it hasn't moved forward in quite a while.

@WeatherGod

This comment has been minimized.

Copy link
Contributor

commented Nov 7, 2017

Yeah, we need to move something forward, because the main benefit of xarray is the ability to manage datasets from multiple sources in a consistent way. And data from different sources will almost always be in different projections.

My current problem that I need to solve right now is that I am ingesting model data that is in a LCC projection and ingesting radar data that is in a simple regular lat/lon grid. Both dataset objects have latitude and longitude coordinate arrays, I just need to get both datasets to have the same lat/lon grid.

I guess I could continue using my old scipy-based solution (using map_coordinates() or RectBivariateSpline), but at the very least, it would make sense to have some documentation demonstrating how one might go about this very common problem, even if it is showing how to use the scipy-based tools with xarrays. If that is of interest, I can see what I can write up after I am done my immediate task.

@shoyer

This comment has been minimized.

Copy link
Member

commented Nov 7, 2017

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jan 2, 2018

ping @stefanomattia who seems to be interested in the KDTreeIndex concepts described in this issue.

@rabernat

This comment has been minimized.

Copy link
Contributor

commented Jan 2, 2018

Subscribers to this thread will probably be interested in @JiaweiZhuang's recent progress on xESMF. That package is now a viable solution for 2D regridding of xarray datasets.
https://github.com/JiaweiZhuang/xESMF

@stefanomattia

This comment has been minimized.

Copy link

commented Jan 3, 2018

Thanks @jhamman, I'd love to contribute! I'm not that confident in my Python skills, but maybe with a little guidance? Let me know if or how I could help.

@jhamman

This comment has been minimized.

Copy link
Member Author

commented Jan 3, 2018

@stefanomattia - I'd be happy to provide guidance and even to contribute to some of the development. Based on your blog post, I think you may be well on your way.

@shoyer

This comment has been minimized.

Copy link
Member

commented Jan 3, 2018

@jhamman @stefanomattia can you share a link to this blog post? :)

@jhamman

This comment has been minimized.

@stefanomattia

This comment has been minimized.

Copy link

commented Jan 4, 2018

That post must look a bit amateurish, I reckon, but if you guys think it could be a starting point for a KD-tree search implementation in xarray, I would be thrilled to contribute! There is no learning without trying, after all. I could start from #475 (comment). @jhamman maybe you could send me an email with a few requirements?

@benbovy

This comment has been minimized.

Copy link
Member

commented Jan 5, 2018

Note that it will probably be easier to implement such KDTreeIndex after having refactored indexes and multi-indexes in xarray (see #1603). I think this refactoring would represent a good amount of work, though, so maybe we can do it after if you don't want to wait too long for the KD-Tree feature?

@duncanwp

This comment has been minimized.

Copy link
Contributor

commented Jan 9, 2018

Further to the comment I made in a related issue #486 comment I've now taken a simplified version of the collocation approach in CIS and created a stand-alone package which works with xarray objects: https://github.com/cistools/collocate.

This works essentially the same as the nice example shown in the above blog, with some key differences:

  • The points within a certain distance (tolerance) of each sample point can be aggregated or selected from using the built-in kernels, allowing fast operations over many sample points.
  • The horizontal distance constraint can be supplemented with constraints in other dimensions (such as time or altitude).
  • The transform from Cartesian to Eucledian coordinates is not needed as we use our own KD-Tree implementation which builds haversine rectangles. Depending on use cases this isn't always the fastest approach, but it does sidestep some nasty dateline issues.
  • In the case where only the nearest points in the horizontal is needed the collocation falls back the fast single point lookup.
  • The KD-Tree implementation is (relatively well) separated so could easily be switched out for cKDtree or pyresample implementations
  • There are a some tests too, although no docs yet.

I'll try and put together a notebook building on the above blogpost so that the similarities and differences are a bit clearer.

I'm not familiar enough with xarray indexing to be able to say how well this would fit inside xarray, but hopefully it will be useful before we're able to crack KD-MultiIndexes!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
9 participants
You can’t perform that action at this time.