Meaning-based advertising and document relevance determination

• US 9,710,825 B1
• Filed: 09/14/2015
• Issued: 07/18/2017
• Est. Priority Date: 09/22/1999
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Weissman, Adam J., Elbaz, Gilad Israel
• Primary Examiner(s): Le, Uyen
• Application Number:
  US14/853,498
• Time in Patent Office: 673 Days
• Field of Search: None
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method for advertising on electronic data networks based upon semantic differentiation.

Claims

1. A computer-implemented method comprising:

receiving a query having a plurality of query terms;

obtaining a plurality of meanings associated with each of the plurality of query terms, including a first plurality of meanings associated with a first query term and a second plurality of meanings associated with a different second query term, wherein each meaning of the plurality of meanings is a sequence of one or more terms having a respective score corresponding to a likelihood of a query term having the meaning;

obtaining data representing a semantic space having a plurality of elements, each element being associated with a different respective meaning, and wherein each of the plurality of elements has a connection with at least one other element in the semantic space, wherein the connection between two elements indicates that the two elements have a similar meaning;

determining that a first meaning of the first plurality of meanings for the first query term has a connection in the semantic space with a second meaning of the second plurality of meanings for the second query term;

in response to determining that the first meaning has a connection in the semantic space with the second meaning, increasing respective scores associated with the first meaning, the second meaning, or both, an increase indicating a higher probability that a respective meaning relates to the query;

ranking the plurality of meanings according to the respective scores associated with the plurality of meanings;

selecting a highest-ranked meaning of the plurality of meanings;

identifying a first element in the semantic space having the highest-ranked meaning;

determining a plurality of additional elements in the semantic space that are each located within a threshold semantic distance of the first element;

identifying one or more advertisements associated, in the semantic space, with one or more of the additional elements that are located within the threshold semantic distance of the first element, wherein the one or more of the additional elements differ from the plurality of query terms; and

providing the identified one or more advertisements in response to receiving the query.

2. The method of claim 1, wherein the score associated with a particular meaning is higher if the particular meaning matches a query term rather than a stemmed or morphed variant of the query term.

3. The method of claim 1, wherein the score for a particular meaning is higher if the particular meaning has two or more terms that match two or more corresponding query terms.

4. The method of claim 1, wherein each meaning has an associated measure of commonness, and wherein more common meanings have a higher score than less common meanings.

5. The method of claim 1, further comprising comparing all of the first plurality of meanings to all of the second plurality of meanings to determine if any pair of meanings has a connection in the semantic space.

6. The method of claim 1, further comprising determining a semantic distance between the first element and a plurality of other elements including evaluating a sum of strengths of connections between the first element and the other element in the semantic space.

7. The method of claim 6, further comprising traversing multiple connections in the semantic space between the first element and each other element of the plurality of other elements, wherein the semantic distance between the first element and each other element is based on respective strengths of connections traversed between the first element and the other element.

8. The method of claim 7, wherein each connection in the semantic space has a direction of association, and wherein a first strength associated with traversing a connection in a direction opposite to its direction of association is higher than a second strength associated with traversing the connection in its direction of association.

9. The method of claim 1, further comprising:

generating a ranking of the one or more advertisements associated with one or more of the additional elements located within the threshold semantic distance of the first element, wherein the ranking is based on respective semantic distances between the first element and each additional element of the one or more additional elements.

10. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a query having a plurality of query terms;

obtaining a plurality of meanings associated with each of the plurality of query terms, including a first plurality of meanings associated with a first query term and a second plurality of meanings associated with a different second query term, wherein each meaning of the plurality of meanings is a sequence of one or more terms having a respective score corresponding to a likelihood of a query term having the meaning;

obtaining data representing a semantic space having a plurality of elements, each element being associated with a different respective meaning, and wherein each of the plurality of elements has a connection with at least one other element in the semantic space, wherein the connection between two elements indicates that the two elements have a similar meaning;

determining that a first meaning of the first plurality of meanings for the first query term has a connection in the semantic space with a second meaning of the second plurality of meanings for the second query term;

in response to determining that the first meaning has a connection in the semantic space with the second meaning, increasing respective scores associated with the first meaning, the second meaning, or both, an increase indicating a higher probability that a respective meaning relates to the query;

ranking the plurality of meanings according to the respective scores associated with the plurality of meanings;

selecting a highest-ranked meaning of the plurality of meanings;

identifying a first element in the semantic space having the highest-ranked meaning;

determining a plurality of additional elements in the semantic space that are each located within a threshold semantic distance of the first element;

