Calculating global importance of documents based on global hitting times

Abstract

A calculate importance system calculates the global importance of a web page based on a “mean hitting time.” Hitting time of a target web page is a measure of the minimum number of transitions needed to land on the target web page. Mean hitting time of a target web page is an average number of such transitions for all possible starting web pages. The calculate importance system calculates a global importance score for a web page based on the reciprocal of a mean hitting time. A search engine may rank web pages of a search result based on a combination of relevance of the web pages to the search request and global importance of the web pages based on a global hitting time.

1 .- 20 . (canceled) 
     
     
         21 . A method in a computing device for generating an importance score for documents having links between the documents, the method comprising:
 providing an initial probability distribution for each document;   providing a transition probabilities indicating the probability of transitioning between documents; and   for each document,
 calculating by the computing device a probability of starting from and returning to that document after a number of transitions based on the initial probability distribution and the transition probabilities; and 
 setting the importance score of the document based on the calculated probability. 
   
     
     
         22 . The method of  claim 21  wherein the calculating of the probability includes multiplying the transition probabilities by themselves the number of times. 
     
     
         23 . The method of  claim 21  wherein the calculating of the probability includes using a random sampling technique. 
     
     
         24 . The method of  claim 21  wherein the documents are web pages and the web pages are ranked at least in part based on the importance scores. 
     
     
         25 . The method of  claim 24  wherein the web pages are search results of a search request and the web pages are ranked at least in part based on relevance of the web pages to the search request. 
     
     
         26 . The method of  claim 21  wherein the initial probability distribution is based on a stationary distribution of the transition probabilities. 
     
     
         27 . The method of  claim 21  wherein the initial probability distribution is uniform. 
     
     
         28 . The method of  claim 21  wherein the initial probability distribution is zero for documents considered to be spam. 
     
     
         29 . The method of  claim 21  wherein the initial probability distribution is personalized to a user. 
     
     
         30 . The method of  claim 21  wherein the transition probabilities represent the probabilities of using the links to transition between documents. 
     
     
         31 . The method of  claim 21  wherein the transition probabilities represents the probability of using the links to transition between documents. 
     
     
         32 . A computer-readable storage device encoded with instructions for controlling a computing device to rank web pages, by a method comprising:
 generating importance scores for web pages that are based on a mean hitting time for the web pages, the mean hitting time for a target web page being based on an average of hitting times of transitioning from starting web pages to the target web page; and   ranking the web pages based at least in part on the importance scores of the web pages.   
     
     
         33 . The computer-readable storage device of  claim 32  wherein the mean hitting time is based on an initial probability distribution of the starting web pages that is derived from a stationary probability of transition probabilities of the web pages. 
     
     
         34 . The computer-readable storage device of  claim 32  wherein the mean hitting time is based on an initial probability distribution of starting pages that is user-specific. 
     
     
         35 . The computer-readable storage device of  claim 32  wherein web pages that are ranked are search results of a search request. 
     
     
         36 . The computer-readable storage device of  claim 32  wherein the web pages are further ranked based on relevance of a web page to the search request. 
     
     
         37 . A computing system for ranking documents, comprising:
 an importance store having importance scores for documents, the importance score for a document based on a global hitting time, the global hitting time for a target document being based on number of transitions from a starting document to land on the target document;   a memory storing computer-executable instructions of:
 a component that identifies documents of a search result for a search request; 
 a component that determines relevance of each identified document to the search request; and 
 a component that ranks the identified documents based at least in part on the importance score of the documents and the relevance of the documents to the search request; and 
   a processor that executes the computer-executable instructions stored in the memory.   
     
     
         38 . The computing device of  claim 37  wherein the global hitting time is based on an initial probability distribution of the starting documents that is derived from a stationary probability of transition probabilities of the documents. 
     
     
         39 . The computing device of  claim 38  wherein the global hitting time is a mean hitting time. 
     
     
         40 . The computing device of  claim 38  wherein the documents are web pages and a transition includes following a link from one web page to another web page.