Back to Volume
Paper: An O(N logM) Algorithm for Catalogue Crossmatching
Volume: 347, Astronomical Data Analysis Software and Systems XIV
Page: 346
Authors: Devereux, D.; Abel, D.J.; Power, R.A.; Lamb, P.R.
Abstract: Catalogue cross-matching is an inherently costly operation. Our algorithm applies filter-refine and plane sweep techniques. Pre-processing consists of a sort by declination, and the active list is a queue indexed by a binary tree. The algorithm is O(N logM) in both I/O and processor costs, with only moderate memory requirements. Empirical assessment on catalogues of up to a billion records suggests that the algorithm performs at least an order of magnitude better than the techniques in current use.
Back to Volume