Fact-based object merging

• US 7,966,291 B1
• Filed: 06/26/2007
• Issued: 06/21/2011
• Est. Priority Date: 06/26/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Petrovic, Nemanja, Shamsi, Farhan, Kehlenbeck, Alexander, Vespe, David
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Tran; Bao G
• Application Number:
  US11/768,877
• Time in Patent Office: 1,456 Days
• Field of Search: 707/7, 707/999.2, 707/999.002, 707/999.003, 707/641, 707/808, 709/224, 717/125, 717/131, 717/107, 345/629, 345/636
• US Class Current: 707/641
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A repository contains objects including facts about entities. Some objects might be associated with the same entity. An object merge engine identifies a set of merge candidate objects. A grouping module groups the merge candidate objects based on the values of facts included in the objects. An object comparison module compares pairs of objects in each group to identify evidence for and/or against merging the pair. Evidence for merging the pair exists if, e.g., the objects have a type in common or share an uncommon fact. Evidence against merging the pair exists if, e.g., the objects have differing singleton attributes. A graph generation module generates graphs describing the evidence for and/or against merging the pair. A merging module analyzes the graphs and merges objects associated with the same entity. The merged objects are stored in the repository.

Claims

1. A computer-implemented method of merging objects stored in a memory and associated with a same entity, comprising:

identifying a plurality of merge candidate objects, wherein each merge candidate object is created using facts extracted from one or more electronic documents, each fact comprises an attribute and a value, each merge candidate object comprises one or more facts describing an entity with which the object is associated, each merge candidate object includes at least one fact with a same attribute, and each merge candidate object is distinct from the one or more electronic documents and the entity associated with the object;

grouping the plurality of merge candidate objects in accordance with values corresponding to the same attribute in the at least one fact, the grouping including assigning a respective merge candidate object to a respective group of a plurality of groups, the respective group corresponding to the value of the at least one fact with the same attribute in the respective merge candidate object;

identifying similarities between objects in each group, the identifying including computing a similarity value that indicates an amount of similarity between a pair of objects in the group;

generating one or more graphs describing identified similarities among the objects in all of the groups;

analyzing the one or more graphs describing the similarities among the objects to identify two or more objects associated with the same entity;

merging the two or more objects associated with the same entity to produce a merged object that includes facts of the two or more objects associated with the same entity; and

storing the merged object in a repository in the memory.

2. The method of claim 1, wherein the merge candidate objects are stored in the repository, and wherein each merge candidate object includes one or more facts extracted from an electronic document stored by a document host on a network.

3. The method of claim 1, wherein the at least one fact having the same attribute includes a name fact having a value including a name of the entity with which the object is associated and wherein grouping the plurality of merge candidate objects comprises:

identifying names in the name facts of the plurality of merge candidate objects;

creating a group for each distinct identified name; and

assigning each merge candidate object to a group corresponding to the name in the name fact included in the object, wherein an object including a plurality of distinct names is assigned to a plurality of groups.

4. The method of claim 1, wherein identifying similarities between objects in each group comprises:

comparing the pair of objects in the group to identify evidence that the objects in the pair are associated with the same entity;

comparing the pair of objects in the group to identify evidence that the objects in the pair are not associated with the same entity; and

computing the similarity value responsive to results of the comparisons, the similarity value indicating the amount of similarity between the objects.

5. The method of claim 4, wherein comparing the pair of objects to identify evidence that the objects are associated with the same entity comprises one or more determinations from a group consisting of:

determining whether both objects of the pair include a same type fact value, a respective type fact value indicating a respective type of a respective associated entity;

determining whether a term frequency/inverse document frequency (TF/IDF) metric calculated in accordance with text values of facts included in the objects of the pair exceeds a specified TF/IDF threshold;

determining whether both objects of the pair include facts extracted from a same electronic document stored by a document host on a network;

determining whether a web link graph distance for electronic documents from which the facts of the objects were extracted is less than a web link graph distance threshold; and

determining whether both objects of the pair include an uncommon fact.

6. The method of claim 4, wherein comparing the pair of objects to identify evidence that the objects are associated with the same entity comprises:

identifying an attribute of a fact included in each of the pair of objects and in a plurality of other objects stored in a repository;

identifying values of the same attribute included in a plurality of objects in the group;

computing a normal distribution of the identified values for the same attribute, the normal distribution including a mean; and

determining whether each object in the pair includes a same value for the same attribute, the same value being within a specified distance from the mean of the normal distribution.

7. The method of claim 4, wherein comparing the pair of objects to identify evidence that the objects are not associated with the same entity comprises one or more determinations from a group consisting of:

