OPTIMIZED GRAPH TRAVERSAL

• US 20180239751A1
• Filed: 02/22/2017
• Published: 08/23/2018
• Est. Priority Date: 02/22/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Durr, Christopher Jacob, Ayala, Hector Mauricio, Jain, Mayank
• Granted Patent: US 10,140,286 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G10L 15/08 Speech classification or search

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for optimized graph traversal are disclosed. In one aspect, a method includes the actions of receiving a given phrase that is input through a user interface by a digital component provider. The actions further include determining an entity that is being referred to by the given phrase. The actions further include identifying properties of the entity. The actions further include selecting a subset of the properties that were identified for the entity. The actions further include identifying additional phrases. The actions further include updating the user interface to present at least some of the additional phrases with programmatic controls that assign one or more of the additional phrase as distribution criteria for digital components of the digital component provider in response to activation of the programmatic controls.

Claims

1. A system comprising:

a front end server that is configured to receive a given phrase that is input through a user interface by a digital component provider;

a knowledge graph traverser that is configured to determine an entity that is being referred to by the given phrase, wherein the knowledge graph traverser performs the determination by accessing a knowledge graph comprising nodes that each uniquely identify different entities, and identifying a particular node that uniquely identifies the entity being referred to by the given phrase, wherein the nodes of the knowledge graph are connected by edges that represent relationships between connected nodes; and

a property selector that interacts with the graph traverser and is configured to;

identify properties of the entity by accessing other nodes that are connected to the particular node that identifies the entity;

access a search query history that includes previous search queries provided by users;

determine, from among the properties that were identified for the entity, one or more properties that occur in the previous search queries provided by the users at a greater frequency than other properties that were identified for the entity; and

based on characteristics of the digital component provider, select, from among the one or more properties that occur in the previous search queries provided by the users at the greater frequency than the other properties that were identified for the entity, a subset of the properties that were identified for the entity,

wherein the knowledge graph traverser is further configured to identify additional phrases by accessing the knowledge graph using the subset of properties that were identified for the entity, and

wherein the front-end server updates the user interface to present at least some of the additional phrases with programmatic controls that assign one or more of the additional phrase as distribution criteria for digital components of the digital component provider in response to activation of the programmatic controls.

2. The system of claim 1, comprising:

a knowledge graph filter that is configured to reduce a number of accesses to the knowledge graph by the knowledge graph traverser when identifying the additional phrases.

3. The system of claim 1, comprising:

a phrase selector that is configured to identify, from among the additional phrases, one or more phrases that have a higher performance characteristic than other phrases among the additional phrases, wherein the phrase selector performs the identification by accessing phrase action scores for the identified additional phrases, comparing the phrase action scores to each other, identifying one or more of the phrase action scores having highest values based on the comparison, and selecting the one or more additional phrases having the phrase action scores having the highest values.

4. The system of claim 1, wherein the property selector is further configured to:

select the subset of the properties associated with the entity using a selection model continuously trained using machine learning.

5. The system of claim 4, wherein the property selector is further configured to:

initially train the selection model using selection model training data comprising phrases associated with the previous search queries submitted by users, digital component selection data associated with the previous search queries, entities associated with the phrases, and properties associated with the entities.

6. The system of claim 1, wherein additional phrases identified by the knowledge graph traverser comprise a minimum spanning tree among the entity.

7. A computer-implemented method comprising:

receiving a given phrase that is input through a user interface by a digital component provider;

determining an entity that is being referred to by the given phrase by accessing a knowledge graph comprising nodes that each uniquely identify different entities, and identifying a particular node that uniquely identifies the entity being referred to by the given phrase, wherein the nodes of the knowledge graph are connected by edges that represent relationships between connected nodes;

identifying properties of the entity by accessing other nodes that are connected to the particular node that identifies the entity;

accessing a search query history that includes previous search queries provided by users;

determining, from among the properties that were identified for the entity, one or more properties that occur in the previous search queries provided by the users at a greater frequency than other properties that were identified for the entity;

based on characteristics of the digital component provider, selecting, from among the one or more properties that occur in the previous search queries provided by the users at the greater frequency than the other properties that were identified for the entity, a subset of the properties that were identified for the entity;

identifying additional phrases by accessing the knowledge graph using the subset of properties that were identified for the entity; and

updating the user interface to present at least some of the additional phrases with programmatic controls that assign one or more of the additional phrase as distribution criteria for digital components of the digital component provider in response to activation of the programmatic controls.

8. The method of claim 7, comprising:

reducing a number of accesses to the knowledge graph by the knowledge graph traverser when identifying the additional phrases.

9. The method of claim 7, comprising:

identifying, from among the additional phrases, one or more phrases that have a higher performance characteristic than other phrases among the additional phrases by accessing phrase action scores for the identified additional phrases, comparing the phrase action scores to each other, identifying one or more of the phrase action scores having highest values based on the comparison, and selecting the one or more additional phrases having the phrase action scores having the highest values.

10. The method of claim 7, comprising

selecting the subset of the properties associated with the entity using a selection model continuously trained using machine learning.

11. The method of claim 10, comprising:

initially training the selection model using selection model training data comprising phrases associated with the previous search queries submitted by users, digital component selection data associated with the previous search queries, entities associated with the phrases, and properties associated with the entities.

12. The method of claim 7, wherein additional identified phrases comprise a minimum spanning tree among the entity.

13. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving a given phrase that is input through a user interface by a digital component provider;

determining an entity that is being referred to by the given phrase by accessing a knowledge graph comprising nodes that each uniquely identify different entities, and identifying a particular node that uniquely identifies the entity being referred to by the given phrase, wherein the nodes of the knowledge graph are connected by edges that represent relationships between connected nodes;

identifying properties of the entity by accessing other nodes that are connected to the particular node that identifies the entity;

accessing a search query history that includes previous search queries provided by users;

determining, from among the properties that were identified for the entity, one or more properties that occur in the previous search queries provided by the users at a greater frequency than other properties that were identified for the entity;

based on characteristics of the digital component provider, selecting, from among the one or more properties that occur in the previous search queries provided by the users at the greater frequency than the other properties that were identified for the entity, a subset of the properties that were identified for the entity;

identifying additional phrases by accessing the knowledge graph using the subset of properties that were identified for the entity; and

updating the user interface to present at least some of the additional phrases with programmatic controls that assign one or more of the additional phrase as distribution criteria for digital components of the digital component provider in response to activation of the programmatic controls.

14. The medium of claim 13, wherein the operations further comprise:

reducing a number of accesses to the knowledge graph by the knowledge graph traverser when identifying the additional phrases.

15. The medium of claim 13, wherein the operations further comprise:

identifying, from among the additional phrases, one or more phrases that have a higher performance characteristic than other phrases among the additional phrases by accessing phrase action scores for the identified additional phrases, comparing the phrase action scores to each other, identifying one or more of the phrase action scores having highest values based on the comparison, and selecting the one or more additional phrases having the phrase action scores having the highest values.

16. The medium of claim 13, wherein the operations further comprise:

selecting the subset of the properties associated with the entity using a selection model continuously trained using machine learning.

17. The medium of claim 16, wherein the operations further comprise:

initially training the selection model using selection model training data comprising phrases associated with the previous search queries submitted by users, digital component selection data associated with the previous search queries, entities associated with the phrases, and properties associated with the entities.

18. The medium of claim 13, wherein additional identified phrases comprise a minimum spanning tree among the entity.