identifying one or more advertisements associated, in the semantic space, with one or more of the additional elements that are located within the threshold semantic distance of the first element, wherein the one or more of the additional elements differ from the plurality of query terms; and

providing the identified one or more advertisements in response to receiving the query.

11. The system of claim 10, wherein the score associated with a particular meaning is higher if the particular meaning matches a query term rather than a stemmed or morphed variant of the query term.

12. The system of claim 10, wherein the score for a particular meaning is higher if the particular meaning has two or more terms that match two or more corresponding query terms.

13. The system of claim 10, wherein each meaning has an associated measure of commonness, and wherein more common meanings have a higher score than less common meanings.

14. The system of claim 10, wherein the operations further comprise comparing all of the first plurality of meanings to all of the second plurality of meanings to determine if any pair of meanings has a connection in the semantic space.

15. The system of claim 10, wherein the operations further comprise determining a semantic distance between the first element and a plurality of other elements including evaluating a sum of strengths of connections between the first element and the other element in the semantic space.

16. The system of claim 15, wherein the operations further comprise traversing multiple connections in the semantic space between the first element and each other element of the plurality of other elements, wherein the semantic distance between the first element and each other element is based on respective strengths of connections traversed between the first element and the other element.

17. The system of claim 16, wherein each connection in the semantic space has a direction of association, and wherein a first strength associated with traversing a connection in a direction opposite to its direction of association is higher than a second strength associated with traversing the connection in its direction of association.

18. The system of claim 10, wherein the operations further comprise:

generating a ranking of the one or more advertisements associated with one or more of the additional elements located within the threshold semantic distance of the first element, wherein the ranking is based on respective semantic distances between the first element and each additional element of the one or more additional elements.

19. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a query having a plurality of query terms;

obtaining a plurality of meanings associated with each of the plurality of query terms, including a first plurality of meanings associated with a first query term and a second plurality of meanings associated with a different second query term, wherein each meaning of the plurality of meanings is a sequence of one or more terms having a respective score corresponding to a likelihood of a query term having the meaning;

obtaining data representing a semantic space having a plurality of elements, each element being associated with a different respective meaning, and wherein each of the plurality of elements has a connection with at least one other element in the semantic space, wherein the connection between two elements indicates that the two elements have a similar meaning;

determining that a first meaning of the first plurality of meanings for the first query term has a connection in the semantic space with a second meaning of the second plurality of meanings for the second query term;

in response to determining that the first meaning has a connection in the semantic space with the second meaning, increasing respective scores associated with the first meaning, the second meaning, or both, an increase indicating a higher probability that a respective meaning relates to the query;

ranking the plurality of meanings according to the respective scores associated with the plurality of meanings;

selecting a highest-ranked meaning of the plurality of meanings;

identifying a first element in the semantic space having the highest-ranked meaning;

determining a plurality of additional elements in the semantic space that are each located within a threshold semantic distance of the first element;

identifying one or more advertisements associated, in the semantic space, with one or more of the additional elements that are located within the threshold semantic distance of the first element, wherein the one or more of the additional elements differ from the plurality of query terms; and

providing the identified one or more advertisements in response to receiving the query.

20. The computer program product of claim 19, wherein the score associated with a particular meaning is higher if the particular meaning matches a query term rather than a stemmed or morphed variant of the query term.

21. The computer program product of claim 19, wherein the score for a particular meaning is higher if the particular meaning has two or more terms that match two or more corresponding query terms.

22. The computer program product of claim 19, wherein each meaning has an associated measure of commonness, and wherein more common meanings have a higher score than less common meanings.

23. The computer program product of claim 19, wherein the operations further comprise comparing all of the first plurality of meanings to all of the second plurality of meanings to determine if any pair of meanings has a connection in the semantic space.

24. The computer program product of claim 19, wherein the operations further comprise determining a semantic distance between the first element and a plurality of other elements including evaluating a sum of strengths of connections between the first element and the other element in the semantic space.

25. The computer program product of claim 24, wherein the operations further comprise traversing multiple connections in the semantic space between the first element and each other element of the plurality of other elements, wherein the semantic distance between the first element and each other element is based on respective strengths of connections traversed between the first element and the other element.

26. The computer program product of claim 25, wherein each connection in the semantic space has a direction of association, and wherein a first strength associated with traversing a connection in a direction opposite to its direction of association is higher than a second strength associated with traversing the connection in its direction of association.

27. The computer program product of claim 19, wherein the operations further comprise:

generating a ranking of the one or more advertisements associated with one or more of the additional elements located within the threshold semantic distance of the first element, wherein the ranking is based on respective semantic distances between the first element and each additional element of the one or more additional elements.