Providing search results based on sorted properties

• US 9,875,320 B1
• Filed: 02/08/2016
• Issued: 01/23/2018
• Est. Priority Date: 12/05/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Li, Yiming, Gu, Zhenyu
• Primary Examiner(s): Bullock, Joshua
• Application Number:
  US15/018,831
• Time in Patent Office: 715 Days
• Field of Search: 707706, 707769
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

An entity may be related to multiple related entities by one or more properties, and the entity may also be associated with one or more entity types. A system for providing sorted results may include identifying the entity, related entities, and types. The system may also determine related entity scores for each respective related entity, relative to the entity. For each property, the related entity scores of the related entities related to the entity by that property are combined to generate a property score. The properties are then sorted based on their property scores. The sorting may occur for properties associated with an entity type, and sorted search results may be provided as output for one or more entity types of interest.

Claims

1. A computer-implemented method comprising the following operations performed via one or more processors:

identifying, in a knowledge graph, at least one entity reference and related entity references related to the at least one entity reference by respective properties;

for each respective one of the related entity references, determining a related entity score associated with a respective property that relates the at least one entity reference and the respective one of the related entity references;

identifying a first entity type and a second entity type associated with the at least one entity reference, wherein the second entity type is a subtype of the first entity type;

for each respective property, generating a property score based on related entity scores associated with that respective property, wherein generating a property score comprises aggregating the property scores for each property associated with the first entity type and the second entity type to generate an aggregated property score; and

generating and causing to be stored a data structure of sortable properties based on the generated property scores, wherein the data structure is usable to provide sorted search results in response to a query.

2. The method of claim 1, wherein the related entity scores are based on a co-occurrence of the at least one entity reference and respective related entity references in content, wherein the co-occurrence is correlated with a property included in the knowledge graph.

3. The method of claim 1, further comprising:

retrieving the data structure of sortable properties; and

causing to be presented, using at least one processor, a collection of information based on the retrieved data structure.

4. The method of claim 3, wherein causing to be presented the collection of information comprises:

sorting, using at least one processor, the collection of information based on the property scores; and

causing to be presented the sorted collection of information.

5. The method of claim 1, further comprising receiving a query, wherein identifying in the knowledge graph the at least one entity reference is based on the query.

6. A computer-implemented method comprising the following operations performed via one or more processors:

receiving a query that includes an entity reference and a given entity type reference, the given entity type reference identifying a given entity type of a plurality of entity types associated with the entity reference in a knowledge graph;

identifying a stored data structure of sortable properties associated with the entity reference, the stored data structure including;

first features assigned to a plurality of the properties and to the given entity type identified by the given entity type reference, the first features indicating the relative importance of each of the respective properties to the given entity type associated with the entity type reference, and

second features assigned to a plurality of the properties and to an additional entity type of the entity types associated with the entity reference, the second features indicating the relative importance of each of the respective properties to the additional entity type of the entity types associated with the entity type reference;

selecting the first features based on the first features being assigned in the stored data structure to the given entity type identified by the given entity type reference of the query; and

causing to be presented in response to the query, a collection of information that is related to the entity reference and that is sorted based on the selected first features.

7. The method of claim 6, wherein the first features are first property scores for the properties for the given entity type, and wherein the collection of information is sorted based on the first property scores.

8. The method of claim 7, wherein the second features are second property scores for the properties for the additional entity type.

9. The method of claim 8, further comprising:

receiving an additional query that includes the entity reference and an additional entity type reference, the additional entity type reference identifying the additional entity type;

selecting the second features based on the second features being assigned in the stored data structure to the additional entity type identified by the additional entity type reference of the additional query; and

causing to be presented in response to the additional query, an additional collection of information that is related to the entity reference and that is sorted based on the selected second features.

10. The method of claim 6, wherein the entity type and the additional entity type are both subtypes of a third entity type associated with the entity reference in the knowledge graph.

11. A system, comprising:

a data structure of sortable properties associated with an entity reference, the stored data structure including;

first features assigned to a plurality of the properties and to a given entity type of a plurality of entity types associated with the entity reference in a knowledge graph, the first features indicating the relative importance of each of the respective properties to the given entity type associated with the entity reference, and

second features assigned to a plurality of the properties and to an additional entity type of the entity types associated with the entity reference in the knowledge graph, the second features indicating the relative importance of each of the respective properties to the additional entity type of the entity types associated with the entity type reference;

one or more processors configured to perform operations comprising;

receiving a query that includes the entity reference and a given entity type reference, the given entity type reference identifying the given entity type;

selecting the first features based on the first features being assigned in the data structure to the given entity type identified by the given entity type reference of the query; and

causing to be presented in response to the query, a collection of information that is related to the entity reference and that is sorted based on the selected first features.

12. The system of claim 11, wherein the first features are first property scores for the properties for the given entity type, and wherein the collection of information is sorted based on the first property scores.

13. The system of claim 12, wherein the second features are second property scores for the properties for the additional entity type.

14. The system of claim 13, wherein the one or more processors are further configured to perform operations comprising:

receiving an additional query that includes the entity reference and an additional entity type reference, the additional entity type reference identifying the additional entity type;

selecting the second features based on the second features being assigned in the data structure to the additional entity type identified by the additional entity type reference of the additional query; and

causing to be presented in response to the additional query, an additional collection of information that is related to the entity reference and that is sorted based on the selected second features.

15. The system of claim 11, wherein the entity type and the additional entity type are both subtypes of a third entity type associated with the entity reference in the knowledge graph.