System and method for ranking search results using click distance

US 7,761,448 B2
Filed: 09/30/2004
Issued: 07/20/2010
Est. Priority Date: 09/30/2004
Status: Expired due to Fees

First Claim

Patent Images

1. A system for ranking search results, comprising a search engine on a computing device, the search engine configured to execute computer-executable instructions, which when executed by the computing system cause the computing system to perform a method comprising:

discovering a plurality of documents on a network;

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

generating a representation of the network from the document and link information, wherein the representation of the network includes a plurality of nodes, each document being represented by one of the plurality of nodes;

receiving manually input click distances designating a subset of the plurality of nodes as highest authority nodes, the subset of the plurality of nodes including at least a first highest authority node and a second highest authority node, wherein the manually input click distances indicate a relative importance of each highest authority node with respect to other highest authority nodes;

initializing click distances for a second subset of the plurality of nodes to a maximum value, the second subset of the plurality of nodes not including highest authority nodes and comprising at least a first non-highest authority node and a second non-highest authority node;

computing click distances for the first and second non-highest authority nodes by;

determining a first click distance for the first non-highest authority node, the first click distance being a first number of branches traversed on a first shortest path between the first non-highest authority node and the first highest authority node;

determining a second click distance for the first non-highest authority node, the second click distance being a second number of branches traversed on a second shortest path between the first non-highest authority node and the second highest authority node;

determining a third click distance for the second non-highest authority node, the third click distance being a third number of branches traversed on a third shortest path between the second non-highest authority node and the first highest authority node; and

determining a fourth click distance for the second non-highest authority node, the fourth click distance being a fourth number of branches traversed on a fourth shortest path between the second non-highest authority node and the second highest authority node;

storing the first, second, third, and fourth click distances in memory, such that the first and second click distances are associated with a first document, and the third and fourth click distances are associated with a second document;

calculating search rank results using at least one of the first, second, third, and fourth click distances associated with each of the first and second documents as a query-independent relevance measure in ranking the plurality of documents; and

storing search rank results in memory, wherein the search rank results comprise a list of documents arranged in a descending order of relevance.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

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.

239 Citations

20 Claims

1. A system for ranking search results, comprising a search engine on a computing device, the search engine configured to execute computer-executable instructions, which when executed by the computing system cause the computing system to perform a method comprising:
- discovering a plurality of documents on a network;
  
  recording document and link information for each of the plurality of documents on the network;
  
  generating a representation of the network from the document and link information, wherein the representation of the network includes a plurality of nodes, each document being represented by one of the plurality of nodes;
  
  receiving manually input click distances designating a subset of the plurality of nodes as highest authority nodes, the subset of the plurality of nodes including at least a first highest authority node and a second highest authority node, wherein the manually input click distances indicate a relative importance of each highest authority node with respect to other highest authority nodes;
  
  initializing click distances for a second subset of the plurality of nodes to a maximum value, the second subset of the plurality of nodes not including highest authority nodes and comprising at least a first non-highest authority node and a second non-highest authority node;
  
  computing click distances for the first and second non-highest authority nodes by;
  
  determining a first click distance for the first non-highest authority node, the first click distance being a first number of branches traversed on a first shortest path between the first non-highest authority node and the first highest authority node;
  
  determining a second click distance for the first non-highest authority node, the second click distance being a second number of branches traversed on a second shortest path between the first non-highest authority node and the second highest authority node;
  
  determining a third click distance for the second non-highest authority node, the third click distance being a third number of branches traversed on a third shortest path between the second non-highest authority node and the first highest authority node; and
  
  determining a fourth click distance for the second non-highest authority node, the fourth click distance being a fourth number of branches traversed on a fourth shortest path between the second non-highest authority node and the second highest authority node;
  
  storing the first, second, third, and fourth click distances in memory, such that the first and second click distances are associated with a first document, and the third and fourth click distances are associated with a second document;
  
  calculating search rank results using at least one of the first, second, third, and fourth click distances associated with each of the first and second documents as a query-independent relevance measure in ranking the plurality of documents; and
  
  storing search rank results in memory, wherein the search rank results comprise a list of documents arranged in a descending order of relevance.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- - 2. The system of claim 1 wherein generating a representation of the network further comprises generating a network graph and storing the network graph into the memory.
  - 3. The system of claim 1 wherein computing click distances further comprises merging the first, second, third, and fourth click distances into an index that includes one or more other ranking values that correspond to each of the first and second documents.
  - 4. The system of claim 3 further comprising populating a scoring function with the first, second, third, and fourth click distances and the one or more other ranking values for producing a score by which the first and second documents are ranked.
  - 5. The system of claim 1 wherein calculating search rank results using at least one of the click distances associated with each of the first and second documents as a query-independent relevance measure further comprises using a component corresponding to the first, second, third, and fourth click distances in a scoring function for determining a relevance score for each of the documents.
  - 6. The system of claim 5 wherein the relevance score is offset by a Uniform Resource Locator depth property that smoothes an effect of a click distance on the scoring function when a click distance for a node is disproportionate to a depth of the node in the representation of the network.
  - 7. The system of claim 1 wherein calculating the search rank results further comprises ranking the first and second documents according to a scoring function (score) that is determined according to at least:
    - the at least one of the click distances associated with each of the first and second documents (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).
  - 8. The system of claim 1 wherein calculating the search rank results further comprises ranking the first and second documents according to a scoring function (score) that is determined according to at least:
    - the at least one of the click distances associated with each of the first and second documents (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).
  - 9. The system of claim 8 wherein the scoring function (score) is given by:
    - $score = \sum \frac{w t f (k_{1} + 1)}{k_{1} ((1 - b) + b \frac{w d l}{a v w d l}) + w t f} \times \log (\frac{N}{n}) + w_{c d} \frac{k_{c d}}{k_{c d} + \frac{b_{c d} C D + b_{u d} U D}{b_{c d} + b_{u d}}} .$
  - 10. The system of claim 1 further comprising:
    - allowing the at least one of the click distances associated with each of the first and second documents to be manually changed.

