Web searching

• US 7,836,058 B2
• Filed: 03/27/2008
• Issued: 11/16/2010
• Est. Priority Date: 03/27/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Xuanhui, Mityagin, Anton, Chellapilla, Kumar H.
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US12/056,302
• Publication Number:
  US 20090248657A1
• Time in Patent Office: 964 Days
• Field of Search: 707/737, 707/739, 707/748, 707/751, 707/754, 707/798
• US Class Current: 707/748
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Mislabeled URLs are identified and corrected based upon a click relevance ranking computed from user data comprising user click information. The click relevance ranking is formed by applying a set of relevance ordering rules to user log data aggregated by query and URL and by mapping the results of the relevance ordering rules into a linear ordering. For a given query, the aggregated user log data comprises a relative total number of impression, a relative total number of clicks received and a rank associated with the query/URL pair at the time of the total number of impressions and total number of clicks received. The click relevance ranking is used to identify and correct mislabeled query/URL pairs of other rankings according to a number of disclosed methods.

Claims

1. A method for improving relevance of web searches for a query, comprising:

providing a pre-existing relevance ranking of a plurality of query/uniform resource locator (URL) pairs, respective labels being associated with the plurality of query/URL pairs;

computing a click relevance ranking of the plurality of query/URL pairs based upon user log data comprising user click data; and

identifying and correcting mislabeled query/URL pairs in the pre-existing relevance ranking based upon the click relevance ranking,

the user log data comprising;

respective rank associated with a query/URL pair within the plurality of query/URL pairs at one or more times;

respective total numbers of impressions (I) for the rank associated with the query/URL pair; and

respective total numbers of clicks received (C) for the rank associated with the query/URL pair,

wherein the click rate (CR) is the sum of the total number of clicks for all ranks associated with the query/URL pair divided by the sum of the total number of impressions for all ranks associated with the query/URL pair, and

computing the click relevance ranking comprises;

aggregating the user log data by query and URL;

reducing click bias;

creating a click relevance ordering of the plurality of query/URL pairs;

creating a directed acyclic graph of a relevance relationship between the plurality of query/URL pairs; and

mapping the directed acyclic graph into a linear ordering, at least some of one or more of the providing, computing and identifying performed at least in part with a microprocessor.

2. The method of claim 1, reducing the click bias comprising:

corresponding to the total number of clicks received divided by the total number of impressions;

calculating a respective click weight at rank for the query/URL pair corresponding to;

3. The method of claim 2, creating click relevance ordering of an m^th and n^th query/URL pair within the plurality of query/URL pairs comprising utilization of a plurality of click relevance ordering rules comprising:

if C_m≈

C_n and CR_m>

CR_n and NCR_m>

NCR_n;

if I_m≈

I_n and CR_m>

CR_n and NCR_m>

NCR_n;

if I_m≈

I_n and CR_m>

2×

CR_n and NCR_m≈

NCR_n;

if I_m=I_n and CR_m≈

CR_n and NCR_m>

2×

NCR_n;

if I_m>

100 and I_n>

100 and CR_m>

5×

CR_n and NCR_m>

0.8×

NCR_n; and

if CR_m>

50×

C_n;

wherein m=1;

k, n=1;

k, and k=number of query/URL pairs in user data log;

and wherein URL_m is more relevant than URL_n if any one of the plurality of click relevance ordering rules are satisfied.

4. The method of claim 3, the plurality of click relevance ordering rules mitigating contradictory relations in the acyclic graph.

5. The method of claim 4, mapping the directed acyclic graph into a linear ordering performed using a flooding technique.

6. The method of claim 4, wherein the user log data is limited to a specific individual.

7. The method of claim 1, comprising:

determining a longest common subsequence (LCS) of the plurality of query/URL pairs that is strictly decreasing in both the pre-existing and click relevance ranking; and

removing labels for query/URL pairs which are not in the LCS.

8. The method of claim 1, comprising:

determining a LCS of query/URL pairs that is strictly decreasing in both the pre-existing and click relevance ranking;

assigning the pre-existing relevance ranking labels associated with the LCS of query/URL pairs to the click relevance ranking; and

relabeling a label associated with the query/URL pair not in the LCS with a new label interpolated from the click relevance ranking.

9. The method of claim 8, comprising:

increasing a value of the label associated with a most relevant query/URL pair when the click rate exceeds a specified threshold.

10. The method of claim 1, comprising:

computing a distribution of labels in the pre-existing relevance ranking; and

