Identifying central entities

• US 9,009,192 B1
• Filed: 06/03/2011
• Issued: 04/14/2015
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Shmiel, Tomer, Bar-Yossef, Ziv, Ofek, Eran, Matias, Yossi, Sobol, Alexander, Pilpel, Haran, Barkai, Eldad
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): GMAHL, NAVNEET K
• Application Number:
  US13/153,352
• Time in Patent Office: 1,411 Days
• Field of Search: 707748-750, 707735-738, 707/774, 707/754
• US Class Current: 707/774
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for identifying central entities. In one aspect, a method includes obtaining candidate entities for a first resource; filtering a first entity graph whose nodes represent different entities found in a plurality of resources to remove nodes that do not correspond to a candidate entity, wherein pairs of nodes in the filtered first entity graph that are connected by an edge correspond to pairs of candidate entities that are associated with the same resource; generating a second entity graph for the first resource from the filtered first entity graph, wherein the second entity graph does not include nodes from the filtered first entity graph that are not connected to other nodes in the filtered first graph; and identifying candidate entities that are represented by nodes in the second entity graph as being central entities for the first resource.

Claims

1. A method implemented by a data processing apparatus, the method comprising:

identifying multiple candidate entities that are associated with a first web resource, each candidate entity being a word or a phrase;

obtaining a first entity graph representing relationships between entities associated with resources in a collection of resources, wherein the first entity graph includes multiple nodes, each node representing a different entity associated with a respective resource in the collection of resources, each entity being a word or a phrase, wherein the first entity graph includes edges connecting pairs of nodes, and wherein each of the edges represents that two nodes connected by an edge represent two entities that are frequently associated with a same resource in the collection of resources;

filtering the first entity graph to remove nodes that do not represent any of the candidate entities associated with the first web resource;

generating, from the filtered first entity graph, a second entity graph for the first resource, including removing nodes from the filtered first entity graph that are not connected by an edge to at least one other node in the filtered first entity graph;

identifying candidate entities that are represented by respective nodes in the second entity graph as being central entities for the first resource;

generating respective search queries for each of the identified central entities;

obtaining search results responsive to the search queries from a search engine;

selecting a web resource referenced by a particular search result of the obtained search results as relevant additional content for the first web resource; and

associating the relevant additional content with the first web resource for presentation to a user requesting content from the first web resource.

2. The method of claim 1, wherein each edge in the first entity graph represents that two nodes connected by an edge have a computed probability that respective entities associated with the two nodes would be associated with a same resource more frequently than two entities that are independent of each other.

3. The method of claim 2, further comprising removing nodes from the second entity graph that do not have outgoing edges.

4. The method of claim 1, wherein each edge in the first entity graph and the second entity graph is weighted, and wherein a weight of an edge between a particular pair of nodes is based on a measure of relatedness of the pair of entities represented by the nodes.

5. The method of claim 4, wherein the measure of relatedness is determined using a pointwise mutual information measure that determines a relatedness of a first and second entity based on how often the first entity and the second entity are associated with resources in a collection of resources and how often the first entity and the second entity are associated with a same resource in the collection of resources.

6. The method of claim 1, wherein selecting a web resource referenced by a particular search result of the obtained search results as relevant additional content for the first web resource comprises:

generating a first score for each of one or more of the identified central entities based at least in part on weights of outgoing edges of respective nodes corresponding to the identified central entities;

determining that the particular search result was identified as being responsive to a search query generated for a central entity having a highest first score among the one or more identified central entities; and

selecting a web resource referenced by the particular search result.

7. The method of claim 6, wherein the first score for the particular identified central entity is based at least in part on a count of a number of times the identified central entity appears in a query log of queries to a search engine.

8. The method of claim 6, wherein the first score for the particular identified central entity is based at least in part on a frequency of occurrence of the identified central entity in the first resource.

9. The method of claim 6, wherein the first score for the particular identified central entity is based at least in part on a frequency of occurrence of the identified central entity in the collection of resources used to generate the first entity graph.

10. The method of claim 1, further comprising:

receiving an indication that a user has requested content from the first web resource;

obtaining the relevant additional content associated with the first web resource; and

providing the relevant additional content for presentation to the user along with content from the first web resource.

11. The method of claim 1, wherein identifying multiple candidate entities that are associated with a first web resource comprises identifying entities occurring in the resource, entities occurring in metadata associated with the resource, or entities occurring in a title or a URL of the resource.

12. A computer-readable storage device having stored thereon instructions, which, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

identifying multiple candidate entities that are associated with a first web resource, each candidate entity being a word or a phrase;

obtaining a first entity graph representing relationships between entities associated with resources in a collection of resources, wherein the first entity graph includes multiple nodes, each node representing a different entity associated with a respective resource in the collection of resources, each entity being a word or a phrase, wherein the first entity graph includes edges connecting pairs of nodes, and wherein each of the edges represents that two nodes connected by an edge represent two entities that are frequently associated with a same resource in the collection of resources;

filtering the first entity graph to remove nodes that do not represent any of the candidate entities associated with the first web resource;

generating, from the filtered first entity graph, a second entity graph for the first resource, including removing nodes from the filtered first entity graph that are not connected by an edge to at least one other node in the filtered first entity graph;

identifying candidate entities that are represented by respective nodes in the second entity graph as being central entities for the first resource;

generating respective search queries for each of the identified central entities;

obtaining search results responsive to the search queries from a search engine;

selecting a web resource referenced by a particular search result of the obtained search results as relevant additional content for the first web resource; and

associating the relevant additional content with the first web resource for presentation to a user requesting content from the first web resource.

