Patent Document ID: 5497486
Application ID: 08213795
Patent Flag: 1

Claim One:
1. A method of merging two databases of records, each record having a plurality of fields, comprising the steps of: (a) computing a first key for each record in each database by extracting at least a portion of a first field: (b) parallel merge sorting the records in each database using the first key; (c) comparing to each other, on a first group of at least one processor, a predetermined number of sequential records sorted according to the first key to determine if one or more of the records match; (d) storing identifiers for any matching records; (e) computing a second key for each record in each database by extracting at least a portion of a second field; (f) parallel merge sorting the records in each database using the second key; (g) comparing to each other, on a second group of at least one processor, a predetermined number of sequential records sorted according to the second key to determine if one or more of the records match; (h) storing identifiers for any matching records; (i) creating a union of said stored identifiers; (j) subjecting said union to transitive closure; (k) wherein, in each group of processors for each database: (i) N is a number of records; (ii) P is a number of processors, each processor p, 1.ltoreq.p.ltoreq.P, being able to store M+w records; (a) w is a size of a merge phase window; and (b) M is a blocking factor; (ii) P is less than N; (iii) MP is less than N; and (iv) r.sub.i represents record i in a cluster. 0.ltoreq.i.ltoreq.MP-1; and (1) each said comparing step comprises the steps of: (i) dividing the sorted database into N/MP clusters; (ii) processing each of the N/MP clusters in turn by providing each processor p with records r.sub.(p-1)M,. .. , r.sub.pM-1,. .. , r.sub.pM+w-2, for 1.ltoreq.p.ltoreq.P; (iii) searching matching records independently at each processor using a window of the size w; and (iv) repeating the processing step for a next cluster of records.