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.28

   5.277107 = sum of:
     5.277107 = weight(author_txt:golub in 600) [ClassicSimilarity], result of:
       5.277107 = fieldWeight in 600, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.443371 = idf(docFreq=25, maxDocs=44421)
         0.625 = fieldNorm(doc=600)
   

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

   5.277107 = sum of:
     5.277107 = weight(author_txt:golub in 897) [ClassicSimilarity], result of:
       5.277107 = fieldWeight in 897, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.443371 = idf(docFreq=25, maxDocs=44421)
         0.625 = fieldNorm(doc=897)
   

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

   5.277107 = sum of:
     5.277107 = weight(author_txt:golub in 1134) [ClassicSimilarity], result of:
       5.277107 = fieldWeight in 1134, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.443371 = idf(docFreq=25, maxDocs=44421)
         0.625 = fieldNorm(doc=1134)
   

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

   5.277107 = sum of:
     5.277107 = weight(author_txt:golub in 558) [ClassicSimilarity], result of:
       5.277107 = fieldWeight in 558, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.443371 = idf(docFreq=25, maxDocs=44421)
         0.625 = fieldNorm(doc=558)
   

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

   5.277107 = sum of:
     5.277107 = weight(author_txt:golub in 379) [ClassicSimilarity], result of:
       5.277107 = fieldWeight in 379, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.443371 = idf(docFreq=25, maxDocs=44421)
         0.625 = fieldNorm(doc=379)
   