11. A method for ranking search results, the method comprising:
- discovering a plurality of documents stored on one or more computing devices in a network of computing devices;
  
  recording document and link information for each of the plurality of documents;
  
  generating a representation of the network from the document and link information, wherein the representation of the network includes a plurality of nodes, each document being represented by one of the plurality of nodes;
  
  receiving manually input click distances designating a subset of the plurality of nodes as highest authority nodes, the subset of the plurality of nodes including at least a first highest authority node and a second highest authority node, wherein the manually input click distances indicate a relative importance of each highest authority node with respect to other highest authority nodes;
  
  initializing click distances for a second subset of the plurality of nodes to a maximum value, the second subset of the plurality of nodes not including the highest authority nodes and comprising at least a first non-highest authority node and a second non-highest authority node;
  
  computing click distances for the first and second non-highest authority nodes by;
  
  determining a first click distance for the first non-highest authority node, the first click distance being a first number of branches traversed on a first shortest path between the first non-highest authority node and the first highest authority node;
  
  determining a second click distance for the first non-highest authority node, the second click distance being a second number of branches traversed on a second shortest path between the first non-highest authority node and the second highest authority node;
  
  determining a third click distance for the second non-highest authority node, the third click distance being a third number of branches traversed on a third shortest path between the second non-highest authority node and the first highest authority node; and
  
  determining a fourth distance for the second non-highest authority node, the fourth click distance being a fourth number of branches traversed on a fourth shortest path between the second non-highest authority node and the second highest authority node;
  
  storing the first, second, third, and fourth click distances in memory on a computing device in the network, such that the first and second click distances are associated with a first document, and the third and fourth click distances are associated with a second document;
  
  calculating search rank results using at least one of the first, second, third, and fourth click distances associated with each of the first and second documents as a query-independent relevance measure in ranking the plurality of documents; and
  
  storing the search rank results in the memory on the computing device.
- View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
- - 12. The method of claim 11, wherein generating a representation of the network further comprises generating a network graph and storing the network graph into the memory.
  - 13. The method of claim 11 wherein computing the first, second, third, and fourth click distances further comprises merging the first, second, third, and fourth click distances into an index that includes one or more other ranking values that correspond to each of the first and second documents.
  - 14. The method of claim 13 further comprising populating a scoring function with first, second, third, and fourth click distances and the one or more other ranking values for producing a score by which the first and second documents are ranked.
  - 15. The method of claim 11 wherein calculating search rank results using at least one of the click distances associated with each of the first and second documents as a query-independent relevance measure further comprises using a component corresponding to the first, second, third, and fourth click distances in a scoring function for determining a relevance score for each of the documents.
  - 16. The method of claim 11 wherein the relevance score is offset by a Uniform Resource Locator depth property that smoothes an effect of a click distance on the scoring function when a click distance for a node is disproportionate to a depth of the node in the representation of the network.
  - 17. The method of claim 11, wherein calculating the search rank results further comprises ranking the first and second documents according to a scoring function (score) that is determined according to at least:
    - the at least one of the click distances associated with each of the first and second documents (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).
  - 18. The method of claim 11 wherein calculating the search rank results further comprises ranking the first and second documents according to a scoring function (score) that is determined according to at least:
    - the at least one of the click distances associated with each of the first and second documents (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).
  - 19. The method of claim 18 wherein the scoring function (score) is given by:
    - $score = \sum \frac{w t f (k_{1} + 1)}{k_{1} ((1 - b) + b \frac{w d l}{a v w d l}) + w t f} \times \log (\frac{N}{n}) + w_{c d} \frac{k_{c d}}{k_{c d} + \frac{b_{c d} C D + b_{u d} U D}{b_{c d} + b_{u d}}} .$
  - 20. The method of claim 11 further comprising:
    - allowing the at least one of the click distances associated with each of the first and second documents to be manually changed.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Microsoft Technology Licensing LLC (Microsoft Corporation)
Original Assignee
Microsoft Corporation
Inventors
Meyerzon, Dmitriy, Zaragoza, Hugo
Primary Examiner(s)
Mofiz; Apu M
Assistant Examiner(s)
Le; Hung D

Application Number

US10/955,983
Publication Number

US 20060074903A1
Time in Patent Office

2,119 Days
Field of Search

None
US Class Current

707/731
CPC Class Codes

G06F 16/951   Indexing; Web crawling tech...

G06F 16/9532   Query formulation

G06F 16/9538   Presentation of query results

System and method for ranking search results using click distance

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

239 Citations

20 Claims

Specification

Solutions

Use Cases

Quick Links

System and method for ranking search results using click distance

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

239 Citations

20 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links