Adaptive clustering of records and entity representations

• US 8,316,047 B2
• Filed: 04/24/2009
• Issued: 11/20/2012
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Inventors: Bayliss, David Alan
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Walker, Bryan
• Application Number:
  US12/429,403
• Publication Number:
  US 20090271363A1
• Time in Patent Office: 1,306 Days
• Field of Search: 707/780, 707/999.006, 707/740
• US Class Current: 707/780
• 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: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Disclosed is a system for, and method of, determining whether records and entity representations should be linked. The system and method include assigning to each pair of entity references a match value reflecting the likelihood that the entity references are related. Based on the match values, each entity reference may then associated with a preferred entity reference. Pairs of entity references that are mutually preferred may then be identified and linked. The process may be iterated to generate further links.

Claims

1. A computer implemented iterative process for generating entity representations by identifying and linking related records in a computer implemented database using a record matching formula, each record and entity representation electronically stored in the database, each record comprising a plurality of fields, each field configured to contain a field value, the process comprising:

assigning to each pair of records from a plurality of records in the database a match value using the record matching formula, wherein the record matching formula is of the form

2. The process of claim 1 wherein each preferred record associated with a given record comprises a record that, when paired with the given record, has a maximal assigned match value in comparison to match values assigned to other record pairs comprising the given record.

3. The process of claim 1 further comprising, for at least one mutually preferred pair of records consisting of a first record and a second record, altering at least one field value from the first record based on at least one field value from the second record.

4. The process of claim 1 wherein the match value reflects a number of field values common to the pair of records.

5. The process of claim 1 wherein the database comprises a third record and a fourth record, wherein the third record is an associated preferred record of the fourth record and wherein the fourth record is not an associated preferred record of the third record.

6. The process of claim 1 further comprising, after the step of forming and prior to the step of retrieving:

for a particular record in a particular entity representation, assigning to each pair of records consisting of the particular record and a record from a entity representation different from the particular entity representation, a match value using the record matching formula;

determining a mutually preferred record for the particular record; and

linking the particular entity representation to the mutually preferred record for the particular record.

7. A computer implemented iterative process for generating entity representations by identifying and linking related records in a computer implemented database using a record matching formula, each record and entity representation electronically stored in the database, each record comprising a plurality of fields, each field configured to contain a field value, the process comprising:

determining a symmetric mutually preferred pair of records consisting of a first record and a second record, each comprising at least a one-way relationship with each other, and wherein a match score of the first record and the second record as computed using the record matching formula is at least as great as a match score of the first record and any other record in the database, and wherein the match score of the first record and the second record as computed using the record matching formula is at least as great as a match score for the second record and any other record in the database, wherein the record matching formula is of the form

8. A computer system for iteratively generating entity representations in a computer implemented database using a record matching formula, the database comprising a plurality of records, each record comprising a plurality of fields, each field configured to contain a field value, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field configured to contain a field value;

a processor programmed to assign to each pair of records from a plurality of records in the database a match value using a the record matching formula, wherein the record matching formula is of the form

9. The system of claim 8 wherein each preferred record associated with a given record comprises a record that, when paired with the given record, has a maximal assigned match value in comparison to match values assigned to other record pairs comprising the given record.

10. The system of claim 8 further comprising processor programmed to, for at least one mutually preferred pair of records consisting of a first record and a second record, alter at least one field value from the first record based on at least one field value from the second record.

11. The system of claim 8 wherein the match value reflects a number of field values common to the pair of records.

12. The system of claim 8 wherein the database comprises a third record and a fourth record, wherein the third record is an associated preferred record of the fourth record and wherein the fourth record is not an associated preferred record of the third record.

13. The system of claim 8 further comprising:

a processor programmed to, for a particular record in a particular entity representation, assign to each pair of records consisting of the particular record and a record from a entity representation different from the particular entity representation, a match value using the record matching formula;

a processor programmed to determine a mutually preferred record for the particular record; and

a processor programmed to link the particular entity representation to the mutually preferred record for the particular record.

14. A computer system for iteratively generating entity representations by identifying and linking related records in a computer implemented database using a record matching formula, each record and entity representation electronically stored in the database, each record comprising a plurality of fields, each field configured to contain a field value, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field configured to contain a field value;

a processor programmed to determine a symmetric mutually preferred pair of records consisting of a first record and a second record, wherein a match score of the first record and the second record as computed using the record matching formula is at least as great as a match score of the first record and any other record in the database, and wherein the match score of the first record and the second record as computed using the record matching formula is at least as great as a match score for the second record and any other record in the database, wherein the record matching formula is of the form