Similar documents (content)

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

   0.2212758 = sum of:
     0.2212758 = product of:
       1.106379 = sum of:
         0.008381342 = weight(abstract_txt:that in 3564) [ClassicSimilarity], result of:
           0.008381342 = score(doc=3564,freq=4.0), product of:
             0.028352037 = queryWeight, product of:
               1.1769469 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.010186105 = queryNorm
             0.2956169 = fieldWeight in 3564, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.0625 = fieldNorm(doc=3564)
         0.070921 = weight(abstract_txt:iteration in 3564) [ClassicSimilarity], result of:
           0.070921 = score(doc=3564,freq=1.0), product of:
             0.12958002 = queryWeight, product of:
               1.4526906 = boost
               8.757029 = idf(docFreq=18, maxDocs=44421)
               0.010186105 = queryNorm
             0.5473143 = fieldWeight in 3564, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.757029 = idf(docFreq=18, maxDocs=44421)
               0.0625 = fieldNorm(doc=3564)
         0.084579825 = weight(abstract_txt:convergence in 3564) [ClassicSimilarity], result of:
           0.084579825 = score(doc=3564,freq=1.0), product of:
             0.18360141 = queryWeight, product of:
               2.4454405 = boost
               7.370734 = idf(docFreq=75, maxDocs=44421)
               0.010186105 = queryNorm
             0.4606709 = fieldWeight in 3564, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.370734 = idf(docFreq=75, maxDocs=44421)
               0.0625 = fieldNorm(doc=3564)
         0.14534782 = weight(abstract_txt:computation in 3564) [ClassicSimilarity], result of:
           0.14534782 = score(doc=3564,freq=1.0), product of:
             0.3015326 = queryWeight, product of:
               3.8382378 = boost
               7.7124834 = idf(docFreq=53, maxDocs=44421)
               0.010186105 = queryNorm
             0.4820302 = fieldWeight in 3564, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.7124834 = idf(docFreq=53, maxDocs=44421)
               0.0625 = fieldNorm(doc=3564)
         0.797149 = weight(abstract_txt:pagerank in 3564) [ClassicSimilarity], result of:
           0.797149 = score(doc=3564,freq=6.0), product of:
             0.6844842 = queryWeight, product of:
               8.833541 = boost
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.010186105 = queryNorm
             1.1645981 = fieldWeight in 3564, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.0625 = fieldNorm(doc=3564)
       0.2 = coord(5/25)
   

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

   0.21201928 = sum of:
     0.21201928 = product of:
       1.0600964 = sum of:
         0.029475918 = weight(abstract_txt:furthermore in 3566) [ClassicSimilarity], result of:
           0.029475918 = score(doc=3566,freq=1.0), product of:
             0.062190834 = queryWeight, product of:
               1.0063922 = boost
               6.066678 = idf(docFreq=279, maxDocs=44421)
               0.010186105 = queryNorm
             0.4739592 = fieldWeight in 3566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.066678 = idf(docFreq=279, maxDocs=44421)
               0.078125 = fieldNorm(doc=3566)
         0.037771825 = weight(abstract_txt:speed in 3566) [ClassicSimilarity], result of:
           0.037771825 = score(doc=3566,freq=1.0), product of:
             0.0733714 = queryWeight, product of:
               1.0931191 = boost
               6.58948 = idf(docFreq=165, maxDocs=44421)
               0.010186105 = queryNorm
             0.5148031 = fieldWeight in 3566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.58948 = idf(docFreq=165, maxDocs=44421)
               0.078125 = fieldNorm(doc=3566)
         0.10572478 = weight(abstract_txt:convergence in 3566) [ClassicSimilarity], result of:
           0.10572478 = score(doc=3566,freq=1.0), product of:
             0.18360141 = queryWeight, product of:
               2.4454405 = boost
               7.370734 = idf(docFreq=75, maxDocs=44421)
               0.010186105 = queryNorm
             0.5758386 = fieldWeight in 3566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.370734 = idf(docFreq=75, maxDocs=44421)
               0.078125 = fieldNorm(doc=3566)
         0.073537074 = weight(abstract_txt:algorithm in 3566) [ClassicSimilarity], result of:
           0.073537074 = score(doc=3566,freq=1.0), product of:
             0.16499071 = queryWeight, product of:
               2.83919 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.010186105 = queryNorm
             0.44570434 = fieldWeight in 3566, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.078125 = fieldNorm(doc=3566)
         0.8135868 = weight(abstract_txt:pagerank in 3566) [ClassicSimilarity], result of:
           0.8135868 = score(doc=3566,freq=4.0), product of:
             0.6844842 = queryWeight, product of:
               8.833541 = boost
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.010186105 = queryNorm
             1.1886129 = fieldWeight in 3566, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.078125 = fieldNorm(doc=3566)
       0.2 = coord(5/25)
   

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

   0.19674894 = sum of:
     0.19674894 = product of:
       1.2296809 = sum of:
         0.008646598 = weight(abstract_txt:have in 4268) [ClassicSimilarity], result of:
           0.008646598 = score(doc=4268,freq=1.0), product of:
             0.03459301 = queryWeight, product of:
               1.0614835 = boost
               3.199388 = idf(docFreq=4924, maxDocs=44421)
               0.010186105 = queryNorm
             0.2499522 = fieldWeight in 4268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.199388 = idf(docFreq=4924, maxDocs=44421)
               0.078125 = fieldNorm(doc=4268)
         0.005238338 = weight(abstract_txt:that in 4268) [ClassicSimilarity], result of:
           0.005238338 = score(doc=4268,freq=1.0), product of:
             0.028352037 = queryWeight, product of:
               1.1769469 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.010186105 = queryNorm
             0.18476056 = fieldWeight in 4268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.078125 = fieldNorm(doc=4268)
         0.13952182 = weight(abstract_txt:pages in 4268) [ClassicSimilarity], result of:
           0.13952182 = score(doc=4268,freq=1.0), product of:
             0.31858596 = queryWeight, product of:
               5.579471 = boost
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.010186105 = queryNorm
             0.4379409 = fieldWeight in 4268, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.078125 = fieldNorm(doc=4268)
         1.0762742 = weight(abstract_txt:pagerank in 4268) [ClassicSimilarity], result of:
           1.0762742 = score(doc=4268,freq=7.0), product of:
             0.6844842 = queryWeight, product of:
               8.833541 = boost
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.010186105 = queryNorm
             1.5723871 = fieldWeight in 4268, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.078125 = fieldNorm(doc=4268)
       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.18272673 = sum of:
     0.18272673 = product of:
       0.91363364 = sum of:
         0.0069172787 = weight(abstract_txt:have in 5457) [ClassicSimilarity], result of:
           0.0069172787 = score(doc=5457,freq=1.0), product of:
             0.03459301 = queryWeight, product of:
               1.0614835 = boost
               3.199388 = idf(docFreq=4924, maxDocs=44421)
               0.010186105 = queryNorm
             0.19996175 = fieldWeight in 5457, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.199388 = idf(docFreq=4924, maxDocs=44421)
               0.0625 = fieldNorm(doc=5457)
         0.010265006 = weight(abstract_txt:that in 5457) [ClassicSimilarity], result of:
           0.010265006 = score(doc=5457,freq=6.0), product of:
             0.028352037 = queryWeight, product of:
               1.1769469 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.010186105 = queryNorm
             0.3620553 = fieldWeight in 5457, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.0625 = fieldNorm(doc=5457)
         0.083197705 = weight(abstract_txt:algorithm in 5457) [ClassicSimilarity], result of:
           0.083197705 = score(doc=5457,freq=2.0), product of:
             0.16499071 = queryWeight, product of:
               2.83919 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.010186105 = queryNorm
             0.5042569 = fieldWeight in 5457, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0625 = fieldNorm(doc=5457)
         0.24958421 = weight(abstract_txt:pages in 5457) [ClassicSimilarity], result of:
           0.24958421 = score(doc=5457,freq=5.0), product of:
             0.31858596 = queryWeight, product of:
               5.579471 = boost
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.010186105 = queryNorm
             0.78341246 = fieldWeight in 5457, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.0625 = fieldNorm(doc=5457)
         0.56366944 = weight(abstract_txt:pagerank in 5457) [ClassicSimilarity], result of:
           0.56366944 = score(doc=5457,freq=3.0), product of:
             0.6844842 = queryWeight, product of:
               8.833541 = boost
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.010186105 = queryNorm
             0.8234952 = fieldWeight in 5457, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.0625 = fieldNorm(doc=5457)
       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.1699365 = sum of:
     0.1699365 = product of:
       0.7080687 = sum of:
         0.004323299 = weight(abstract_txt:have in 218) [ClassicSimilarity], result of:
           0.004323299 = score(doc=218,freq=1.0), product of:
             0.03459301 = queryWeight, product of:
               1.0614835 = boost
               3.199388 = idf(docFreq=4924, maxDocs=44421)
               0.010186105 = queryNorm
             0.1249761 = fieldWeight in 218, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.199388 = idf(docFreq=4924, maxDocs=44421)
               0.0390625 = fieldNorm(doc=218)
         0.020197522 = weight(abstract_txt:quickly in 218) [ClassicSimilarity], result of:
           0.020197522 = score(doc=218,freq=1.0), product of:
             0.076730296 = queryWeight, product of:
               1.1178603 = boost
               6.738623 = idf(docFreq=142, maxDocs=44421)
               0.010186105 = queryNorm
             0.26322746 = fieldWeight in 218, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.738623 = idf(docFreq=142, maxDocs=44421)
               0.0390625 = fieldNorm(doc=218)
         0.009073067 = weight(abstract_txt:that in 218) [ClassicSimilarity], result of:
           0.009073067 = score(doc=218,freq=12.0), product of:
             0.028352037 = queryWeight, product of:
               1.1769469 = boost
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.010186105 = queryNorm
             0.32001466 = fieldWeight in 218, product of:
               3.4641016 = tf(freq=12.0), with freq of:
                 12.0 = termFreq=12.0
               2.3649352 = idf(docFreq=11344, maxDocs=44421)
               0.0390625 = fieldNorm(doc=218)
         0.051998567 = weight(abstract_txt:algorithm in 218) [ClassicSimilarity], result of:
           0.051998567 = score(doc=218,freq=2.0), product of:
             0.16499071 = queryWeight, product of:
               2.83919 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.010186105 = queryNorm
             0.31516057 = fieldWeight in 218, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0390625 = fieldNorm(doc=218)
         0.27018285 = weight(abstract_txt:pages in 218) [ClassicSimilarity], result of:
           0.27018285 = score(doc=218,freq=15.0), product of:
             0.31858596 = queryWeight, product of:
               5.579471 = boost
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.010186105 = queryNorm
             0.8480689 = fieldWeight in 218, product of:
               3.8729835 = tf(freq=15.0), with freq of:
                 15.0 = termFreq=15.0
               5.6056433 = idf(docFreq=443, maxDocs=44421)
               0.0390625 = fieldNorm(doc=218)
         0.3522934 = weight(abstract_txt:pagerank in 218) [ClassicSimilarity], result of:
           0.3522934 = score(doc=218,freq=3.0), product of:
             0.6844842 = queryWeight, product of:
               8.833541 = boost
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.010186105 = queryNorm
             0.5146845 = fieldWeight in 218, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.607123 = idf(docFreq=59, maxDocs=44421)
               0.0390625 = fieldNorm(doc=218)
       0.24 = coord(6/25)