Entity normalization via name normalization

• US 8,700,568 B2
• Filed: 03/31/2006
• Issued: 04/15/2014
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Betz, Jonathan T.
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US11/394,508
• Publication Number:
  US 20070198600A1
• Time in Patent Office: 2,937 Days
• Field of Search: 707/201, 707/6, 707/3, 707/500, 707/612, 707/655, 717/172
• US Class Current: 707/612
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• 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/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/338 Presentation of query results

Abstract

A system and method identifying duplicate objects from a plurality of objects. The system and method normalizes name values of objects, groups objects into buckets based at least in part on the normalized name values, matches objects within the same bucket based on a selected matcher, and identifies the matching objects as duplicate objects.

Claims

1. A computer-implemented method of identifying duplicate objects in a plurality of objects, each of the plurality of objects having one or more associated facts and being stored in a computer memory, each of the one or more facts having a value, the method comprising:

using a computer processor to perform;

extracting facts from web documents that are located on document hosts;

associating the facts extracted from the web documents with a plurality of objects;

for each of the plurality of objects, normalizing the value of a name fact, the name fact being among the one or more facts associated with the object;

grouping the plurality of objects into a plurality of buckets in accordance with the normalized value of the name facts of the plurality of objects; and

applying a matcher to a pair of objects in one of the plurality of buckets to determine if the pair of objects are duplicates, one of the pair of objects having an associated fact that is not a common fact of the pair of objects.

2. The method of claim 1, wherein normalizing the value of the name fact comprises:

normalizing the value of the name fact by applying a group of normalization rules to the value of the name fact.

3. The method of claim 2, wherein the group of normalization rules comprises at least one rule selected from a group consisting of:

removing social titles; and

removing honorific words.

4. The method of claim 2, wherein the group of normalization rules comprises at least one rule selected from a group consisting of:

removing single letter words;

removing punctuation marks;

removing stop words; and

converting uppercase characters into lowercase.

5. The method of claim 2, wherein the group of normalization rules comprises sorting the value in alphabetic order.

6. The method of claim 1, wherein grouping comprises:

generating a signature for each of the plurality of objects based at least in part on the normalized value of the name fact of each of the plurality of objects, wherein the signatures for duplicate objects are identical even if facts associated with the duplicate objects are not duplicates; and

responsive to an identifier of an existing bucket being the same as the signature of an object, adding the object to the existing bucket, otherwise establishing a new bucket including the object, an identifier of the new bucket being same as the signature of the object.

7. The method of claim 1, wherein applying the matcher to a pair of objects in one of the plurality of buckets comprises:

for each common fact of the pair of objects, determining a similarity of the values of the common fact based on a similarity measure; and

determining that the pair of objects are duplicates based on the similarity.

8. The method of claim 7, wherein determining that the pair of objects are duplicates comprises:

determining that the pair of objects are duplicates based on the number of the common facts with similar values and the number of common facts.

9. The method of claim 1, wherein applying comprises applying the matcher to each pair of objects in one of the plurality of buckets to determine if the pair of objects are duplicates.

10. The method of claim 1, further comprising:

selecting the matcher from a collection of matchers, wherein applying the matcher includes applying the selected matcher to a pair of objects in one of the plurality of buckets to determine if the pair of objects are duplicates.

11. The method of claim 1, further comprising:

merging duplicate objects.

12. A system for identifying duplicate objects in a plurality of objects, each of the plurality of objects having one or more associated facts, each of the one or more facts having a value, the system comprising:

a processor for executing programs; and

a subsystem executable by the processor, the subsystem including;

instructions for extracting facts from web documents that are located on document hosts;

instructions for associating the facts extracted from the web documents with a plurality of objects;

instructions for normalizing the value of a name fact of each of the plurality of objects, the name fact being among the one or more facts associated with the object;

instructions for grouping the plurality of objects into a plurality of buckets in accordance with the normalized value of the name facts of the plurality of objects; and

instructions for applying a matcher to a pair of objects in one of the plurality of buckets to determine if the pair of objects are duplicates, one of the pair of objects having an associated fact that is not a common fact of the pair of objects.

13. The system of claim 12, wherein the subsystem further includes:

instructions for merging duplicate objects.

14. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising:

instructions for extracting facts from web documents that are located on document hosts;

instructions for associating the facts extracted from the web documents with a plurality of objects;

instructions for normalizing the value of a name fact of each of the plurality of objects, the name fact being among the one or more facts associated with the object;

instructions for grouping the plurality of objects into a plurality of buckets in accordance with the normalized value of the name facts of the plurality of objects; and

instructions for applying a matcher to a pair of objects in one of the plurality of buckets to determine if the pair of objects are duplicates, one of the pair of objects having an associated fact that is not a common fact of the pair of objects.

15. The computer program product of claim 14, wherein the one or more programs further comprise:

instructions for merging duplicate objects.