Ranking search results using biased click distance

• US 7,599,917 B2
• Filed: 08/15/2005
• Issued: 10/06/2009
• Est. Priority Date: 08/15/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meyerzon, Dmitriy, Zaragoza, Hugo
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Badawi; Sherief
• Application Number:
  US11/206,286
• Publication Number:
  US 20070038622A1
• Time in Patent Office: 1,513 Days
• Field of Search: 707/102, 707/3, 707/5, 707/204, 707/7, 707/104.1, 715/501.1, 709/221
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Methods of providing a document relevance score to a document on a network are disclosed. Computer readable medium having stored thereon computer-executable instructions for performing a method of providing a document relevance score to a document on a network are also disclosed. Further, computing systems containing at least one application module, wherein the at least one application module comprises application code for performing methods of providing a document relevance score to a document on a network are disclosed.

Claims

1. A computer readable storage medium having stored thereon computer-executable instructions for ranking a plurality of documents in a network, wherein said computer-executable instructions when executed by the computer perform a method of generating search results in response to a search query, the method comprising:

storing document information in memory, the document information identifying the plurality of documents in the network, the plurality of documents including authoritative documents and non-authoritative documents, the authoritative documents including at least a first authoritative document and a second authoritative document, and the non-authoritative documents including at least a first non-authoritative document;

storing link information in the memory, the link information identifying links among the plurality of documents;

computing click distance values for each of the non-authoritative documents to the authoritative documents, the click distance values including at least a first click distance value that is a function of a number of links that need to be followed to create a path from the first non-authoritative document to the first authoritative document and a second click distance value that is a function of a number of links that need to be followed to create a path from the first non-authoritative document to the second authoritative document;

computing biased click distance values for each of the non-authoritative documents in the network to the authoritative documents, wherein the biased click distance values include at least a first biased click distance value that is a function of a lesser of the first and second click distances;

receiving the search query including at least one search term;

executing the search query to generate a list of the plurality of documents that include the at least one search term, the list of the plurality of documents including an identifier of the first non-authoritative document;

ranking the list of the plurality of documents that include the at least one search term using a ranking function that comprises one or more query-independent components, wherein at least one query-independent component includes a biased click distance parameter that takes into account the biased click distance values, including the first biased click distance value; and

outputting the ranked search results according to the ranking.

2. The computer readable storage medium of claim 1, wherein the method further comprises assigning assigned biased click distance values to the authoritative documents.

3. The computer readable storage medium of claim 2, wherein at least two of the assigned biased click distance values differ from one another.

4. The computer readable storage medium of claim 1, wherein the ranking function further comprises at least a second query-independent component that includes an edge value parameter that takes into account edge values of each edge in the network, wherein one or more edge values are a number other than 1.

5. The computer readable storage medium of claim 4, wherein the edge values are equal to one another and are equal to a number other than 1.

6. The computer readable storage medium of claim 4, wherein the edge values are equal to one another and are equal to or greater than a highest biased click distance value initially assigned to one or more of the authoritative documents.

7. The computer readable storage medium of claim 1, further comprising computer-executable instructions for assigning a score generated by the ranking function to each document in the network, said score being used to rank documents in ascending or descending order.

8. The computer readable storage medium of claim 7, wherein the score for each document is generated using a formula:

$\mathrm{Score}=\sum <br><br>\frac{{\mathrm{wtf}}^{\mathrm{\prime <br><br>}}<br><br>\left(k_1+1\right)}{k_1+{\mathrm{wtf}}^{\mathrm{\prime <br><br>}}}\times <br><br>\log <br><br>\left(\frac{N}{n}\right)+w_{c<br><br><br><br>d}<br><br>\frac{k_{c<br><br><br><br>d}}{k_{c<br><br><br><br>d}+\frac{b_{c<br><br><br><br>d}<br><br>\frac{\mathrm{CD}}{k_{\mathrm{ew}}}+b_{\mathrm{ud}}<br><br>\mathrm{UD}}{b_{c<br><br><br><br>d}+b_{\mathrm{ud}}}}$

wherein;

wtf′

represents a weighted term frequency,