determining whether objects of the pair contain different values for a singleton attribute, wherein a singleton attribute can contain only one value for a given entity;

determining whether both objects of the pair were added to a repository by a same agent; and

determining whether the objects of the pair contain mutually exclusive type fact values, wherein a respective type fact value represents a respective type of an entity associated with the respective object.

8. The method of claim 1, wherein generating one or more graphs describing the similarities among the objects of all of the groups comprises:

generating a graph comprising a pair of nodes representing a pair of merge candidate objects and an edge between the pair of nodes, the edge having a weight representing the similarity value for the pair of objects.

9. The method of claim 8, wherein merging the two or more objects associated with the same entity to produce a merged object comprises:

performing hierarchical agglomerative clustering of the graph.

10. The method of claim 1, wherein identifying similarities comprises:

comparing a pair of objects in the group to determine whether a first object of the pair includes a subset of facts included in a second object of the pair.

11. The method of claim 10, wherein the first object includes a subset of the facts included in the second object and wherein generating one or more graphs describing the identified similarities among the objects of all of the groups comprises:

generating a directed graph comprising a pair of nodes representing the pair of objects and a directed edge between the pair of nodes, the direction of the edge indicating that the first object includes a subset of the facts included in the second object.

12. The method of claim 11, wherein the merging comprises:

analyzing the directed graph to determine whether the node representing the second object is a graph sink and whether the node representing the first object is connected to only one graph sink; and

responsive to a positive determination that the node representing the second object is a graph sink and the node representing the first object is connected to only one graph sink, merging the first object into the second object.

13. A computer system for merging objects associated with a same entity, the computer system comprising:

a grouping module for identifying a plurality of merge candidate objects, wherein each merge candidate object is created using facts extracted from one or more electronic documents, each fact comprises an attribute and a value, each merge candidate object comprises one or more facts describing an entity with which the object is associated, each merge candidate object includes at least one fact with a same attribute, and each merge candidate object is distinct from the one or more electronic documents and the entity associated with the object, and for grouping the plurality of merge candidate objects in accordance with values corresponding to the same attribute in the at least one fact, the grouping including assigning a respective merge candidate object to a respective group of a plurality of groups, the respective group corresponding to the value of the at least one fact with the same attribute in the respective merge candidate object;

an object comparison module for identifying similarities between objects in each group, the identifying including computing a similarity value that indicates an amount of similarity between a pair of objects in the group;

a graph generation module for generating one or more graphs describing identified similarities among the objects of all of the groups; and

a merging module for analyzing the one or more graphs describing the similarities among the objects to identify two or more objects associated with the same entity, merging the two or more objects associated with the same entity to produce a merged object that includes facts of the two or more objects associated with the same entity, and storing the merged object in a repository.

14. The computer system of claim 13, wherein the object comparison module is further adapted to:

compare the pair of objects in the group to identify evidence that the objects in the pair are associated with the same entity;

compare the pair of objects in the group to identify evidence that the objects in the pair are not associated with the same entity; and

compute the similarity value responsive to results of the comparisons, the similarity value indicating the amount of similarity between the objects.

15. The computer system of claim 14, wherein comparing the pair of objects to identify evidence that the objects are associated with the same entity comprises one or more determinations from a group consisting of:

determining whether both objects of the pair include a same type fact value, a respective type fact value indicating a respective type of a respective associated entity;

determining whether a term frequency/inverse document frequency (TF/IDF) metric calculated in accordance with text values of facts included in the objects of the pair exceeds a specified TF/IDF threshold;

determining whether both objects of the pair include facts extracted from a same electronic document stored by a document host on a network;

determining whether a web link graph distance for electronic documents from which the facts of the objects were extracted is less than a web link graph distance threshold; and

determining whether both objects of the pair include an uncommon fact.

16. The computer system of claim 14, wherein comparing the pair of objects to identify evidence that the objects are not associated with the same entity comprises one or more determinations from a group consisting of:

determining whether objects of the pair contain different values for a singleton attribute, wherein a singleton attribute can only contain one value for a given entity;

determining whether both objects of the pair were added to a repository by a same agent; and

determining whether the objects of the pair contain mutually exclusive type fact values, wherein a respective type fact value represents a respective type of an entity associated with the respective object.

17. The computer system of claim 13, wherein the graph generation module generates a graph comprising a pair of nodes representing a pair of merge candidate objects and an edge between the pair of nodes, the edge having a weight representing the similarity value for the pair of objects.

18. The computer system of claim 17, wherein the merging module is adapted to perform hierarchical agglomerative clustering of the graph.

