Sponsored search results re-ranking based on linking associations

• US 8,041,715 B2
• Filed: 03/24/2009
• Issued: 10/18/2011
• Est. Priority Date: 03/24/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Gnanamani, Arun Kumar, Makeev, Evgeniy
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): MOSER, BRUCE M
• Application Number:
  US12/410,037
• Publication Number:
  US 20100250527A1
• Time in Patent Office: 938 Days
• Field of Search: 707/2, 707/5, 707/999.002, 707/999.005, 707/726, 707/735
• US Class Current: 707/726
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A computer-implemented system and methods of re-ranking sponsored search results by a search engine in response to a search query include: retrieving one or more organic search results and a plurality of sponsored search results (“search results”), along with their respective rankings, associated with a search query; determining a degree of association between each sponsored search result and the other search results through analyzing web links between the search results and other web documents to or from which the search results are at least indirectly linked; calculating a clustering score for each sponsored search result based on their respective degrees of linking association; generating a new ranking score for each sponsored search result based on their respective clustering scores and rankings; and re-ranking, and storing in memory, the plurality of sponsored search results based on the new ranking scores of each respective sponsored search result.

Claims

1. A computer-implemented method of re-ranking sponsored search results by a search engine in response to a search query, the method comprising:

retrieving, by a search engine, one or more organic search results and a plurality of sponsored search results (“

search results”

), along with their respective rankings, associated with a search query;

determining, by the search engine, a degree of association between each sponsored search result and the other search results through analyzing web links between the plurality of sponsored search results, the one or more organic search results, and other web documents to or from which the search results are at least indirectly linked;

calculating, by the search engine, a clustering score for each sponsored search result based on their respective degrees of linking association;

generating, by the search engine, a new ranking score for each sponsored search result based on their respective clustering scores and rankings;

re-ranking, by the search engine, the plurality of sponsored search results based on the new ranking scores of each respective sponsored search result; and

storing in memory, by the search engine, the plurality of re-ranked sponsored search results in relation to the search query.

2. The method of claim 1, further comprising:

delivering the re-ranked plurality of sponsored search results to a user in response to the search query submitted by the user.

3. The method of claim 1, wherein re-ranking comprises moving a sponsored search result to a higher-ranked position if the sponsored search result is closely associated with at least another search result.

4. The method of claim 1, further comprising:

delivering the search results, by the search engine, to a web graph, wherein the web graph contains a plurality of interlinked web documents each represented by a node (u₁, u₂, . . . u_n), and is stored on one or more computers coupled with the search engine; and

retrieving, by the search engine, values of one or more operators based on the relative linking within the web graph between the one or more organic search results, the plurality of sponsored search results, and any of the plurality of web documents.

5. The method of claim 4, wherein the operator comprises Common Vertices, which is a function, f(u₁,u₂), that provides a number of web documents that have a link to both web documents u₁ and u₂.

6. The method of claim 4, wherein the operator comprises Reachable Vertices, which is a function, f(u₁,u₂), that provides a number of web documents that link to both web documents u₁ and u₂ through at least one other web document, but no more than a predetermined maximum number of nodes.

7. The method of claim 4, wherein the operator comprises Edge Distance, which is a function, f(u₁,u₂), that generates an inverse of a shortest path between the web documents u₁ and u₂.

8. The method of claim 4, wherein the operator comprises NumPaths, which is a function, f(u₁,u₂), that provides a number of distinct paths between the nodes u₁ and u₂.

9. The method of claim 4, further comprising:

calculating a FunctionScore(f,u) between each of a possible pair of nodes within the plurality of sponsored search results (S) and the one or more organic search results (O), and the value of each operator (f), wherein the FunctionScore comprises

Σ

((f(u,o)×

RankWeightOrganic)/(1+log(pos(o))))/|O|, for each o in O+Σ

((f(u,s)×

RankWeightSponsored)/(1+log(pos(s))))/|S|, for each s in S,

wherein RankWeightOrganic and RankWeightSponsored comprise normalizing weights applied to the organic and sponsored search results, respectively, and wherein pos(o) and pos(s) comprise the ranking of each organic and sponsored search result, respectively.

10. The method of claim 9, wherein calculating the clustering score of a sponsored search result comprises calculating Σ

(FunctionScore(f,u)×

WO(f)) for each operator (f), wherein WO(f) comprises a scalar that normalizes each operator (f) to each other.

11. The method of claim 10, further comprising:

limiting the number of sponsored search results used in the calculation steps to a specific number to be able to perform the calculations more quickly.

12. A computer-implemented method of re-ranking sponsored search results by a search engine in response to a search query, the method comprising:

retrieving, by a search engine, one or more organic search results and a plurality of sponsored search results (“

search results”

), along with their respective rankings, associated with a search query;

delivering the search results, by the search engine, to a web graph, wherein the web graph contains a plurality of interlinked web documents each represented by a node (u₁, u₂, . . . u_n), and is stored on computer storage coupled with the search engine;

retrieving, by the search engine, values of one or more operators based on the relative linking within the web graph between the one or more organic search results, the plurality of sponsored search results, and any of the plurality of web documents;

calculating, by the search engine, a clustering score for each sponsored search result based on the one or more operators, wherein the clustering score indicates a degree of linking association between each sponsored search result and the other search results;

generating, by the search engine, a new ranking score for each sponsored search result based on their respective clustering scores and rankings;

re-ranking, by the search engine, the plurality of sponsored search results based on the new ranking scores of each respective sponsored search result; and

storing in memory, by the search engine, the plurality of re-ranked sponsored search results in relation to the search query.

