Attribute entropy as a signal in object normalization

• US 8,244,689 B2
• Filed: 02/17/2006
• Issued: 08/14/2012
• 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., Menezes, Vivek
• Primary Examiner(s): Vital, Pierre
• Assistant Examiner(s): Lee, Rachel J
• Application Number:
  US11/356,765
• Publication Number:
  US 20070198597A1
• Time in Patent Office: 2,370 Days
• Field of Search: 707/201
• US Class Current: 707/692
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries

Abstract

A system and method determines whether two objects are duplicate objects. The system and method matches common facts of the two objects based on a match measure, combines the entropies of the matching common facts, and determines whether the two objects are duplicate objects based on the sum of entropies.

Claims

1. A computer-implemented method of determining if a first object and a second object represent a same entity, the method comprising:

identifying one or more common attributes between the first object and the second object, wherein the first object and the second object are included in a fact repository located on one or more computer systems;

determining an entropy for each of the one or more common attributes, wherein a respective entropy for a respective attribute in the one or more common attributes comprises a respective numeric value measuring a respective amount of information carried by the respective attribute;

identifying a subset of the one or more common attributes whose respective values are equivalent;

determining whether the first object and the second object represent the same entity by comparing a sum of entropies for the subset of the one or more common attributes to an entropy threshold measure; and

in response to determining that the first object and the second object represent the same entity, merging the first object and the second object in the fact repository.

2. The method of claim 1 wherein identifying the subset of the one or more common attributes whose respective values are equivalent comprises comparing values of the attributes for the first object and the second object.

3. The method of claim 2, wherein comparing values comprises determining whether the values are the same.

4. The method of claim 2, wherein comparing values comprises calculating a match measure indicating that the values are equivalent.

5. The method of claim 1, wherein the respective numeric value comprises a sum, over all possible values associated with the respective attribute, of a product of a probability of each value and the log of the probability.

6. The method of claim 1, further comprising:

responsive to the first object and the second object being determined to represent the same entity, calculating the entropy of a respective attribute in the one or more common attributes, values of facts for the first object or values of facts for the second object being excluded when doing the calculation.

7. The method of claim 2, wherein comparing values comprises determining whether the values are lexically equivalent.

8. The method of claim 4, wherein the match measure comprises a fuzzy match based on string or tuple similarity measures.

9. The method of claim 1, further comprising:

identifying a first subset of the one or more common attributes whose respective values are equivalent;

identifying a second subset of the one or more common attributes whose respective values are nonequivalent;

determining whether the first object and the second object represent different entities by comparing a difference of a sum of entropies for the first subset of the one or more common attributes and a sum of entropies for the second subset of the one or more common attributes to an entropy threshold measure; and

in response to determining that the first object and the second object do not represent different entities, merging the first object and the second object in the fact repository and deleting in the merged object the one or more common attributes and values corresponding to the one or more common attributes for one of the first object and the second object.

10. A computer-implemented method of determining if a first object and a second object represent different entities, the method comprising:

identifying one or more common attributes between the first object and the second object, wherein the first object and the second object are included in a fact repository located on one or more computer systems;

determining an entropy for each of the one or more common attributes;

identifying a first subset of the one or more common attributes whose respective values are equivalent;

identifying a second subset of the one or more common attributes whose respective values are nonequivalent;

determining whether the first object and the second object represent different entities by comparing a difference of a sum of entropies for the first subset of the one or more common attributes and a sum of entropies for the second subset of the one or more common attributes to an entropy threshold measure; and

in response to determining that the first object and the second object do not represent different entities, merging the first object and the second object in the fact repository and deleting in the merged object the one or more common attributes and values corresponding to the one or more common attributes for one of the first object.

11. The method of claim 10, wherein identifying the second subset of the one or more common attributes whose respective values are nonequivalent comprises calculating a match measure indicating that the values are nonequivalent.

12. The method of claim 10, wherein the respective entropy comprises a respective numeric value measuring a respective amount of information carried by the attribute.

13. The method of claim 10, wherein identifying the first subset of the one or more common attributes whose respective values are equivalent comprises determining whether the respective values of a respective attribute in the one or more common attributes are the same.

14. The method of claim 12, wherein the respective numeric value comprises a sum, over all possible values associated with the attribute, of a product of a probability of each value and the log of the probability.

15. A system for determining if a first object and a second object represent a same entity, the system comprising:

a processor for executing programs; and

a subsystem executable by the processor, the subsystem including;

instructions for identifying one or more common attributes between the first object and the second object wherein the first object and the second object are included in a fact repository located on one or more computer systems;

instructions for determining an entropy for each of the one or more common attributes, wherein a respective entropy for a respective attribute in the one or more common attributes comprises a respective numeric value measuring a respective amount of information carried by the respective attribute;

instructions for identifying a subset of the one or more common attributes whose respective values are equivalent;

instructions for determining whether the first object and the second object represent the same entity by comparing a sum of entropies for the subset of the one or more common attributes to an entropy threshold measure; and

instructions for merging the first object and the second object in the fact repository in response to determining that the first object and the second object represent the same entity.

16. The system of claim 15, further comprising:

instructions for identifying a first subset of the one or more common attributes whose respective values are equivalent;

instructions for identifying a second subset of the one or more common attributes whose respective values are nonequivalent;

instructions for determining whether the first object and the second object represent different entities by comparing a difference of a sum of entropies for the first subset of the one or more common attributes and a sum of entropies for the second subset of the one or more common attributes to an entropy threshold measure; and

instructions for merging the first object and the second object in the fact repository and deleting in the merged object the one or more common attributes and values corresponding to the one or more common attributes for one of the first object and the second object in response to determining that the first object and the second object do not represent different entities.

17. A computer program product for use in conjunction with a computer system, the computer program product comprising a non-transitory computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism including:

instructions for identifying one or more common attributes between the first object and the second object, wherein the first object and the second object are included in a fact repository located on one or more computer systems;

instructions for determining an entropy for each of the one or more common attributes, wherein a respective entropy for a respective attribute in the one or more common attributes comprises a respective numeric value measuring a respective amount of information carried by the respective attribute;

instructions for identifying a subset of the one or more common attributes whose respective values are equivalent;

instructions for determining whether the first object and the second object represent a same entity by comparing a sum of entropies for the subset of the one or more common attributes to an entropy threshold measure; and

instructions for merging the first object and the second object in the fact repository in response to determining that the first object and the second object represent the same entity.

18. The computer program product of claim 17, further comprising:

instructions for identifying a first subset of the one or more common attributes whose respective values are equivalent;

instructions for identifying a second subset of the one or more common attributes whose respective values are nonequivalent;

instructions for determining whether the first object and the second object represent different entities by comparing a difference of a sum of entropies for the first subset of the one or more common attributes and a sum of entropies for the second subset of the one or more common attributes to an entropy threshold measure; and

instructions for merging the first object and the second object in the fact repository and deleting in the merged object the one or more common attributes and values corresponding to the one or more common attributes for one of the first object and the second object one of the first object and the second object in response to determining that the first object and the second object do not represent different entities.