US5497486A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of merging large databases in parallel
Assignee: S Aqua Semiconductor LLC
•
Filing: 1994-03-15
•
Granted: 1996-03-05
•
Expires: 2014-03-15
Abstract
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.
Inventors
- 👤 Salvatore J. Stolfo
- 👤 Mauricio A. Herna/ ndez
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 11:15
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/06; G06F7/14; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; G06F16/50; G06F16/58; G06F16/583; G06F16/5838; G06F7/22; G06F7/32; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99937
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
340 words
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≦p≦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 i represents record i in a cluster. 0≦i≦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 pM-1 , . . . , r pM+w-2 , for 1≦p≦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.
Claim 2
Independent Claim
340 words
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≦p≦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 i represents record i in a cluster. 0≦i≦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 pM-1 , . . . , r pM+w-2 , for 1≦p≦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.
Claim 3
Dependent Claim
142 words
The method according to claim 1, wherein: (a) in each group of processors for each database: (i) N is a number of records in the database; (ii) P is a number of processors p; and (iii) C is a number of clusters to be formed per processor p; and (b) each said comparing step comprises the steps of: (i) dividing the N records into CP subranges; (ii) assigning to each processor C clusters of the subranges; (iii) providing a coordinator processor which reads the database and sends each record to an appropriate processor where each record is received; (iv) saving each received record at each processor where it is received in a proper local cluster; (v) after the coordinator finishes reading and clustering the data among the processors, sorting and applying a window scanning method to the local clusters of each processor.
Claim 4
Dependent Claim
23 words
The method according to claim 2, wherein the coordinator processor load balances the various processors using a simple longest processing time first strategy.
References Cited (Backward Citations)
US4209845A
Cited
US4930072A
Cited
US5355481A
Cited
US5146590A
Cited
US5142687A
Cited
US5111395A
Cited
US5303149A
Cited
US5193207A
Cited
US5319739A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-05 | 1999-09-04 | 2000-03-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-05 | 2003-09-04 | 2004-03-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-05 | 2007-09-04 | 2008-03-05 | $7700.00 | Window Closed / Lapsed |