13. The method of claim 12, further comprising:

delivering the re-ranked plurality of sponsored search results to a user in response to the search query submitted by the user.

14. The method of claim 12, further comprising:

calculating a FunctionScore(f,u) between each of a possible pair of nodes within the plurality of sponsored search results (S) and the one or more organic search results (O), and the value of each operator (f), wherein the FunctionScore comprises

Σ

((f(u,o)×

RankWeightOrganic)/(1+log(pos(o))))/|O|, for each o in O+Σ

((f(u,s)×

RankWeightSponsored)/(1+log(pos(s))))/|S|, for each s in S,

wherein RankWeightOrganic and RankWeightSponsored comprise normalizing weights applied to the organic and sponsored search results, respectively, and wherein pos(o) and pos(s) comprise the ranking of each organic and sponsored search result, respectively.

15. The method of claim 14, wherein calculating the clustering score of a sponsored search result comprises calculating Σ

(FunctionScore(f,u)×

WO(f)) for each operator (f), wherein WO(f) comprises a scalar that normalizes each operator (f) to each other.

16. A computer-implemented system of re-ranking sponsored search results in response to a search query, the system comprising:

a search engine having a memory, a processor, and a communication interface through which the search engine retrieves one or more organic search results and a plurality of sponsored search results (“

search results”

), along with their respective rankings, associated with a search query;

an operator determiner coupled with the search engine to determine a degree of association between each sponsored search result and the other search results through analyzing web links between the plurality of sponsored search results, the one or more organic search results, and other web documents to or from which the search results are at least indirectly linked; and

a re-ranking engine coupled with the operator determiner and the search engine to;

calculate a clustering score for each sponsored search result based on their respective degrees of linking association;

generate a new ranking score for each sponsored search result based on their respective clustering scores and rankings;

re-rank the plurality of sponsored search results based on the new ranking scores of each respective sponsored search result; and

store in the memory the plurality of re-ranked search results in relation to the search query.

17. The system of claim 16, wherein the search engine delivers the re-ranked plurality of sponsored search result to a user in response to the search query submitted by the user.

18. The system of claim 16, wherein re-ranking comprises moving a sponsored search result to a higher-ranked position if the sponsored search result is closely associated with at least another search result.

19. The system of claim 16, further comprising:

one or more web graph machines having stored thereon a web graph, the one or more web graph machines coupled with the search engine, wherein the web graph contains a plurality of interlinked web documents each represented by a node (u₁, u₂, . . . u_n); and

wherein the search engine retrieves values of one or more operators from the one or more web graph machines based on the relative linking within the web graph of the one or more organic search results, the plurality of sponsored search results, and any of the plurality of web documents.

20. The system of claim 19, wherein the operator comprises Common Vertices, which is a function, f(u₁,u₂), that provides a number of web documents that have a link to both web documents u₁ and u₂.

21. The system of claim 19, wherein the operator comprises Reachable Vertices, which is a function, f(u₁,u₂), that provides a number of web documents that link to both web documents u₁ and u₂ through at least one other web document, but no more than a predetermined maximum number of nodes.

22. The system of claim 19, wherein the operator comprises Edge Distance, which is a function, f(u₁,u₂), that generates an inverse of a shortest path between the web documents u₁ and u₂.

23. The system of claim 19, wherein the operator comprises NumPaths, which is a function, f(u₁,u₂), that provides a number of distinct paths between the nodes u₁ and u₂.

24. The system of claim 19, wherein the re-ranking engine:

calculates a FunctionScore(f,u) between each of a possible pair of nodes within the plurality of sponsored search results (S) and the one or more organic search results (O), and the value of each operator (f), wherein the FunctionScore comprises

Σ

((f(u,o)×

RankWeightOrganic)/(1+log(pos(o))))/|O|, for each o in O+Σ

((f(u,s)×

RankWeightSponsored)/(1+log(pos(s))))/|S|, for each s in S,

wherein RankWeightOrganic and RankWeightSponsored comprise normalizing weights applied to the organic and sponsored search results, respectively, and wherein pos(o) and pos(s) comprise the ranking of each organic and sponsored search result, respectively.

25. The system of claim 24, wherein the clustering score comprises Σ

(FunctionScore(f,u)×

WO(f)) for each operator (f), wherein WO(f) comprises a scalar that normalizes each operator (f) to each other.

26. The system of claim 25, wherein the re-ranking engine limits the number of sponsored search results used in the calculation of the FunctionScores and the clustering score to a specific number.

27. A computer-implemented method of re-ranking sponsored search results by a search engine in response to a search query, the method comprising:

retrieving, by a search engine, one or more organic search results and a plurality of sponsored search results (“

search results”

), along with their respective rankings, associated with a search query;

delivering the search results, by the search engine, to a web graph, wherein the web graph contains a plurality of interlinked web documents each represented by a node (u₁, u₂, . . . u_n), and is stored on computer storage coupled with the search engine;

retrieving, by the search engine, values of one or more operators based on the relative linking within the web graph between the one or more organic search results, the plurality of sponsored search results, and any of the plurality of web documents;

calculating, by the search engine, a clustering score for each sponsored search result based on the one or more operators, wherein the clustering score indicates a degree of linking association between each sponsored search result and the other search results;

re-ranking, by the search engine, the plurality of sponsored search results based on the clustering scores of each respective sponsored search result;

storing in memory, by the search engine, the plurality of re-ranked sponsored search results in relation to the search query; and

delivering the re-ranked plurality of sponsored search results to a user in response to the search query submitted by the user.