Automatic definition of entity collections

• US 9,454,599 B2
• Filed: 02/21/2014
• Issued: 09/27/2016
• Est. Priority Date: 10/09/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Golden, Keith, Hutchinson, Ben, Behal, Amit, Marks, Alexander Oliver, Zhang, Faen, Gao, Yuan, Wu, Fei
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US14/186,320
• Publication Number:
  US 20150100568A1
• Time in Patent Office: 949 Days
• Field of Search: 707/722
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3328 using graphical result space presentation or visualisation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A system for automatically generating entity collections comprises a data graph including entities connected by edges and instructions that cause the computer system to determine a set of entities from the data graph and to determine a set of constraints that has a quantity of constraints. A constraint in the set represents a path in the data graph shared by at least two of the entities in the set of entities. The instructions also cause the computer system to generate candidate collection definitions from combinations of the constraints, where each candidate collection definition identifies at least one constraint and no more than the quantity of constraints. The instructions also cause the computer system to determine an information gain for at least some of the candidate collection definitions, and store at least one candidate collection definition that has an information gain that meets a threshold as a candidate collection.

Claims

1. A computer system comprising:

at least one processor; and

one or more memories storing;

a knowledge base including entities connected by edges, wherein the edges represent at least thousands of factual relationships that may link two of the entities, and

instructions that, when executed by the at least one processor, cause the computer system to;

determine a first set of entities from the knowledge base,

determine a second set of constraints, the second set including a quantity of constraints, wherein a constraint in the second set identifies a constraint type and identifies a path of at least one edge in the knowledge base that is shared by at least two of the entities in the first set,

generate candidate collection definitions from combinations of the constraints in the second set, where each candidate collection definition identifies one or more constraints from the second set in conjunctive normal form,

prune the candidate collection definitions by discarding candidate collection definitions having an information gain that fails to meet a threshold, and

store at least one of the candidate collection definitions as a candidate collection in the one or more memories, the candidate collection having an information gain that meets the threshold, wherein the candidate collection definition is used to determine entities in the knowledge base belonging to the candidate collection.

2. The system of claim 1, wherein determining the first set of entities includes:

selecting a category from a crowd-sourced document corpus; and

determining entities identified by the category.

3. The system of claim 1, wherein determining the first set of entities includes:

identifying a popular query from search records;

converting the popular query to at least one semantic query; and

executing the at least one semantic query against the knowledge base to obtain a query result, wherein the first set of entities is the query result from the knowledge base.

4. The system of claim 3, wherein converting the popular query to at least one semantic query includes:

converting the popular query to a plurality of semantic queries;

running each of the plurality of semantic queries against the knowledge base; and

determining a plurality of sets of entities, a set of the plurality of sets representing entities responsive to one of the semantic queries.

5. The system of claim 1, wherein the instructions further include instructions that, when executed by the at least one processor, cause the computer system to:

generate a collection name for the candidate collection definition based on properties from the knowledge base associated with the constraints of the candidate collection definition.

6. The system of claim 5, wherein generating the collection name includes:

for each constraint associated with the candidate collection definition;

when the constraint identifies a relationship and an object entity, determining a name for the object entity and pluralizing the name, and

when the constraint identifies a relationship without an object entity, determining a name for the relationship; and

generating the collection name from a combination of the determined names for the constraints associated with the candidate collection definition.

7. The system of claim 1, wherein determining the second set of constraints includes:

generating a correlation score for respective constraints; and

using the correlation scores to select the quantity of constraints.

8. The system of claim 1, wherein the instructions further include instructions that, when executed by the at least one processor, cause the computer system to:

determine that a first candidate collection definition and a second candidate collection definition are compatible; and

merge the first candidate collection definition and the second candidate collection definition into a third candidate collection definition responsive to the determining.

9. The system of claim 8, wherein determining that the first candidate collection definition and the second candidate collection definition are compatible includes:

determining that a constraint for the first candidate collection definition is equivalent with a constraint for the second candidate collection definition; and

generating a condition for the third candidate collection definition that represents a union of the constraint for the first candidate collection definition and the constraint for the second candidate collection definition.

10. The system of claim 9, wherein the one or more memories further stores a table indicating relationship equivalencies and wherein the instructions further include instructions that cause the computer system to:

determine that the constraint for the first candidate is a relationship in the table for a particular equivalency;

convert the constraint for the first candidate to a first union that includes the equivalents for the constraint;

determine that the constraint for the second candidate is a second relationship in the table for the particular equivalency;

convert the constraint for the second candidate to a second union that includes the equivalents for the constraint; and

determine that the first union and the second union are identical,

wherein the condition for the third candidate represents the first union.

