GNU Astronomy Utilities - Tasks: task #15803, Match program builds k-d tree and...
You are not allowed to post comments on this tracker with your current authentication level.
task #15803: Match program builds k-d tree and later read from it
Submitter: | Mohammad Akhlaghi <makhlaghi> | ||
Submitted: | Thu 29 Oct 2020 10:51:11 PM UTC | ||
Should Start On: | Thu 29 Oct 2020 12:00:00 AM UTC | Should be Finished on: | Thu 29 Oct 2020 12:00:00 AM UTC |
Category: | Match | Priority: | 5 - Normal |
Item Group: | Enhancement | Status: | Done |
Privacy: | Public | Assigned to: | sks_15 |
Percent Complete: | 100% | Open/Closed: | Closed |
Effort: | 0.00 |
Jump to the original submission
Mon 15 Nov 2021 02:08:14 AM UTC, comment #10: |
Mohammad Akhlaghi <makhlaghi> |
Sun 18 Apr 2021 02:04:14 AM UTC, comment #9: In the process suggested in the previous comment, the coordinates of the two catalogs will be identical. Although that won't make any difference with regard to this particular test, a more robust test would be to add noise to one of the catalogs (or both) before the match.
|
Mohammad Akhlaghi <makhlaghi> |
Sat 17 Apr 2021 09:20:36 PM UTC, comment #8: Thanks a lot Sachin, I just had a fast look. Here are some points:
|
Mohammad Akhlaghi <makhlaghi> |
Sat 17 Apr 2021 07:17:15 PM UTC, comment #7: I made the commit in which I've changed the name of `match_coordinate_*` functions which did sort-based matching to `match_sort_based_*`. Also, I added the tests to be performed during `make test` in tests/match/.
|
Sachin Kumar Singh <sks_15> |
Mon 29 Mar 2021 01:49:26 AM UTC, comment #6: I done a full re-write in Commit a6c61757668 (commit message in P.S.) and look clear for the final steps now :-). In short, I noticed that all the troubles we were dealing with (one point matching multiple in the other) was already treated before in the sort-based matching.
|
Mohammad Akhlaghi <makhlaghi> |
Sun 13 Dec 2020 02:53:07 AM UTC, comment #5: I made some further improvements in Commit 6b5e8ef1c7, please look into them carefully.
|
Mohammad Akhlaghi <makhlaghi> |
Thu 10 Dec 2020 03:42:51 AM UTC, comment #4: A first implementation of the option reading and preparations has been done in Commit 61e7108b5b12 of my development branch on my development repository.
|
Mohammad Akhlaghi <makhlaghi> |
Wed 04 Nov 2020 10:28:27 PM UTC, comment #3: After the first implementation is complete, we can add an internal/automatic decision to use k-d trees or not.
|
Mohammad Akhlaghi <makhlaghi> |
Tue 03 Nov 2020 10:52:37 PM UTC, comment #2: Thanks for the nice review, its great to add this feature soon :-).
|
Mohammad Akhlaghi <makhlaghi> |
Tue 03 Nov 2020 08:49:59 PM UTC, comment #1: I'm about to begin with the implementation of this task and just wanted to discuss the details of the implementation.
|
Sachin Kumar Singh <sks_15> |
Thu 29 Oct 2020 10:51:11 PM UTC, original submission:
Gnuastro's library now has a k-d tree library. With k-d trees, matching large catalogs can be greatly sped up.
|
Mohammad Akhlaghi <makhlaghi> |
No files currently attached
Depends on the following items: None found
Items that depend on this one: None found
There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.
Follow 9 latest changes.
Date | Changed by | Updated Field | Previous Value | => | Replaced by |
---|---|---|---|---|---|
2021-11-15 | makhlaghi | Open/Closed | Open | Closed | |
2021-11-15 | makhlaghi | Status | In Progress | Done | |
Percent Complete | 90% | 100% | |||
2021-03-29 | makhlaghi | Percent Complete | 70% | 90% | |
2020-12-13 | makhlaghi | Percent Complete | 20% | 70% | |
Summary | Match program should build k-d tree and later read from it | Match program builds k-d tree and later read from it | |||
2020-12-10 | makhlaghi | Status | None | In Progress | |
Percent Complete | 0% | 20% | |||
2020-10-30 | pedram | Carbon-Copy | - | Added pedram |
Powered by Savane 3.13-f8d8.
Corresponding source code
A first, fully working (as far as I have tested it!) version of this branch has been completed and was just merged into the 'master' branch (from Commit c36f753a5bc4 to Commit f5d7d1a351). So I am closing this task.
It involved a lot of work, but the final result is very impressive, and also lead to many good improvements in Table reading (in parallel) and finding/fixing bug #61462 while testing on various large input tables.
To see the current status of the implementation of this branch, see the new "Matching algorithms" section of the book from the links below (which also include the tarball, in case you would like to try it):
https://akhlaghi.org/gnuastro.pdf
https://akhlaghi.org/gnuastro-latest.tar.lz
The only thing that isn't yet implemented is the automatic feature and the benchmarking tests (to deduce when to use sort-based and when to use k-d tree based). But I thought that its not necessary because now by default the k-d tree method is used. The speed improvements of the sort-based method are only relevant when the table is small, and in those cases, even 10 times speed improvement will not be noticeable for a user (it will be a small fraction of milli-second anyway!).
The benchmarking Python scripts have been removed in Commit a6b838c488, but are present in the commits before it, in case they may be necessary later. But generally, Python is not a future-proof language, so it is discouraged.
In that spirit, while completing the work on this branch, I added a 'bin/match/debug-1.sh' script to the version-controlled source of Gnuastro that will allow easy creation of debugging tables. We can later implement the benchmarking steps in shell also (if necessary).