Document (#39561)

Author

Kamvar, S.
Haveliwala, T.
Golub, G.

Title

Adaptive methods for the computation of PageRank

Imprint

Stanford : Stanford University

Year

2003

Pages

13 S

Series

Stanford University Technical Report; April 2003

Abstract

We observe that the convergence patterns of pages in the PageRank algorithm have a nonuniform distribution. Specifically, many pages converge to their true PageRank quickly, while relatively few pages take a much longer time to converge. Furthermore, we observe that these slow-converging pages are generally those pages with high PageRank.We use this observation to devise a simple algorithm to speed up the computation of PageRank, in which the PageRank of pages that have converged are not recomputed at each iteration after convergence. This algorithm, which we call Adaptive PageRank, speeds up the computation of PageRank by nearly 30%.

Content

Accepted for publication by NSMC '03. Vgl. auch: http://infolab.stanford.edu/~taherh/papers/adaptive.pdf.

Theme

Suchmaschinen

Object

PageRank

Similar documents (author)

1. Golub, K.: Automated subject classification of textual web documents (2006) 5.30

   5.298757 = sum of:
     5.298757 = weight(author_txt:golub in 5600) [ClassicSimilarity], result of:
       5.298757 = fieldWeight in 5600, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.478011 = idf(docFreq=24, maxDocs=44218)
         0.625 = fieldNorm(doc=5600)
   

2. Golub, K.: Automated subject classification of textual Web pages, based on a controlled vocabulary : challenges and recommendations (2006) 5.30

   5.298757 = sum of:
     5.298757 = weight(author_txt:golub in 5897) [ClassicSimilarity], result of:
       5.298757 = fieldWeight in 5897, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.478011 = idf(docFreq=24, maxDocs=44218)
         0.625 = fieldNorm(doc=5897)
   

3. Golub, K.: Subject access to information : an interdisciplinary approach (2015) 5.30

   5.298757 = sum of:
     5.298757 = weight(author_txt:golub in 134) [ClassicSimilarity], result of:
       5.298757 = fieldWeight in 134, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.478011 = idf(docFreq=24, maxDocs=44218)
         0.625 = fieldNorm(doc=134)
   

4. Golub, K.: Automated subject classification of textual documents in the context of Web-based hierarchical browsing (2011) 5.30

   5.298757 = sum of:
     5.298757 = weight(author_txt:golub in 4558) [ClassicSimilarity], result of:
       5.298757 = fieldWeight in 4558, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.478011 = idf(docFreq=24, maxDocs=44218)
         0.625 = fieldNorm(doc=4558)
   

5. Golub, K.: Subject access in Swedish discovery services (2018) 5.30

   5.298757 = sum of:
     5.298757 = weight(author_txt:golub in 4379) [ClassicSimilarity], result of:
       5.298757 = fieldWeight in 4379, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.478011 = idf(docFreq=24, maxDocs=44218)
         0.625 = fieldNorm(doc=4379)
   

Similar documents (content)

1. Boldi, P.; Santini, M.; Vigna, S.: PageRank as a function of the damping factor (2005) 0.22

   0.22118346 = sum of:
     0.22118346 = product of:
       1.1059173 = sum of:
         0.00843074 = weight(abstract_txt:that in 2564) [ClassicSimilarity], result of:
           0.00843074 = score(doc=2564,freq=4.0), product of:
             0.028464498 = queryWeight, product of:
               1.1787533 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010191274 = queryNorm
             0.2961844 = fieldWeight in 2564, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0625 = fieldNorm(doc=2564)
         0.07213904 = weight(abstract_txt:iteration in 2564) [ClassicSimilarity], result of:
           0.07213904 = score(doc=2564,freq=1.0), product of:
             0.13106485 = queryWeight, product of:
               1.4603388 = boost
               8.806516 = idf(docFreq=17, maxDocs=44218)
               0.010191274 = queryNorm
             0.55040723 = fieldWeight in 2564, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.806516 = idf(docFreq=17, maxDocs=44218)
               0.0625 = fieldNorm(doc=2564)
         0.08443263 = weight(abstract_txt:convergence in 2564) [ClassicSimilarity], result of:
           0.08443263 = score(doc=2564,freq=1.0), product of:
             0.18339586 = queryWeight, product of:
               2.4429822 = boost
               7.3661537 = idf(docFreq=75, maxDocs=44218)
               0.010191274 = queryNorm
             0.4603846 = fieldWeight in 2564, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.3661537 = idf(docFreq=75, maxDocs=44218)
               0.0625 = fieldNorm(doc=2564)
         0.1451069 = weight(abstract_txt:computation in 2564) [ClassicSimilarity], result of:
           0.1451069 = score(doc=2564,freq=1.0), product of:
             0.30121166 = queryWeight, product of:
               3.834485 = boost
               7.7079034 = idf(docFreq=53, maxDocs=44218)
               0.010191274 = queryNorm
             0.48174396 = fieldWeight in 2564, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.7079034 = idf(docFreq=53, maxDocs=44218)
               0.0625 = fieldNorm(doc=2564)
         0.795808 = weight(abstract_txt:pagerank in 2564) [ClassicSimilarity], result of:
           0.795808 = score(doc=2564,freq=6.0), product of:
             0.68374443 = queryWeight, product of:
               8.824832 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010191274 = queryNorm
             1.1638969 = fieldWeight in 2564, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.0625 = fieldNorm(doc=2564)
       0.2 = coord(5/25)
   

2. Haveliwala, T.; Kamvar, S.: ¬The second eigenvalue of the Google matrix (2003) 0.21

   0.21180268 = sum of:
     0.21180268 = product of:
       1.0590134 = sum of:
         0.029890949 = weight(abstract_txt:furthermore in 2566) [ClassicSimilarity], result of:
           0.029890949 = score(doc=2566,freq=1.0), product of:
             0.06277583 = queryWeight, product of:
               1.0106639 = boost
               6.0947685 = idf(docFreq=270, maxDocs=44218)
               0.010191274 = queryNorm
             0.4761538 = fieldWeight in 2566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.0947685 = idf(docFreq=270, maxDocs=44218)
               0.078125 = fieldNorm(doc=2566)
         0.037801623 = weight(abstract_txt:speed in 2566) [ClassicSimilarity], result of:
           0.037801623 = score(doc=2566,freq=1.0), product of:
             0.073413 = queryWeight, product of:
               1.0929418 = boost
               6.590942 = idf(docFreq=164, maxDocs=44218)
               0.010191274 = queryNorm
             0.5149173 = fieldWeight in 2566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.590942 = idf(docFreq=164, maxDocs=44218)
               0.078125 = fieldNorm(doc=2566)
         0.10554079 = weight(abstract_txt:convergence in 2566) [ClassicSimilarity], result of:
           0.10554079 = score(doc=2566,freq=1.0), product of:
             0.18339586 = queryWeight, product of:
               2.4429822 = boost
               7.3661537 = idf(docFreq=75, maxDocs=44218)
               0.010191274 = queryNorm
             0.57548076 = fieldWeight in 2566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.3661537 = idf(docFreq=75, maxDocs=44218)
               0.078125 = fieldNorm(doc=2566)
         0.07356188 = weight(abstract_txt:algorithm in 2566) [ClassicSimilarity], result of:
           0.07356188 = score(doc=2566,freq=1.0), product of:
             0.16503458 = queryWeight, product of:
               2.8383021 = boost
               5.705423 = idf(docFreq=399, maxDocs=44218)
               0.010191274 = queryNorm
             0.44573617 = fieldWeight in 2566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.705423 = idf(docFreq=399, maxDocs=44218)
               0.078125 = fieldNorm(doc=2566)
         0.8122182 = weight(abstract_txt:pagerank in 2566) [ClassicSimilarity], result of:
           0.8122182 = score(doc=2566,freq=4.0), product of:
             0.68374443 = queryWeight, product of:
               8.824832 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010191274 = queryNorm
             1.1878973 = fieldWeight in 2566, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.078125 = fieldNorm(doc=2566)
       0.2 = coord(5/25)
   

3. Dominich, S.; Skrop, A.: PageRank and interaction information retrieval (2005) 0.20

   0.19647309 = sum of:
     0.19647309 = product of:
       1.2279569 = sum of:
         0.008690009 = weight(abstract_txt:have in 3268) [ClassicSimilarity], result of:
           0.008690009 = score(doc=3268,freq=1.0), product of:
             0.03471012 = queryWeight, product of:
               1.062805 = boost
               3.2046018 = idf(docFreq=4876, maxDocs=44218)
               0.010191274 = queryNorm
             0.2503595 = fieldWeight in 3268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.2046018 = idf(docFreq=4876, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
         0.0052692126 = weight(abstract_txt:that in 3268) [ClassicSimilarity], result of:
           0.0052692126 = score(doc=3268,freq=1.0), product of:
             0.028464498 = queryWeight, product of:
               1.1787533 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010191274 = queryNorm
             0.18511525 = fieldWeight in 3268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
         0.1395341 = weight(abstract_txt:pages in 3268) [ClassicSimilarity], result of:
           0.1395341 = score(doc=3268,freq=1.0), product of:
             0.31861776 = queryWeight, product of:
               5.5772634 = boost
               5.6055775 = idf(docFreq=441, maxDocs=44218)
               0.010191274 = queryNorm
             0.43793574 = fieldWeight in 3268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6055775 = idf(docFreq=441, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
         1.0744636 = weight(abstract_txt:pagerank in 3268) [ClassicSimilarity], result of:
           1.0744636 = score(doc=3268,freq=7.0), product of:
             0.68374443 = queryWeight, product of:
               8.824832 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010191274 = queryNorm
             1.5714405 = fieldWeight in 3268, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.078125 = fieldNorm(doc=3268)
       0.16 = coord(4/25)
   

4. Thelwall, M.: Can Google's PageRank be used to find the most important academic Web pages? (2003) 0.18

   0.18256615 = sum of:
     0.18256615 = product of:
       0.9128307 = sum of:
         0.0069520073 = weight(abstract_txt:have in 4457) [ClassicSimilarity], result of:
           0.0069520073 = score(doc=4457,freq=1.0), product of:
             0.03471012 = queryWeight, product of:
               1.062805 = boost
               3.2046018 = idf(docFreq=4876, maxDocs=44218)
               0.010191274 = queryNorm
             0.20028761 = fieldWeight in 4457, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.2046018 = idf(docFreq=4876, maxDocs=44218)
               0.0625 = fieldNorm(doc=4457)
         0.010325505 = weight(abstract_txt:that in 4457) [ClassicSimilarity], result of:
           0.010325505 = score(doc=4457,freq=6.0), product of:
             0.028464498 = queryWeight, product of:
               1.1787533 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010191274 = queryNorm
             0.36275032 = fieldWeight in 4457, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0625 = fieldNorm(doc=4457)
         0.083225764 = weight(abstract_txt:algorithm in 4457) [ClassicSimilarity], result of:
           0.083225764 = score(doc=4457,freq=2.0), product of:
             0.16503458 = queryWeight, product of:
               2.8383021 = boost
               5.705423 = idf(docFreq=399, maxDocs=44218)
               0.010191274 = queryNorm
             0.5042929 = fieldWeight in 4457, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.705423 = idf(docFreq=399, maxDocs=44218)
               0.0625 = fieldNorm(doc=4457)
         0.24960619 = weight(abstract_txt:pages in 4457) [ClassicSimilarity], result of:
           0.24960619 = score(doc=4457,freq=5.0), product of:
             0.31861776 = queryWeight, product of:
               5.5772634 = boost
               5.6055775 = idf(docFreq=441, maxDocs=44218)
               0.010191274 = queryNorm
             0.7834033 = fieldWeight in 4457, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               5.6055775 = idf(docFreq=441, maxDocs=44218)
               0.0625 = fieldNorm(doc=4457)
         0.56272125 = weight(abstract_txt:pagerank in 4457) [ClassicSimilarity], result of:
           0.56272125 = score(doc=4457,freq=3.0), product of:
             0.68374443 = queryWeight, product of:
               8.824832 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010191274 = queryNorm
             0.8229994 = fieldWeight in 4457, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.0625 = fieldNorm(doc=4457)
       0.2 = coord(5/25)
   

5. Austin, D.: How Google finds your needle in the Web's haystack : as we'll see, the trick is to ask the web itself to rank the importance of pages... (2006) 0.17

   0.16984336 = sum of:
     0.16984336 = product of:
       0.7076807 = sum of:
         0.0043450044 = weight(abstract_txt:have in 93) [ClassicSimilarity], result of:
           0.0043450044 = score(doc=93,freq=1.0), product of:
             0.03471012 = queryWeight, product of:
               1.062805 = boost
               3.2046018 = idf(docFreq=4876, maxDocs=44218)
               0.010191274 = queryNorm
             0.12517975 = fieldWeight in 93, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.2046018 = idf(docFreq=4876, maxDocs=44218)
               0.0390625 = fieldNorm(doc=93)
         0.020285603 = weight(abstract_txt:quickly in 93) [ClassicSimilarity], result of:
           0.020285603 = score(doc=93,freq=1.0), product of:
             0.07695637 = queryWeight, product of:
               1.119007 = boost
               6.7481275 = idf(docFreq=140, maxDocs=44218)
               0.010191274 = queryNorm
             0.26359874 = fieldWeight in 93, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.7481275 = idf(docFreq=140, maxDocs=44218)
               0.0390625 = fieldNorm(doc=93)
         0.009126544 = weight(abstract_txt:that in 93) [ClassicSimilarity], result of:
           0.009126544 = score(doc=93,freq=12.0), product of:
             0.028464498 = queryWeight, product of:
               1.1787533 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.010191274 = queryNorm
             0.320629 = fieldWeight in 93, product of:
               3.4641016 = tf(freq=12.0), with freq of:
                 12.0 = termFreq=12.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0390625 = fieldNorm(doc=93)
         0.052016106 = weight(abstract_txt:algorithm in 93) [ClassicSimilarity], result of:
           0.052016106 = score(doc=93,freq=2.0), product of:
             0.16503458 = queryWeight, product of:
               2.8383021 = boost
               5.705423 = idf(docFreq=399, maxDocs=44218)
               0.010191274 = queryNorm
             0.31518307 = fieldWeight in 93, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.705423 = idf(docFreq=399, maxDocs=44218)
               0.0390625 = fieldNorm(doc=93)
         0.27020663 = weight(abstract_txt:pages in 93) [ClassicSimilarity], result of:
           0.27020663 = score(doc=93,freq=15.0), product of:
             0.31861776 = queryWeight, product of:
               5.5772634 = boost
               5.6055775 = idf(docFreq=441, maxDocs=44218)
               0.010191274 = queryNorm
             0.84805894 = fieldWeight in 93, product of:
               3.8729835 = tf(freq=15.0), with freq of:
                 15.0 = termFreq=15.0
               5.6055775 = idf(docFreq=441, maxDocs=44218)
               0.0390625 = fieldNorm(doc=93)
         0.35170078 = weight(abstract_txt:pagerank in 93) [ClassicSimilarity], result of:
           0.35170078 = score(doc=93,freq=3.0), product of:
             0.68374443 = queryWeight, product of:
               8.824832 = boost
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.010191274 = queryNorm
             0.5143746 = fieldWeight in 93, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.602543 = idf(docFreq=59, maxDocs=44218)
               0.0390625 = fieldNorm(doc=93)
       0.24 = coord(6/25)