ADAPTIVE CLUSTERING OF RECORDS AND ENTITY REPRESENTATIONS

• US 20090271363A1
• Filed: 04/24/2009
• Published: 10/29/2009
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk & Information Analytics Group, Inc. (RELX PLC)
• Inventors: BAYLISS, David Alan
• Granted Patent: US 8,316,047 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 capable of containing a field value, the process comprising:

assigning to each pair of records from a plurality of records in the database a match value using a the record matching formula, the match value reflecting a likelihood that the pair of records is related, the match value computed by a programmed processor;

assigning, for each record from the plurality of records, at least one associated preferred record, wherein a match value assigned to a given record together with its associated preferred record is at least as great as a match value assigned to the record together with any other record in the plurality of records;

identifying mutually preferred pairs of records from the plurality of records, each mutually preferred pair of records consisting of a first record and a second record, the first record consisting of a preferred record associated with the second record and the second record consisting of a preferred record associated with the first record;

forming and storing a plurality of entity representations in the database, each entity representation of the plurality of entity representations comprising at least one linked pair of mutually preferred records; and

retrieving information from at least one record of a pair of mutually preferred records.

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. The process of claim 1 wherein the record matching formula is of the form

$S$

( r 1 , r 2 ) = ∑

i = 1 I 

p i 

w i .

8. 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 capable of containing a field value, the process comprising:

determining a 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;

forming a new entity representation in the database, the new entity representation comprising at least the first record and the second record;

determining a mutually preferred pair of records consisting of the first record and a third record, the third record from a different entity representation than the new entity representation, wherein a match score of the first record and the third 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 not in the new entity representation, and wherein a match score of the first record and the third record as computed using the record matching formula is at least as great as a match score for the third record and any other record not in the different entity representation;

consolidating the new entity representation with the different entity representation by linking the new entity representation with the different entity representation resulting in a consolidated entity representation; and

retrieving information from the consolidation entity representation.

9. The process of claim 8 wherein the record matching formula is of the form

$S$

( r 1 , r 2 ) = ∑

i = 1 I 

p i 

w i .

10. 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 capable of containing a field value, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing 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, the match value reflecting a likelihood that the pair of records is related, the match value computed by a programmed processor;

a processor programmed to assign, for each record from the plurality of records, at least one associated preferred record, wherein a match value assigned to a given record together with its associated preferred record is at least as great as a match value assigned to the record together with any other record in the plurality of records;

a processor programmed to identify mutually preferred pairs of records from the plurality of records, each mutually preferred pair of records consisting of a first record and a second record, the first record consisting of a preferred record associated with the second record and the second record consisting of a preferred record associated with the first record; and

a processor programmed to form and store a plurality of entity representations in the database, each entity representation of the plurality of entity representations comprising at least one linked pair of mutually preferred records.

11. The system of claim 10 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.

12. The system of claim 10 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.

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

14. The system of claim 10 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.

15. The system of claim 10 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.

16. The system of claim 10 wherein the record matching formula is of the form

$S$

( r 1 , r 2 ) = ∑

i = 1 I 

p i 

w i .

17. 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 capable of containing a field value, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value;

a processor programmed to determine a 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;

a processor programmed to form and store a new entity representation in the database, the new entity representation comprising at least the first record and the second record;

a processor programmed to determine a mutually preferred pair of records consisting of the first record and a third record, the third record from a different entity representation than the new entity representation, wherein a match score of the first record and the third 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 not in the new entity representation, and wherein a match score of the first record and the third record as computed using the record matching formula is at least as great as a match score for the third record and any other record not in the different entity representation; and

a processor programmed to consolidate the new entity representation with the different entity representation by linking the new entity representation with the different entity representation, resulting in a consolidated entity representation.

18. The system of claim 17 wherein the record matching formula is of the form

$S$

( r 1 , r 2 ) = ∑

i = 1 I 

p i 

w i .