19. The computer system of claim 13, wherein the object comparison module compares a pair of objects in the group to determine whether a first object of the pair includes a subset of facts included in a second object of the pair.

20. The computer system of claim 19, wherein the first object includes a subset of the facts included in the second object and wherein the graph generation module generates a directed graph comprising a pair of nodes representing the pair of objects and a directed edge between the pair of nodes, the direction of the edge indicating that the first object includes a subset of the facts included in the second object.

21. The computer system of claim 20, wherein the merging module is further adapted to:

analyze the directed graph to determine whether the node representing the second object is a graph sink and whether the node representing the first object is connected to only one graph sink; and

responsive to a positive determination that the node representing the second object is a graph sink and the node representing the first object is connected to only one graph sink, merge the first object into the second object.

22. A non-transitory computer-readable storage medium storing one or more instructions for execution by one or more processors, the one or more instructions comprising:

a grouping module for identifying a plurality of merge candidate objects, wherein each merge candidate object is created using facts extracted from one or more electronic documents, each fact comprises an attribute and a value, each merge candidate object comprises one or more facts describing an entity with which the object is associated, each merge candidate object includes at least one fact with a same attribute, and each merge candidate object is distinct from the one or more electronic documents and the entity associated with the object, and for grouping the plurality of merge candidate objects in accordance with values corresponding to the same attribute in the at least one fact, the grouping including assigning a respective merge candidate object to a respective group of a plurality of groups, the respective group corresponding to the value of the at least one fact with the same attribute in the respective merge candidate object;

an object comparison module for identifying similarities between objects in each group, the identifying including computing a similarity value that indicates an amount of similarity between a pair of objects in the group;

a graph generation module for generating one or more graphs describing identified similarities among the objects in all of the groups; and

a merging module for analyzing the one or more graphs describing the similarities among the objects to identify two or more objects associated with the same entity, merging the two or more objects associated with the same entity to produce a merged object that includes facts of the two or more objects associated with the same entity, and storing the merged object in a repository.

23. The computer readable storage medium of claim 22, wherein the object comparison module is further adapted to:

compare the pair of objects in the group to identify evidence that the objects in the pair are associated with the same entity;

compare the pair of objects in the group to identify evidence that the objects in the pair are not associated with the same entity; and

compute the similarity value responsive to results of the comparisons, the similarity value indicating the amount of similarity between the objects.

24. The computer readable storage medium of claim 23, wherein comparing the pair of objects to identify evidence that the objects are associated with the same entity comprises one or more determinations from a group consisting of:

determining whether both objects of the pair include a same type fact value, a respective type fact value indicating a respective type of a respective associated entity;

determining whether a term frequency/inverse document frequency (TF/IDF) metric calculated in accordance with text values of facts included in the objects of the pair exceeds a specified TF/IDF threshold;

determining whether both objects of the pair include facts extracted from a same electronic document stored by a document host on a network;

determining whether a web link graph distance for electronic documents from which the facts of the objects were extracted is less than a web link graph distance threshold; and

determining whether both objects of the pair include an uncommon fact.

25. The computer readable storage medium of claim 23, wherein comparing the pair of objects to identify evidence that the objects are not associated with the same entity comprises one or more determinations from a group consisting of:

determining whether objects of the pair contain different values for a singleton attribute, wherein a singleton attribute can only contain one value for a given entity;

determining whether both objects of the pair were added to a repository by a same agent; and

determining whether the objects of the pair contain mutually exclusive type fact values, wherein a respective type fact value represents a respective type of an entity associated with the respective object.

26. The computer readable storage medium of claim 22, wherein the graph generation module generates a graph comprising a pair of nodes representing a pair of merge candidate objects and an edge between the pair of nodes, the edge having a weight representing the similarity value for the pair of objects.

27. The computer readable storage medium of claim 26, wherein the merging module is adapted to perform hierarchical agglomerative clustering of the graph.

28. The computer readable storage medium of claim 22, wherein the object comparison module compares a pair of objects in the group to determine whether a first object of the pair includes a subset of facts included in a second object of the pair.

29. The computer readable storage medium of claim 28, wherein the first object includes a subset of the facts included in the second object and wherein the graph generation module generates a directed graph comprising a pair of nodes representing the pair of objects and a directed edge between the pair of nodes, the direction of the edge indicating that the first object includes a subset of the facts included in the second object.

30. The computer readable storage medium of claim 29, wherein the merging module is further adapted to:

analyze the directed graph to determine whether the node representing the second object is a graph sink and whether the node representing the first object is connected to only one graph sink; and

responsive to a positive determination that the node representing the second object is a graph sink and the node representing the first object is connected to only one graph sink, merge the first object into the second object.