N represents a number of the documents in the network,

n represents a number of the documents containing the search term,

W_cd represents a weight of the at least one query-independent component,

b_cd represents a weight of one of the click distance values,

b_ud represents a weight of a URL depth,

CD represents one of the computed click distance values or an assigned biased click distance for a document,

k_ew represents a tuning constant related to edge weights,

UD represents the URL depth, and

k_cd and k₁ are constants.

9. A method of determining document relevance scores for documents in a network, said method comprising the steps of:

storing document and link information for the documents in the network;

generating a representation of the network from the document and link information, wherein the representation of the network includes nodes that represent the documents and edges that represent the links;

assigning a biased click distance value to at least two authoritative nodes in the network, wherein the at least two authoritative nodes include at least a first authoritative node having a first assigned biased click distance and a second authoritative node having a second assigned biased click distance;

computing click distances for each non-authoritative node in the representation of the network to at least two of the authoritative nodes, wherein the click distances include a first click distance and a second click distance, the first click distance being a function of a number of the links that need to be followed to create a path from a first non-authoritative node to the first authoritative node, and the second click distance being a function of a number of the links that need to be followed to create a path from the first non-authoritative node to the second authoritative node;

computing biased click distance values for each of the non-authoritative documents, wherein the biased click distance values include at least a first biased click distance value that is a function of a lesser of the first and second click distances; and

using the biased click distance values to determine document relevance scores for each of the documents in the network.

10. The method of claim 9, wherein the first assigned biased click distance and the second assigned biased click distance differ from one another.

11. The method of claim 9, further comprising the step of:

assigning to each edge in the representation of the network an edge value, wherein the edge values are equal to or greater than 1.

12. The method of claim 11, wherein each edge value is greater than a highest biased click distance value assigned to any of the authoritative nodes.

13. The method of claim 9, wherein the document relevance score for each document on the network is generated using a formula:

$\mathrm{Score}=\sum <br><br>\frac{{\mathrm{wtf}}^{\mathrm{\prime <br><br>}}<br><br>\left(k_1+1\right)}{k_1+{\mathrm{wtf}}^{\mathrm{\prime <br><br>}}}\times <br><br>\log <br><br>\left(\frac{N}{n}\right)+w_{c<br><br><br><br>d}<br><br>\frac{k_{c<br><br><br><br>d}}{k_{c<br><br><br><br>d}+\frac{b_{c<br><br><br><br>d}<br><br>\frac{\mathrm{CD}}{k_{\mathrm{ew}}}+b_{\mathrm{ud}}<br><br>\mathrm{UD}}{b_{c<br><br><br><br>d}+b_{\mathrm{ud}}}}$

wherein;

wtf′

represents a weighted term frequency,

N represents a number of the documents in the network,

n represents a number of the documents containing a query term,

W_cd represents a weight of a query-independent component,

b_cd represents a weight of one of the click distances,

b_ud represents a weight of a URL depth,

CD represents one of the computed click distances or one of the assigned biased click distances,

k_ew represents a tuning constant related to edge weights,

UD represents the URL depth, and

k_cd and k₁ are constants.

14. A computing system comprising:

a processor; and

a memory, the memory storing computer-executable instructions which when executed by the processor perform a method of determining document relevance scores for nodes in a network, said method comprising the steps of;

assigning biased click distance values to at least two authoritative nodes in a representation of the network, wherein the at least two authoritative nodes include at least a first authoritative node having a first assigned biased click distance and a second authoritative node having a second assigned click distance;

computing click distances for each non-authoritative node in the representation of the network to at least two of the authoritative nodes, wherein the click distances include a first click distance and a second click distance, the first click distance being a function of a number of links that need to be followed to create a path from a first non-authoritative node to the first authoritative node, and the second click distance being a function of a number of the links that need to be followed to create a path from the first non-authoritative node to the second authoritative node;

computing biased click distance values for the non-authoritative nodes, wherein the biased click distance values include at least a first biased click distance value that is a function of a lesser of the first and second click distances; and

using the biased click distance values to determine document relevance scores for each of the nodes in the network.