relabeling a label associated with the query/URL pairs in the click relevance ranking according to the distribution of labels in the pre-existing relevance ranking, the labels decreasing with respect to click relevance.

11. The method of claim 10, comprising:

increasing a value of the label associated with a most relevant query/URL pair when the click rate exceeds a specified threshold.

12. The method of claim 1, the pre-existing relevance ranking comprising human expert ranking.

13. A system configured to improve the relevance of web searches for a query comprising:

a pre-existing relevance ranking component configured to rank a plurality of query/URL pairs associated with a query;

a click relevance ranking component configured to rank the query/URL pairs based upon user click data; and

a dynamic program configured to identify and correct mislabeled query/URL pairs in the pre-existing relevance ranking based upon the click relevance ranking,

the user log data comprising;

respective rank associated with a query/URL pair within the plurality of query/URL pairs at one or more times;

respective total numbers of impressions (I) for the rank associated with the query/URL pair; and

respective total numbers of clicks received (C) for the rank associated with the query/URL pair;

wherein the click rate (CR) is the sum of the total number of clicks for all ranks associated with the query/URL pair divided by the sum of the total number of impressions for all ranks associated with the query/URL pair, and

the click relevance ranking component configured to;

aggregate user log data by query and URL;

reduce click bias;

create a click relevance ordering of the plurality of query/URL pairs;

create a directed acyclic graph of a relevance relationship between the plurality of query/URL pairs; and

map the directed acyclic graph into a linear ordering, at least some of one or more of the pre-existing relevance ranking component, click relevance ranking component and dynamic program implemented at least in part with a microprocessor.

14. The system of claim 13, reducing the click bias comprising:

corresponding to the total number of clicks received divided by the total number of impressions;

calculating respective click weight at ranks for the plurality of URLs corresponding to;

15. The system of claim 14, creating click relevance ordering of an m^th and n^th query/URL pair comprising utilization of a plurality of click relevance ordering rules comprising:

if C_m≈

C_n and CR_m>

CR_n and NCR_m>

NCR_n;

if I_m≈

I_n and CR_m>

CR_n and NCR_m>

NCR_n;

if I_m≈

I_n and CR_m>

2×

CR_n and NCR_m≈

NCR_n;

if I_m≈

I_n and CR_m≈

CR_n and NCR_m>

2×

NCR_n;

if I_m>

100 and I_n>

100 and CR_m>

5×

CR_n and NCR_m>

0.8×

NCR_n; and

if CR_m>

50×

C_n;

wherein m=1;

k, n=1;

k, and k=number of query/URL pairs in user data log;

and wherein URL_m is more relevant than URL_n if any one of the plurality of click relevance ordering rules are satisfied.

16. A method for improving relevance of web searches for a query, comprising:

providing a pre-existing relevance ranking of a plurality of query/uniform resource locator (URL) pairs, respective labels being associated with the plurality of query/URL pairs;

aggregating user log data by the query and URL, wherein the user log data comprises a total number of clicks (C) and a total number of impressions (I) for the plurality of query/URL pairs;

calculating a click rate (CR) and a normalized click rate (NCR) for each of the plurality of query/URL pairs;

creating click relevance ordering of an m^th and n^th query/URL pair comprising utilization of a plurality of click relevance ordering rules comprising;

if C_m≈

C_n and CR_m>

CR_n and NCR_m>

NCR_n;

if I_m≈

I_n and CR_m>

CR_n and NCR_m>

NCR_n;

if I_m≈

I_n and CR_m>

2×

CR_n and NCR_m≈

NCR_n;

if I_m≈

I_n and CR_m≈

CR_n and NCR_m>

2×

NCR_n;

if I_m>

100 and I_n>

100 and CR_m>

5×

CR_n and NCR_m>

0.8×

NCR_n; and

if CR_m>

50×

C_n;

wherein m=1;

k, n=1;

k, and k=number of query/URL pairs in user data log;

and wherein URL_m is more relevant than URL_n if any one of the plurality of click relevance ordering rules are satisfied;

creating a directed acyclic graph of a relevance relationship between the plurality of query/URL pairs;

mapping the directed acyclic graph into a linear ordering; and

identifying and correcting mislabeled query/URL pairs in the pre-existing relevance ranking based upon the click relevance ranking,

at least some of one or more of the providing, aggregating, calculating, creating click relevance ordering, creating a directed acyclic graph, mapping and identifying performed at least in part with a microprocessor.