# US 2010/0250527 A1 · Sponsored search results re-ranking based on linking associations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0250527 A1
- Document ID: US20100250527A1
- Status: Published application
- Kind: A1
- Application number: 12/410,037
- Filed: 2009-03-24
- Published: 2010-09-30
- Earliest claimed: 2009-03-24
- Assignees: Yahoo! Inc.
- Inventors: Arun Kumar Gnanamani; Evgeniy Makeev
- Web page: https://patentgrep.com/patent/US20100250527A1

## CPC

- G06Q 30/02: Marketing; Price estimation or determination; Fundraising
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

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

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

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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 (u1, u2, . . . un), 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.

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 4)

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

### Claim 7 (depends on 4)

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

### Claim 8 (depends on 4)

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

### Claim 9 (depends on 4)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

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.

### Claim 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 (u1, u2, . . . un), 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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 12)

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.

### Claim 15 (depends on 14)

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.

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

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 16)

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.

### Claim 19 (depends on 16)

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 (u1, u2, . . . un); 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.

### Claim 20 (depends on 19)

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

### Claim 21 (depends on 19)

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

### Claim 22 (depends on 19)

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

### Claim 23 (depends on 19)

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

### Claim 24 (depends on 19)

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.

### Claim 25 (depends on 24)

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.

### Claim 26 (depends on 25)

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.

### Claim 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 (u1, u2, . . . un), 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.
