System and method for ranking search results using click distance

• US 20060074903A1
• Filed: 09/30/2004
• Published: 04/06/2006
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meyerzon, Dmitriy, Zaragoza, Hugo
• Granted Patent: US 7,761,448 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

Search results of a search query on a network are ranked according to an additional click distance property associated with each of the documents on the network. The click distance is measurement of the number clicks or user navigations from a page or pages on the network designated as highest authority or root pages on the network. The precision of the results is increased by the addition of the click distance term when the site or intranet where the search query takes place is hierarchically structured.

Claims

1. A computer-implemented method for ranking search results, comprising:

storing document and link information for documents on a network;

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

computing the click distance for each of the nodes in the representation of the network, wherein the click distance is measured from a first node designated as a highest authority node to second node associated with the computed click distance; and

using the computed click distance associated with each of the documents as a query-independent relevance measure in ranking the documents for producing the ranked search results.

2. The computer-implemented method of claim 1, wherein generating a representation of the network further comprises generating a network graph and storing the network graph into memory.

3. The computer-implemented method of claim 1, wherein computing the click distance further comprises initializing the click distance associated with each of the documents at a maximum value except a document corresponding to the highest authority node.

4. The computer-implemented method of claim 1, further comprising storing a current node of the representation of the network in a queue of nodes until the click distance of target nodes associated with the current node are computed.

5. The computer-implemented method of claim 4, wherein the click distance of one of the target nodes is set to the click distance of the current node plus a variable when the click distance of the one of the target nodes is greater than the click distance of the current node plus the variable.

6. The computer-implemented method of claim 1, wherein the computed click distance associated with each of the documents is merged into an index that includes other statistics that correspond to each of the documents.

7. The computer-implemented method of claim 6, wherein a scoring function is populated with the computed click distance and the other statistics for producing a score by which the documents are ranked.

8. The computer-implemented method of claim 1, wherein using the computed click distance associated with each of the documents as a query-independent relevance measure further comprises using a component corresponding to the click distance in a scoring function for determining a relevance score for each of the documents.

9. The computer-implemented method of claim 8, wherein the relevance score is offset by a Uniform Resource Locator depth property that smoothes the effect of the click distance on the relevance score.

10. The computer-implemented method of claim 1, wherein generating the representation of the network further comprises generating a representation of the network wherein more than one node within the representation of the network is designated as a high authority node.

11. The computer-implemented method of claim 1, further comprising allowing the click distance to be manually changed after the click distance is calculated.

12. The computer-implemented method of claim 1, further comprising ranking the documents according to a scoring function (score) that is determined according to at least:

the computed click distance (CD), a weight of a query-independent component (w_cd), a weight of the click distance (b_cd), a weight of a URL depth (b_ud), the URL depth (UD), and a click distance saturation constant (K_cd).

13. The computer-implemented method of claim 1, further comprising ranking the documents according to a scoring function (score) that is determined according to at least:

the computed click distance (CD), a weighted term frequency (wtf), a weighted document length (wdl), an average weighted document length (avwdl), a number of documents on the network (N);

a number of documents containing a query term (n), a weight of a query-independent component (w_cd), a weight of the click distance (b_cd), a weight of a URL depth (b_ud), the URL depth (UD), a click distance saturation constant (K_cd), and other constant (k₁, b).

14. The computer-implemented method of claim 13, wherein the scoring function (score) is given by:

$\mathrm{score}=\sum <br><br>\frac{\mathrm{wtf}<br><br>\left(k_1+1\right)}{k_1<br><br>\left(\left(1-b\right)+b<br><br>\frac{\mathrm{wdl}}{\mathrm{avwdl}}\right)+\mathrm{wtf}}\times <br><br>\log <br><br>\left(\frac{N}{n}\right)+w_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}<br><br>\frac{k_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}}{k_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}+\frac{b_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}<br><br>\mathrm{CD}+b_{\mathrm{ud}}<br><br>\mathrm{UD}}{b_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}+b_{\mathrm{ud}}}}$

15. A system for ranking search results, comprising:

a search engine include on a computing device, the search engine configured to execute computer-executable instructions, the computer-executable instructions comprising;

