Generating insightful connections between graph entities

Patent metadata

Field	Value
Publication number	US-10713261-B2
Application number	US-201313801616-A
Country	US
Kind code	B2
Filing date	Mar 13, 2013
Priority date	Mar 13, 2013
Publication date	Jul 14, 2020
Grant date	Jul 14, 2020

Abstract

Implementations provide an enhanced search result to improve the user search experience. For example, the result may include insightful information relevant to the search query that was not specifically requested but that the user may find interesting, such as relationships shared between the two entities related to the query, a relationship between the two entities that does not commonly occur with another relationship shared by the entities, or strong secondary connections for an entity related to the query. In some implementations, insightful connections may also be unique facts for a particular entity. Unique facts may represent a superlative attribute of an entity such as, for example, the tallest actor, the oldest president, the most expensive stock, etc. Such shared relationships, rare relationships, and/or unique facts may be provided as part of the search results presented to the query requestor and may provide insight to the requestor about the entity.

First claim

What is claimed is:

1. A system comprising:
a data graph that links entities by relationships, each relationship having one of a plurality of labels;
an index for searching a document corpus; and
a query handling system that includes:
at least one processor, and
a memory storing instructions that, when executed by the at least one processor cause the query handling system to perform operations including:
receiving a query,
generating a search result for the query using the index, based on documents responsive to the query,
identifying a first entity from the data graph and a second entity from the data graph corresponding to the query,
identifying first-degree paths from the data graph for the first entity, a first-degree path including a relationship and a target entity,
identifying first-degree paths from the data graph for the second entity,
determining that at least one first-degree path for the first entity matches at least one first-degree path for the second entity, the at least one matched first-degree path being a matched connection, and
including information for the relationship label and the target entity from the matched connection in the search result.

2. The system of claim 1 , wherein the instructions further cause the query handling system to perform operations including:
determining that the query resulted from a selection of a representation of the second entity, the representation being part of a search result for a prior search, the prior search corresponding to the first entity.

3. The system of claim 1 , wherein the query handling system determines that a plurality of first-degree paths match, generating a plurality of matched connections, and the instructions further cause the query handling system to perform operations comprising:
sorting the matched connections by popularity; and
including information for a predetermined number of the sorted matched connections in the search result.

4. The system of claim 3 , wherein the instructions further cause the query handling system to perform operations comprising:
assigning each matched connection to a group; and
sorting the matched connections by popularity within group,
wherein including information for the predetermined number of matched connections includes selecting one of the groups for the including.

5. The system of claim 4 , wherein the group with a highest number of matched connections is selected.

6. The system of claim 4 , wherein the group with a highest number of popular matched connections is selected.

7. The system of claim 3 , wherein popularity for a particular matched connection is based on an amount of appearances in the document corpus of the target entity associated with the particular matched connection.

8. A system comprising:
a data graph that links entities by relationships; and
a query handling system that includes:
at least one processor, and
a memory storing instructions that, when executed by the at least one processor cause the query handling system to perform operations including:
generating a first-degree entity graph for a particular entity in the data graph, the first-degree entity graph having first-degree paths each comprising a first-degree relationship and a first-degree entity,
generating a second degree entity graph for the particular entity in the data graph, the second degree entity graph having second degree paths each comprising a first-second-degree relationship connecting to a first second-degree entity and a second second-degree relationship connecting the first second-degree entity to a second second-degree entity,
for a particular second second-degree entity in the second-degree paths:
assigning each second second-degree relationship to a group,
determining an amount of second second-degree relationships in each group,
determining that the amount meets a threshold, and
storing data relating to the particular entity, the second second-degree entity, and the group in a memory for later retrieval in response to queries,

for a particular first-degree entity in the first-degree paths:
identifying at least one matching path by identifying a second-degree entity in the second-degree paths that matches the particular first-degree entity,
determining whether the first second-degree relationship and the second second-degree relationship of the matching path are of the same type, and
storing data relating to the particular entity and the matching paths for later retrieval in response to queries when the first second-degree relationship and the second second-degree relationship are of the same type.

9. The system of claim 8 , further comprising:
an index for searching a document corpus,
wherein the query handling system provides a search result in response to queries, the search result including information from the index and information based on the stored data relating to the particular entity.

10. The system of claim 8 , wherein the memory further stores instructions that cause the query handling system to perform operations comprising:
receiving a query that relates to the particular entity;
retrieving the data; and
including information from the data in a query result responsive to the query.

11. The system of claim 8 , wherein the memory further stores instructions that cause the query handling system to perform operations comprising:
excluding commonly occurring entities and commonly occurring relationships from the first-degree entity graph and second-degree entity graph.

12. The system of claim 8 , wherein as part of assigning each second second-degree relationship to a group memory further stores instructions that cause the query handling system to perform operations comprising:
assigning each combination of first second-degree relationship and second second-degree relationship to a group.

Assignees

• Google Inc
• Google Llc

Inventors

• Huynh David Francois
• Li Guanghua
• Ding Chen
• Huang Yanlai
• Chai Ying
• Hu Liang
• Chen Jingxu

Classifications

• G06F16/3323 Primary

  using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection · CPC title

• G06F16/24575 Primary

  using context · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F16/24578

  using ranking · CPC title