astronomy-commons / astronomy-commons/lsdb
One-to-one match
- Dominant language
- Python
- Stars
- 55
- Forks
- 26
- Avg merge
- 4d 1h
- Merged PRs (30d)
- 8
Description
With the current cross-matching approach, we can only perform many-to-one and many-to-many matches, but not one-to-one matches. From my understanding, this is due to two features of the LSDB:
1. At the healpix level, we may use the same right table catalog object in two parallel matching tasks. For instance, an object from the right-table that is located in tile A, close to the border with tile B, may find left catalog counterparts in both tiles A and B.
2. At the `KdTreeCrossmatch` level, we match objects from the left catalog to a kD-tree of right catalog objects, which may result in the same right catalog object being matched multiple times.
While the second problem can be easily fixed at the level of the cross-matching algorithm, the first problem is rooted in the LSDB pipeline. Due to the nature of our task parallelization, multiple matches from the left catalog would exist in different healpix tiles and different data frame partitions.
A possible solution is to implement a spatial “group-by `right_hipscat_index`” on the cross-matched catalog :
1. Create a margin cache for the matched catalog based on the left catalog margin cache. This would be the only step requiring cross-partition interaction.
2. Concatenate margin caches with their corresponding partitions.
3. For each partition, drop right catalog objects that do not refer to this partition (i.e., their Norder and Npix do not match the partition’s).
4. For each partition, group by the right catalog `_hipscat_index`, aggregating the left catalog row (in this case, selecting the one with the smallest separation).
5. “flip” the index to use the right catalog `_hipscat_index` instead of the left catalog’s.
One-to-one matching is just a special case. I can see users wanting to run different aggregation pipelines on the cross-matched results. For example, they might want to select the best host galaxy match or concatenate time-series data.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading the current cross-matching pipeline and the KdTreeCrossmatch level described in the issue. Work through the proposed margin-cache, partition filtering, grouping by right_catalog _hipscat_index, and index-flipping steps. Done should support one-to-one matching by retaining the smallest-separation left match and allow other aggregations on cross-matched results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- data-engineering
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 28/100