13. The computer-readable storage device of claim 12, wherein each edge in the first entity graph represents that two nodes connected by an edge have a computed probability that respective entities associated with the two nodes would be associated with a same resource more frequently than two entities that are independent of each other.

14. The computer-readable storage device of claim 13, the operations further comprising removing nodes from the second entity graph that do not have outgoing edges.

15. The computer-readable storage device of claim 12, wherein each edge in the first entity graph and the second entity graph is weighted, and wherein a weight of an edge between a particular pair of nodes is based on a measure of relatedness of the pair of entities represented by the nodes.

16. The computer-readable storage device of claim 15, wherein the measure of relatedness is determined using a pointwise mutual information measure that determines a relatedness of a first and second entity based on how often the first entity and the second entity are associated with resources in a collection of resources and how often the first entity and the second entity are associated with a same resource in the collection of resources.

17. The computer-readable storage device of claim 12, wherein selecting a web resource referenced by a particular search result of the obtained search results as relevant additional content for the first web resource comprises:

generating a first score for each of one or more of the identified central entities based at least in part on weights of outgoing edges of respective nodes corresponding to the identified central entities;

determining that the particular search result was identified as being responsive to a search query generated for a central entity having a highest first score among the one or more identified central entities; and

selecting a web resource referenced by the particular search result.

18. The computer-readable storage device of claim 17, wherein the first score for the particular identified central entity is based at least in part on a count of a number of times the identified central entity appears in a query log of queries to a search engine.

19. The computer-readable storage device of claim 17, wherein the first score for the particular identified central entity is based at least in part on a frequency of occurrence of the identified central entity in the first resource.

20. The computer-readable storage device of claim 17, wherein the first score for the particular identified central entity is based at least in part on a frequency of occurrence of the identified central entity in the collection of resources used to generate the first entity graph.

21. The computer-readable storage device of claim 12, the operations further comprising:

receiving an indication that a user has requested content from the first web resource;

obtaining the relevant additional content associated with the first web resource; and

providing the relevant additional content for presentation to the user along with content from the first web resource.

22. The computer-readable storage device of claim 12, wherein identifying multiple candidate entities that are associated with a first web resource comprises identifying entities occurring in the resource, entities occurring in metadata associated with the resource, or entities occurring in a title or a URL of the resource.

23. A system comprising:

one or more data processing apparatus; and

a computer-readable storage device having stored thereon instructions that, when executed by the one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising;

identifying multiple candidate entities that are associated with a first web resource, each candidate entity being a word or a phrase;

obtaining a first entity graph representing relationships between entities associated with resources in a collection of resources, wherein the first entity graph includes multiple nodes, each node representing a different entity associated with a respective resource in a the collection of resources, each entity being a word or a phrase, wherein the first entity graph includes edges connecting pairs of nodes, and wherein each of the edges represents that two nodes connected by an edge represent two entities that are frequently associated with a same resource in the collection of resources;

filtering the first entity graph to remove nodes that do not represent any of the candidate entities associated with the first web resource;

generating, from the filtered first entity graph, a second entity graph for the first resource, including removing nodes from the filtered first entity graph that are not connected by an edge to at least one other node in the filtered first entity graph;

identifying candidate entities that are represented by respective nodes in the second entity graph as being central entities for the first resource;

generating respective search queries for each of the identified central entities;

obtaining search results responsive to the search queries from a search engine;

selecting a web resource referenced by a particular search result of the obtained search results as relevant additional content for the first web resource; and

associating the relevant additional content with the first web resource for presentation to a user requesting content from the first web resource.

24. The system of claim 23, wherein each edge in the first entity graph represents that two nodes connected by an edge have a computed probability that respective entities associated with the two nodes would be associated with a same resource more frequently than two entities that are independent of each other.

25. The system of claim 24, the operations further comprising removing nodes from the second entity graph that do not have outgoing edges.

26. The system of claim 23, wherein each edge in the first entity graph and the second entity graph is weighted, and wherein a weight of an edge between a particular pair of nodes is based on a measure of relatedness of the pair of entities represented by the nodes.

27. The system of claim 26, wherein the measure of relatedness is determined using a pointwise mutual information measure that determines a relatedness of a first and second entity based on how often the first entity and the second entity are associated with resources in a collection of resources and how often the first entity and the second entity are associated with a same resource in the collection of resources.

28. The system of claim 23, wherein selecting a web resource referenced by a particular search result of the obtained search results as relevant additional content for the first web resource comprises:

generating a first score for each of one or more of the identified central entities based at least in part on weights of outgoing edges of respective nodes corresponding to the identified central entities;

determining that the particular search result was identified as being responsive to a search query generated for a central entity having a highest first score among the one or more identified central entities; and

selecting a web resource referenced by the particular search result.

29. The system of claim 28, wherein the first score for the particular identified central entity is based at least in part on a count of a number of times the identified central entity appears in a query log of queries to a search engine.

30. The system of claim 28, wherein the first score for the particular identified central entity is based at least in part on a frequency of occurrence of the identified central entity in the first resource.

31. The system of claim 28, wherein the first score for the particular identified central entity is based at least in part on a frequency of occurrence of the identified central entity in the collection of resources used to generate the first entity graph.

32. The system of claim 23, the operations further comprising:

receiving an indication that a user has requested content from the first web resource;

obtaining the relevant the additional content associated with the first web resource; and

providing the relevant additional content for presentation to the user along with content from the first web resource.

33. The system of claim 23, wherein identifying multiple candidate entities that are associated with a first web resource comprises identifying entities occurring in the resource, entities occurring in metadata associated with the resource, or entities occurring in a title or a URL of the resource.