Deduplication system

• US 7,092,956 B2
• Filed: 11/02/2001
• Issued: 08/15/2006
• Est. Priority Date: 11/02/2001
• Status: Active Grant

• Current Assignee: GE Capital US Holdings, Inc. (General Electric Company)
• Original Assignee: General Electric Capital Corporation (General Electric Company)
• Inventors: Ruediger, Thomas
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US10/000,271
• Publication Number:
  US 20030097359A1
• Time in Patent Office: 1,747 Days
• Field of Search: 707/1, 707/6, 707/7, 707/101, 707/102, 707/10, 707/2, 707/3, 707/103.R, 707/104.1, 711/216, 706/47, 709/200
• US Class Current: 707/602
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system to load data in a data warehouse includes reception of a plurality of records, determination, for each of the plurality of records, of values representing differences between a record and each other of the plurality of records, identification of at least two of the plurality records as duplicates based on a determined value representing a difference between the two records, and storage of the two records in the data warehouse in association with a same identifier. Determination of the values may include determination, for each of a first plurality of data fields of the record, of a first value representing a difference between data specified in the data field and data specified in a respective one of a second plurality of data fields of one of the other of the plurality of records, determination, for each of the second plurality of data fields, of a second value representing a difference between data specified in the data field and data specified in a respective one of the first plurality of data fields, and determination of a third value representing a difference between the record and the one of the other of the plurality of records based on the determined first and second values.

Claims

1. A method for determining a value representing a difference between a first record comprising a first plurality of data fields and a second record comprising a second plurality of data fields, each of the first plurality of data fields corresponding to a respective one of the second plurality of data fields, the method comprising:

for each of the first plurality of data fields, determining a first value representing a difference between data specified in the data field and data specified in a respective one of the second plurality of data fields;

for each of the second plurality of data fields, determining a second value representing a difference between data specified in the data field and data specified in a respective one of the first plurality of data fields;

determining a third value representing a difference between the first record and the second record based on the determined first and second values; and

identifying whether the first and second records are duplicates based on the determined third value, wherein the determining and identifying is provided by a processor;

wherein the determining of the third value comprises;

determining a sum of the determined first values and the determined second values; and

dividing the sum by two.

2. An apparatus according to claim 1, wherein the instructions to determine the first value and the instructions to determine the second value comprise identical steps performed with respect to different inputs.

3. An apparatus according to claim 1, wherein the first plurality of data fields and the second plurality of data fields include only those fields of the first record and the second record that specify data that is not identical to data specified in a respective field.

4. A method for determining a value representing a difference between a first record comprising a first plurality of data fields and a second record comprising a second plurality of data fields, each of the first plurality of data fields corresponding to a respective one of the second plurality of date fields, the method comprising:

for each of the first plurality of data fields, determining a first value representing a difference between data specified in the data field and data specified in a respective one of the second plurality of data fields;

for each of the second plurality of data fields, determining a second value representing a difference between data specified in the data field and data specified in a respective one of the first plurality of data fields;

determining a third value representing a difference between the first record and the second record based on the determined first and second values; and

identifying whether the first and second records are duplicates based on the determined third value, wherein the determining and identifying is provided by a processor,

wherein the determining of the first value comprises;

determining an asymmetric spelling distance as a normalized cost for converting first input data to second input data via a sequence of operations; and

wherein the step of determining the second value comprises;

determining an asymmetric spelling distance as a normalized cost for converting second input data to first input data via the sequence of operations.

5. A method according to claim 4, wherein the step of determining the third value comprises:

determining, for each of the first plurality of data fields and respective ones of the second plurality of data fields, a fourth value based on a mean of a first value determined for one of the first plurality of data fields and a second value determined for a respective one of the second plurality of data fields; and

summing the determined fourth values.

6. A method according to claim 4, wherein the determining of the first value and the determining of the second value comprise identical operations performed with respect to different inputs.

7. A method according to claim 4, wherein, in the determining of the first value, the first input data is data specified in one of the first plurality of data fields and the second input data is data specified in a respective one of the second plurality of data fields, and

wherein, in the determining of the second value, the first input data is data specified in one of the second plurality of data fields and the second input data is data specified in a respective one of the first plurality of data fields.

8. A method according to claim 4, further comprising:

converting numerical data specified in the one or more of the first plurality of data fields and the second plurailty of data fields to text data.

9. A method according to claim 4, wherein the first plurality of data fields and the second plurality of data fields include only those fields of the first record and the second record that specify data that is not identical to data specified in a respective field.

10. An apparatus storing processor-executable instructions thereon to determine a value representing a difference between a first record comprising a first plurality of data fields and a second record comprising a second plurality of data fields, each of the first plurality of data fields corresponding to a respective one of the second plurality of data fields, the instructions comprising:

instructions to determine, for each of the first plurality of data fields, a first value representing a difference between data specified in the data field and data specified in a respective one of the second plurality of data fields;

instructions to determine, for each of the second plurality of data fields, a second value representing a difference between data specified in the data field and data specified in a respective one of the first plurality of data fields;

instructions to determine a third value representing a difference between the first record and the second record based on the determined first and second values; and

instructions to identify whether the first and second records are duplicates based on the determined third value,

wherein the instructions determine the first value comprises;

instructions to determine an asymmetric spelling distance as a normalized cost for converting first input data to second input data via a sequence of operations; and

wherein the instructions to determine the second value comprises;

instructions to determine an asymmetric spelling distance as a normalized cost for converting second input data to first input data via the sequence of operations.

11. An apparatus according to claim 10, wherein, in the instructions to determine the first value, the first input data is data specified in one of the first plurality of data fields and the second input data is data specified in a respective one of the second plurality of data fields, and

wherein, in the instructions to determine the second value, the first input data is data specified in one of the second plurality of data fields and the second input data is data specified in a respective one of the first plurality of data fields.

12. A data warehouse comprising:

a processor; and

a storage device in communication with the processor and storing instructions adapted to be executed by the processor to;

determine, for each of a first plurality of data fields of a first record, a first value representing a difference between data specified in the data field and data specified in a respective one of a second plurality of data fields of a second record,

determine, for each of the second plurality of data fields, a second value representing a difference between data specified in the data field and data specified in a respective one of the first plurality of data fields,

determine a third value representing a difference between the first record and the second record based on the determined first and second values; and

identify whether the first and second records are duplicates based on the determined third value, wherein the instructions adapted to be executed by the processor to determine the first value comprise instructions adapted to be executed by the processor to;

determine an asymmetric spelling distance as a normalized cost for converting first input data to second input data via a sequence of operations; and

wherein the instructions adapted to be executed by the processor to determine the second value comprise instructions adapted to be executed by the processor to;

determine an asymmetric spelling distance as a normalized cost for converting the second input data to the first input data via the sequence of operations.

13. A data warehouse according to claim 12, wherein the instructions adapted to be executed by the processor to determine the first value and to determine the second value comprise identical steps performed with respect to different inputs.