Providing search results based on sorted properties

• US 9,256,682 B1
• Filed: 12/05/2012
• Issued: 02/09/2016
• Est. Priority Date: 12/05/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Yiming, Gu, Zhenyu
• Primary Examiner(s): Bullock, Joshua
• Application Number:
  US13/706,187
• Time in Patent Office: 1,161 Days
• Field of Search: 707/706, 707/769
• US Class Current: 1/1
• 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:

identifying in a knowledge graph, using at least one processor, at least one entity reference and related entity references related to the at least one entity reference by respective properties, wherein each of the respective properties reflects a relationship between the at least one entity reference and the respective related entity references;

for each respective one of the related entity references, determining, using at least one processor, 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;

for each respective property, generating a property score, using at least one processor, based on a sum of two or more related entity scores associated with that respective property; and

generating, using at least one processor, 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, further comprising:

identifying, using at least one processor, at least one entity type in a knowledge graph associated with the at least one entity reference, wherein the property score for each respective property is based on at least one of the at least one entity type, wherein the data structure is associated with the respective entity type.

3. The method of claim 2, wherein the at least one entity type comprises a first entity type and a second entity type, and wherein the second entity type is a subtype of the first entity type sharing at least one property with the first entity type, and wherein generating a property score comprises aggregating, using at least one processor, the property scores for each property associated with the first entity type and the second entity type to generate an aggregated property score.

4. 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.

5. 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.

6. The method of claim 5, wherein causing to be presented search results 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.

7. 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.

8. A system comprising:

a data structure comprising a knowledge graph; and

one or more processors configured to perform operations comprising;

identifying in the knowledge graph at least one entity reference and related entity references related to the at least one entity reference by respective properties, wherein each of the respective properties reflects a relationship between the at least one entity reference and the respective related entity references;

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;

for each respective property, generating a property score based on a sum of two or more related entity scores associated with that respective property; 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.

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

identifying at least one entity type in a knowledge graph associated with the at least one entity reference, wherein the property score for each respective property is based on at least one of the at least one entity type, wherein the data structure is associated with the respective entity type.

10. The system of claim 9, wherein the at least one entity type comprises a first entity type and a second entity type, and wherein the second entity type is a subtype of the first entity type sharing at least one property with the first entity type, and wherein the one or more processors are further configured to perform generating a property score by performing operations comprising aggregating the property scores for each property associated with the first entity type and the second entity type to generate an aggregated property score.

11. The system of claim 8, wherein the related entity scores are based on a co-occurrence of the each entity reference and respective related entity reference in content, wherein the co-occurrence is correlated with a property included in the knowledge graph.

12. The system of claim 8, wherein the one or more processors are further configured to perform operations 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.

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

sorting the collection of information based on the property scores; and

causing to be presented the sorted collection of information.

14. The system of claim 8, wherein the one or more processors are further configured to perform operations comprising receiving a query, wherein identifying in the knowledge graph the at least one entity reference is based on the query.

15. A non-transitory computer-readable medium for using in providing search results, the computer-readable medium having computer program instructions recorded thereon for:

identifying in a knowledge graph, using at least one processor, at least one entity reference and related entity references related to the at least one entity reference by respective properties, wherein each of the respective properties reflects a relationship between the at least one entity reference and the respective related entity references;

for each respective one of the related entity references, determining, using at least one processor, 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;

for each respective property, generating a property score, using at least one processor, based on a sum of two or more related entity scores associated with that respective property; and

generating, using at least one processor, 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.

16. The non-transitory computer-readable medium of claim 15, the computer-readable medium having further instructions for:

identifying, using at least one processor, at least one entity type in a knowledge graph associated with the at least one entity reference, wherein the property score for each respective property is based on at least one of the at least one entity type, wherein the data structure is associated with the respective entity type.

17. The non-transitory computer-readable medium of claim 16, wherein the at least one entity type comprises a first entity type and a second entity type, and wherein the second entity type is a subtype of the first entity type sharing at least one property with the first entity type, and wherein generating a property score comprises aggregating, using at least one processor, the property scores for each property associated with the first entity type and the second entity type to generate an aggregated property score.

18. The non-transitory computer-readable medium of claim 15, 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.

19. The non-transitory computer-readable medium of claim 15, the computer-readable medium having further instructions for:

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.

20. The non-transitory computer-readable medium of claim 19, the computer-readable medium having further instructions for:

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.

21. The non-transitory computer-readable medium of claim 15, the computer-readable medium having further instructions for receiving a query, wherein identifying in the knowledge graph the at least one entity reference is based on the query.