astronomy-commons / astronomy-commons/lsdb

One-to-one match

Open
#152 4 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.