Pairing algorithm

Figure: The index join

This section describes the pairing algorithm used by catpair. Strictly speaking you should not need to know the details of the algorithm in order to use catpair, but the information is provided for reference and completeness. catpair uses an index join technique which is illustrated in Figure . The secondary catalogue is sorted on the second coordinate to be used in the pairing.¹³ The algorithm is then as follows. Every entry in the primary catalogue is examined sequentially and for each entry the critical distance, $D$, is used to compute the minimum and maximum values of the sorted coordinate which could pair with the primary row. The rows in the secondary catalogue corresponding to these minimum and maximum values are then identified (remember that the secondary is sorted on this column) to yield a range of rows which might pair. All of these rows are then examined individually to check if they do pair.

The advantages of this technique are that it is relatively straightforward and it does not require the primary catalogue to be sorted (though the secondary must). The main disadvantage is that the ranges in the secondary corresponding to subsequent rows in the primary may overlap, thus leading to multiple reads of rows in the secondary. The technique is most appropriate where a small primary is being paired with a large secondary; perhaps a small personal list of target objects is being paired with a large standard catalogue. However, it will certainly work if the primary and secondary are of similar size; it will merely take somewhat longer to execute than is strictly necessary.