discovering documents on a network;

recording document and link information for each of the documents on the network;

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

computing the click distance to each node in the representation of the network from a highest authority node;

associating the computed click distance to each node with the document that corresponds to that node; and

using the computed click distance associated with each of the documents as a query-independent relevance measure in ranking the documents for producing the ranked search results.

16. The system of claim 15, wherein generating a representation of the network further comprises generating a network graph and storing the network graph into memory.

17. The system of claim 15, wherein associating the computed click distance to each node with the document that corresponds to that node further comprises merging the computed click distance associated with each of the documents into an index that includes other ranking values that correspond to each of the documents.

18. The system of claim 17, wherein a scoring function is populated with the computed click distance and the other ranking values for producing a score by which the documents are ranked.

19. The system of claim 15, wherein using the computed click distance associated with each of the documents as a query-independent relevance measure further comprises using a component corresponding to the click distance in a scoring function for determining a relevance score for each of the documents.

20. The system of claim 19, wherein the relevance score is offset by a Uniform Resource Locator depth property that smoothes the effect of click distance on the scoring function when the click distance for a node is disproportionate to the depth of the node in the representation of the network.

21. The system of claim 15, further comprising ranking the documents according to a scoring function (score) that is determined according to at least:

the computed click distance (CD), a weight of a query-independent component (w_cd), a weight of the click distance (b_cd), a weight of a URL depth (b_ud), the URL depth (UD), and a click distance saturation constant (K_cd).

22. The system of claim 15, further comprising ranking the documents according to a scoring function (score) that is determined according to at least:

the computed click distance (CD), a weighted term frequency (wtf), a weighted document length (wdl), an average weighted document length (avwdl), a number of documents on the network (N);

a number of documents containing a query term (n), a weight of a query-independent component (w_cd), a weight of the click distance (b_cd), a weight of a URL depth (b_ud), the URL depth (UD), a click distance saturation constant (K_cd), and other constant (k₁, b).

23. The system of claim 22, wherein the scoring function (score) is given by:

$\mathrm{score}=\sum <br><br>\frac{\mathrm{wtf}<br><br>\left(k_1+1\right)}{k_1<br><br>\left(\left(1-b\right)+b<br><br>\frac{\mathrm{wdl}}{\mathrm{avwdl}}\right)+\mathrm{wtf}}\times <br><br>\log <br><br>\left(\frac{N}{n}\right)+w_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}<br><br>\frac{k_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}}{k_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}+\frac{b_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}<br><br>\mathrm{CD}+b_{\mathrm{ud}}<br><br>\mathrm{UD}}{b_{c<br><br>\text{\hspace{1em}<br><br>}<br><br>d}+b_{\mathrm{ud}}}}$

24. The system of claim 15, wherein generating the representation of the network further comprises generating a representation of the network wherein more than one node within the representation of the network is designated as a high authority node.

25. The system of claim 15, further comprising allowing the click distance to be manually changed after the click distance is calculated.

26. A computer-readable medium that includes computer-executable instructions for ranking search results, the instructions comprising:

storing document and link information for documents on a network such that a network graph representing the network is generated in memory;

storing each document represented in the network graph in a queue when the document has a click distance value that is different from a first click distance value;

when the queue is not empty;

removing a document from the queue,

calculating a click distance for each of the target documents associated with the removed document, wherein each target document is updated with a new click distance value other than the first click distance value when each target document'"'"'s click distance is greater than the click distance associated with the removed document plus a variable, and

adding each of the target documents to the queue that have been updated; and

using the computed click distance associated with each of the documents as a query-independent relevance measure in ranking the documents for producing the ranked search results.

27. The computer-readable medium of claim 26, wherein using the computed click distance associated with each of the documents as a query-independent relevance measure further comprises using a component corresponding to the click distance in a scoring function for determining a relevance score for each of the documents.

28. The computer-readable medium of claim 26, wherein generating the representation of the network further comprises generating a representation of the network wherein more than one node within the representation of the network is designated as a high authority node.

29. The computer-readable medium of claim 26, further comprising allowing the click distance to be manually changed after the click distance is calculated.