Discovering entity actions for an entity graph

• US 9,235,653 B2
• Filed: 06/26/2013
• Issued: 01/12/2016
• Est. Priority Date: 06/26/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Talmon, Haran, Walevski, Daniel, Frengov, Atanas, Sahin, Engin Cinar, Sun, Chen
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US13/927,606
• Publication Number:
  US 20150006501A1
• Time in Patent Office: 930 Days
• Field of Search: 707/708
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Systems and methods identify recent or ephemeral events involving entities that can be used to update a data graph or provide enhanced search results. For example, a computer-implemented method includes determining at least one search term for an entity in a data graph and determining a time period having an increase in queries for the at least one search term, the increase meeting a threshold. The method may include determining documents having dates associated with the time period, the documents being responsive to the at least one search term, and analyzing the documents to determine a subject, verb, object triple, where the search term corresponds to the subject or the object of the triple. The method may also include providing an update for the data graph based on the triple. The method may also include generating text describing the triple for inclusion in a search result for the search query.

Claims

1. A computer system comprising:

memory storing search records;

memory storing a graph-structured knowledge base that includes entities linked to other entities by relationships;

at least one processor; and

memory storing instructions that, when executed by the at least one processor, cause the computer system to perform operations comprising;

determining a search term associated with a first entity that is identified in a graph-based data store,

determining a time period having an amount of queries for the search term that meets a threshold,

selecting documents associated with the time period that are responsive to the search term,

analyzing the selected documents for an action co-occurring with the search term by,

for a particular document of the selected documents;

identifying verbs in content of the particular document, and

generating a triple for at least one verb of the identified verbs, the triple including a subject, the at least one verb, and an object, wherein either the subject or the object represents the search term, and wherein the action is derived from the triple,

determining a second entity associated with the action and the search term, the second entity corresponding to either the subject of the triple or the object of the triple not represented by the search term, and

providing the second entity, the action, and the first entity as an update for the graph-based data store.

2. The system of claim 1, wherein the entity is associated with a query and the memory further stores instructions that, when executed by the at least one processor, causes the computer system to:

generate text for the action and the first entity; and

include the text in a search result for the query.

3. The system of claim 2, wherein the text is first text and wherein the search result includes second text describing relationships for the entity from the graph-based data store.

4. The system of claim 1, wherein the threshold is higher than an average number of queries for a second time period occurring prior to the time period and a third time period occurring subsequent to the time period.

5. The system of claim 1, wherein deriving the action includes:

determining whether the at least one verb maps to a target action; and

selecting the target action as the action when the at least one verb maps to the target action.

6. The system of claim 1, wherein the second entity is not already identified in the graph-based data store.

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

automatically update the graph-based data store when the at least one verb maps to a target action.

8. A computer-implemented method comprising:

determining, by at least one processor, at least one search term for an entity in a data graph stored in memory that includes entities linked to other entities by relationships;

determining, by the at least one processor, a time period having an increase in queries for the at least one search term, the increase meeting a threshold;

determining documents having dates associated with the time period, the documents being responsive to the at least one search term;

analyzing the documents to determine an action appearing in a minimum number of the documents, where the action is represented by subject, verb, object triples where, for each triple the search term corresponds to the subject or the object of the triple and wherein the action is derived from the triple; and

providing an update for the data graph based on the triple.

9. The method of claim 8, wherein dates for the documents are within a temporal distance of the time period.

10. The method of claim 9, wherein the temporal distance is determined as a function of a size of the increase.

11. The method of claim 9, wherein the temporal distance is determined as a function of an amount of time that has elapsed time since the time period.

12. The method of claim 8, wherein analyzing a document of the documents includes:

identifying verbs in content of the document;

matching at least one verb of the identified verbs to the action, the action being a target action from a set of target actions; and

generating the triple using the target action as the verb.

13. The method of claim 12 further comprising:

automatically updating the data graph in response to the at least one verb mapping to the target action.

14. The method of claim 12, wherein target actions in the set of target actions correspond with respective relationships in the data graph.

15. The method of claim 8, wherein the analyzing results in a plurality of triples and the triple is in the plurality of triples, and determining the action includes:

clustering the triples in the plurality of triples into cluster groups based at least on a mapping of the verbs of the triples to actions;

determining whether at least one cluster group meets a threshold cluster score; and

providing the update when the at least one cluster group meets the threshold cluster score, wherein the at least one cluster group represents the action and the triple is a member of the at least one cluster group.

16. The method of claim 12, wherein the triple is selected based on centrality of the triple to the cluster group.

17. The method of claim 8, wherein the threshold is greater than an average frequency of queries that are associated with the at least one search term for time periods of similar length.

18. The method of claim 8, wherein the at least one search term includes a name of the entity appended with a form of a verb.

19. A computer-implemented method comprising:

determining, by at least one processor, at least one search term for an entity in a data graph that relates to a search query, the data graph including entities linked to other entities by relationships;

determining, by the at least one processor, a time period having an amount of queries that meets a threshold, the queries included in the amount being associated with the at least one search term;

determining documents having dates associated with the time period, the documents being responsive to the at least one search term;

analyzing the documents to determine an action appearing in a minimum number of the documents, where the action is represented by subject, verb, object triples where, for each triple the search term corresponds to the subject or the object of the triple and wherein the action is derived from the triple; and

generating text, by the at least one processor, describing the triple for inclusion in a search result for the search query.