New astronomy projects generate observation images continuously and these images are converted into tabular catalogs online. Furthermore, each such new table, called a sample table, is compared against a reference table on the same patch of sky to annotate the stars that match those in the reference and to identify transient objects that have no matches. This cross match must be done within a few seconds to enable timely issuance of alerts as well as shipping of the data products off the pipeline.

To perform the online cross match of tables on celestial objects, or star tables in short, we propose three parallel algorithms, zoneMatch, gridMatch and quadtreeMatch. For zoneMatch and gridMatch, they adapt existing indexes for the spherical coordinate system of celestial objects. Sp...[ Read more ]

New astronomy projects generate observation images continuously and these images are converted into tabular catalogs online. Furthermore, each such new table, called a sample table, is compared against a reference table on the same patch of sky to annotate the stars that match those in the reference and to identify transient objects that have no matches. This cross match must be done within a few seconds to enable timely issuance of alerts as well as shipping of the data products off the pipeline.

To perform the online cross match of tables on celestial objects, or star tables in short, we propose three parallel algorithms, zoneMatch, gridMatch and quadtreeMatch. For zoneMatch and gridMatch, they adapt existing indexes for the spherical coordinate system of celestial objects. Specifically, zoneMatch divides the observation area by the declination coordinate of the celestial sphere whereas gridMatch utilizes a two-dimensional grid on the declination and the right ascension. For quadTreeMatch, the space is regularly subdivided into 4 children until each bucket contains no more than B points, where B is the bucket capacity. With either index on the reference table, we match the stars in the sample table through parallel index probes on the reference. We implemented these algorithms on a multicore CPU as well as a desktop GPU, and evaluated their performance on both synthetic data and real-world astronomical data. Our results show that gridMatch is faster than zoneMatch at the cost of memory space and quadTreeMatch is the slowest one. All parallelization achieves speedups of orders of magnitude.