US 5,497,486 AGranted

Method of merging large databases in parallel

AssigneeSalvatore J. Stolfo

InventorsSalvatore J. Stolfo, Mauricio A. Herna/ ndez

Life of this patent

Estimating the term…

Loading patent…

Abstract

The semantic integration problem for merging multiple databases of very large size, the merge/purge problem, can be solved by multiple runs of the sorted neighborhood method or the clustering method with small windows followed by the computation of the transitive closure over the results of each run. The sorted neighborhood method works well under this scheme but is computationally expensive due to the sorting phase. An alternative method based on data clustering that reduces the complexity to linear time making multiple runs followed by transitive closure feasible and efficient. A method is provided for identifying duplicate records in a database, each record having at least one field and a plurality of keys, including the steps of sorting the records according to a criteria applied to a first key; comparing a number of consecutive sorted records to each other, wherein the number is less than a number of records in said database and identifying a first group of duplicate records; storing the identity of the first group; sorting the records according to a criteria applied to a second key; comparing a number of consecutive sorted records to each other, wherein the number is less than a number of records in said database and identifying a second group of duplicate records; storing the identity of the second group; and subjecting the union of the first and second groups to transitive closure.

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.

24 more elements

Facts

Application

08/213,795Filed 15 Mar 1994

Granted

5 Mar 1996

Term ends

Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 7/14
Arrangements for sorting, selecting, merging, or comparing data on individual record carriers: merging, i.e. combining at least two sets of record…
G06F 7/32
Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc: merging, i.e. combining data contained in…
G06F 16/24556
Unary operations; Data partitioning operations: aggregation; Duplicate elimination
G06F 16/5838
Using metadata automatically derived from the content: using colour

Abstract

Claims3