11. The system of claim 9, wherein the one or more memories further store a table indicating source constraints for a target constraint and wherein the instructions further include instructions that cause the computer system to:

determine that the constraint for the first candidate is a source constraint for the target constraint;

convert the constraint for the first candidate to the target constraint;

determine that the constraint for the second candidate is a source constraint for the target constraint;

convert the constraint for the second candidate to the target constraint; and

determine that the converted constraints are identical,

wherein the condition for the third candidate represents the target constraint.

12. The system of claim 1, the instructions further include instructions that, when executed by the at least one processor, cause the computer system to:

score the candidate collection based on search records; and

publish the candidate collection definition when the score meets a score threshold.

13. The system of claim 12, wherein scoring the candidate collection includes:

generating queries from the candidate collection;

inspecting the search records for popularity indicators for the generated queries; and

using the popularity indicators to score the candidate collection.

14. The system of claim 12, wherein publishing the candidate collection occurs subsequent to curation of a collection name.

15. The system of claim 1, wherein using the candidate collection to determine entities in the knowledge base belonging to the candidate collection includes:

determining, responsive to receiving a query that corresponds to the at least one collection definition, first entities in the knowledge base that meet the at least one constraint in the collection definition of the at least one collection; and

providing information about the first entities as a response to the query.

16. A method comprising:

determining, using at least one processor, a first set of entities from a knowledge base of entities connected by edges, wherein the edges represent at least thousands of factual relationships that may link two of the entities;

determining a plurality of constraints, each constraint identifying a constraint type and identifying a target node and a path of at least one edge leading to the target node from at least two of the entities in the first set;

generating, using the at least one processor, a correlation score for each of the plurality of constraints;

using the correlation scores to select a quantity of constraints for a set of constraints;

generating, using the at least one processor, candidate collection definitions from combinations of the set of constraints, where each candidate collection definition identifies one or more constraints from the set of constraints in conjunctive normal;

pruning the candidate collection definitions by discarding candidate collection definitions having an information gain that fails to meet a threshold; and

storing at least one of the candidate collection definitions as a candidate collection in a memory, the candidate collection having an information gain that meets the threshold.

17. The method of claim 16, wherein determining the first set of entities includes:

selecting a category from a crowd-sourced document corpus; and

determining entities identified by the category.

18. The method of claim 16, wherein determining the first set of entities includes:

identifying a popular query from search records;

converting the popular query to a semantic query; and

executing the at least one semantic query against the knowledge base to obtain a query result, wherein the first set of entities is the query result from the knowledge base.

19. The method of claim 16, further comprising:

generating a collection name for the candidate collection definition based on properties from the knowledge base associated with the constraints of the candidate collection definition.

20. The method of claim 16, wherein the candidate collection is a first candidate collection and the method further comprises:

determining that the first candidate collection and a second candidate collection are compatible; and

merging the first candidate collection and the second candidate collection into a third candidate collection definition responsive to the determining.

21. The method of claim 16, further comprising:

scoring the candidate collection based on search records; and

using the score to prioritize the candidate collection for name curation.

22. A computer system comprising:

at least one processor; and

one or more memories storing;

a knowledge base including entities connected by edges, wherein the edges represent at least thousands of factual relationships that may link two of the entities,

candidate collection definitions, each collection definition including one or more constraints in conjunctive normal form, a constraint identifying a constraint type and identifying representing a path in the knowledge base, and

instructions that, when executed by the at least one processor, cause the computer system to;

generate a name for a first candidate collection definition of the candidate collection definitions based on properties of the paths identified by the constraints of the candidate collection definition, and

provide the name as a suggestion to a curator of the candidate collection definitions.

23. The system of claim 22, wherein generating the name includes:

for each constraint associated with the candidate collection definition;

when the constraint identifies a relationship and an object entity, determining a name for the object entity and pluralizing the name, and

when the constraint identifies a relationship without an object entity, determining a name for the relationship; and

generating the name from a combination of the determined names for the constraints associated with the candidate collection definition.

24. The system of claim 22, wherein the knowledge base includes a mediator for a relationship and generating the name for the first candidate collection definition includes:

determining that a constraint associated with the candidate collection definition includes the relationship with the mediator; and

using the mediator in generating the name.

25. The system of claim 22, wherein the instructions further include instructions that, when executed by the at least one processor, cause the computer system to:

generate the name when it is determined that the first candidate collection definition does not include a condition with disjunctive constraints.

26. The system of claim 22, wherein the instructions further include instructions that, when executed by the at least one processor, cause the computer system to:

generate at least two names based on the properties from the knowledge base; and

provide the at least two names as suggestions.