Document (#39562)

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.47
    5.4713416 = sum of:
      5.4713416 = weight(author_txt:golub in 601) [ClassicSimilarity], result of:
        5.4713416 = score(doc=601,freq=1.0), product of:
          0.99999994 = queryWeight, product of:
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.114231564 = queryNorm
          5.471342 = fieldWeight in 601, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.625 = fieldNorm(doc=601)
    
  2. Golub, K.: Automated subject classification of textual Web pages, based on a controlled vocabulary : challenges and recommendations (2006) 5.47
    5.4713416 = sum of:
      5.4713416 = weight(author_txt:golub in 898) [ClassicSimilarity], result of:
        5.4713416 = score(doc=898,freq=1.0), product of:
          0.99999994 = queryWeight, product of:
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.114231564 = queryNorm
          5.471342 = fieldWeight in 898, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.625 = fieldNorm(doc=898)
    
  3. Golub, K.: Subject access to information : an interdisciplinary approach (2015) 5.47
    5.4713416 = sum of:
      5.4713416 = weight(author_txt:golub in 2135) [ClassicSimilarity], result of:
        5.4713416 = score(doc=2135,freq=1.0), product of:
          0.99999994 = queryWeight, product of:
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.114231564 = queryNorm
          5.471342 = fieldWeight in 2135, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.625 = fieldNorm(doc=2135)
    
  4. Golub, K.: Automated subject classification of textual documents in the context of Web-based hierarchical browsing (2011) 5.47
    5.4713416 = sum of:
      5.4713416 = weight(author_txt:golub in 1559) [ClassicSimilarity], result of:
        5.4713416 = score(doc=1559,freq=1.0), product of:
          0.99999994 = queryWeight, product of:
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.114231564 = queryNorm
          5.471342 = fieldWeight in 1559, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.625 = fieldNorm(doc=1559)
    
  5. Golub, K.: Subject access in Swedish discovery services (2018) 5.47
    5.4713416 = sum of:
      5.4713416 = weight(author_txt:golub in 944) [ClassicSimilarity], result of:
        5.4713416 = score(doc=944,freq=1.0), product of:
          0.99999994 = queryWeight, product of:
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.114231564 = queryNorm
          5.471342 = fieldWeight in 944, product of:
            1.0 = tf(freq=1.0), with freq of:
              1.0 = termFreq=1.0
            8.754148 = idf(docFreq=17, maxDocs=41962)
            0.625 = fieldNorm(doc=944)
    

Similar documents (content)

  1. Boldi, P.; Santini, M.; Vigna, S.: PageRank as a function of the damping factor (2005) 0.22
    0.2190858 = sum of:
      0.2190858 = product of:
        1.095429 = sum of:
          0.008945587 = weight(abstract_txt:that in 4565) [ClassicSimilarity], result of:
            0.008945587 = score(doc=4565,freq=4.0), product of:
              0.029667541 = queryWeight, product of:
                1.1879824 = boost
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.010352714 = queryNorm
              0.30152777 = fieldWeight in 4565, product of:
                2.0 = tf(freq=4.0), with freq of:
                  4.0 = termFreq=4.0
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.0625 = fieldNorm(doc=4565)
          0.07417545 = weight(abstract_txt:iteration in 4565) [ClassicSimilarity], result of:
            0.07417545 = score(doc=4565,freq=1.0), product of:
              0.133771 = queryWeight, product of:
                1.45643 = boost
                8.871931 = idf(docFreq=15, maxDocs=41962)
                0.010352714 = queryNorm
              0.5544957 = fieldWeight in 4565, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                8.871931 = idf(docFreq=15, maxDocs=41962)
                0.0625 = fieldNorm(doc=4565)
          0.08545344 = weight(abstract_txt:convergence in 4565) [ClassicSimilarity], result of:
            0.08545344 = score(doc=4565,freq=1.0), product of:
              0.18521874 = queryWeight, product of:
                2.4236286 = boost
                7.3818398 = idf(docFreq=70, maxDocs=41962)
                0.010352714 = queryNorm
              0.46136498 = fieldWeight in 4565, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                7.3818398 = idf(docFreq=70, maxDocs=41962)
                0.0625 = fieldNorm(doc=4565)
          0.14297287 = weight(abstract_txt:computation in 4565) [ClassicSimilarity], result of:
            0.14297287 = score(doc=4565,freq=1.0), product of:
              0.298812 = queryWeight, product of:
                3.7702336 = boost
                7.6555357 = idf(docFreq=53, maxDocs=41962)
                0.010352714 = queryNorm
              0.47847098 = fieldWeight in 4565, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                7.6555357 = idf(docFreq=53, maxDocs=41962)
                0.0625 = fieldNorm(doc=4565)
          0.7838816 = weight(abstract_txt:pagerank in 4565) [ClassicSimilarity], result of:
            0.7838816 = score(doc=4565,freq=6.0), product of:
              0.6781688 = queryWeight, product of:
                8.67614 = boost
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.010352714 = queryNorm
              1.1558799 = fieldWeight in 4565, product of:
                2.4494898 = tf(freq=6.0), with freq of:
                  6.0 = termFreq=6.0
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.0625 = fieldNorm(doc=4565)
        0.2 = coord(5/25)
    
  2. Haveliwala, T.; Kamvar, S.: ¬The second eigenvalue of the Google matrix (2003) 0.21
    0.2102798 = sum of:
      0.2102798 = product of:
        1.051399 = sum of:
          0.031809572 = weight(abstract_txt:furthermore in 4567) [ClassicSimilarity], result of:
            0.031809572 = score(doc=4567,freq=1.0), product of:
              0.065557204 = queryWeight, product of:
                1.0195742 = boost
                6.210798 = idf(docFreq=228, maxDocs=41962)
                0.010352714 = queryNorm
              0.48521858 = fieldWeight in 4567, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.210798 = idf(docFreq=228, maxDocs=41962)
                0.078125 = fieldNorm(doc=4567)
          0.037642814 = weight(abstract_txt:speed in 4567) [ClassicSimilarity], result of:
            0.037642814 = score(doc=4567,freq=1.0), product of:
              0.0733449 = queryWeight, product of:
                1.078434 = boost
                6.569346 = idf(docFreq=159, maxDocs=41962)
                0.010352714 = queryNorm
              0.51323014 = fieldWeight in 4567, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.569346 = idf(docFreq=159, maxDocs=41962)
                0.078125 = fieldNorm(doc=4567)
          0.1068168 = weight(abstract_txt:convergence in 4567) [ClassicSimilarity], result of:
            0.1068168 = score(doc=4567,freq=1.0), product of:
              0.18521874 = queryWeight, product of:
                2.4236286 = boost
                7.3818398 = idf(docFreq=70, maxDocs=41962)
                0.010352714 = queryNorm
              0.57670623 = fieldWeight in 4567, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                7.3818398 = idf(docFreq=70, maxDocs=41962)
                0.078125 = fieldNorm(doc=4567)
          0.07508395 = weight(abstract_txt:algorithm in 4567) [ClassicSimilarity], result of:
            0.07508395 = score(doc=4567,freq=1.0), product of:
              0.16761789 = queryWeight, product of:
                2.8237708 = boost
                5.733723 = idf(docFreq=368, maxDocs=41962)
                0.010352714 = queryNorm
              0.4479471 = fieldWeight in 4567, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                5.733723 = idf(docFreq=368, maxDocs=41962)
                0.078125 = fieldNorm(doc=4567)
          0.80004585 = weight(abstract_txt:pagerank in 4567) [ClassicSimilarity], result of:
            0.80004585 = score(doc=4567,freq=4.0), product of:
              0.6781688 = queryWeight, product of:
                8.67614 = boost
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.010352714 = queryNorm
              1.1797149 = fieldWeight in 4567, product of:
                2.0 = tf(freq=4.0), with freq of:
                  4.0 = termFreq=4.0
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.078125 = fieldNorm(doc=4567)
        0.2 = coord(5/25)
    
  3. Dominich, S.; Skrop, A.: PageRank and interaction information retrieval (2005) 0.19
    0.19387299 = sum of:
      0.19387299 = product of:
        1.2117062 = sum of:
          0.009115368 = weight(abstract_txt:have in 4269) [ClassicSimilarity], result of:
            0.009115368 = score(doc=4269,freq=1.0), product of:
              0.03590112 = queryWeight, product of:
                1.0670325 = boost
                3.2499464 = idf(docFreq=4422, maxDocs=41962)
                0.010352714 = queryNorm
              0.25390205 = fieldWeight in 4269, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                3.2499464 = idf(docFreq=4422, maxDocs=41962)
                0.078125 = fieldNorm(doc=4269)
          0.005590992 = weight(abstract_txt:that in 4269) [ClassicSimilarity], result of:
            0.005590992 = score(doc=4269,freq=1.0), product of:
              0.029667541 = queryWeight, product of:
                1.1879824 = boost
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.010352714 = queryNorm
              0.18845485 = fieldWeight in 4269, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.078125 = fieldNorm(doc=4269)
          0.13863869 = weight(abstract_txt:pages in 4269) [ClassicSimilarity], result of:
            0.13863869 = score(doc=4269,freq=1.0), product of:
              0.31784979 = queryWeight, product of:
                5.499145 = boost
                5.5830626 = idf(docFreq=428, maxDocs=41962)
                0.010352714 = queryNorm
              0.43617678 = fieldWeight in 4269, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                5.5830626 = idf(docFreq=428, maxDocs=41962)
                0.078125 = fieldNorm(doc=4269)
          1.058361 = weight(abstract_txt:pagerank in 4269) [ClassicSimilarity], result of:
            1.058361 = score(doc=4269,freq=7.0), product of:
              0.6781688 = queryWeight, product of:
                8.67614 = boost
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.010352714 = queryNorm
              1.560616 = fieldWeight in 4269, product of:
                2.6457512 = tf(freq=7.0), with freq of:
                  7.0 = termFreq=7.0
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.078125 = fieldNorm(doc=4269)
        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.18109772 = sum of:
      0.18109772 = product of:
        0.90548855 = sum of:
          0.007292295 = weight(abstract_txt:have in 458) [ClassicSimilarity], result of:
            0.007292295 = score(doc=458,freq=1.0), product of:
              0.03590112 = queryWeight, product of:
                1.0670325 = boost
                3.2499464 = idf(docFreq=4422, maxDocs=41962)
                0.010352714 = queryNorm
              0.20312165 = fieldWeight in 458, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                3.2499464 = idf(docFreq=4422, maxDocs=41962)
                0.0625 = fieldNorm(doc=458)
          0.010956063 = weight(abstract_txt:that in 458) [ClassicSimilarity], result of:
            0.010956063 = score(doc=458,freq=6.0), product of:
              0.029667541 = queryWeight, product of:
                1.1879824 = boost
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.010352714 = queryNorm
              0.3692946 = fieldWeight in 458, product of:
                2.4494898 = tf(freq=6.0), with freq of:
                  6.0 = termFreq=6.0
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.0625 = fieldNorm(doc=458)
          0.084947795 = weight(abstract_txt:algorithm in 458) [ClassicSimilarity], result of:
            0.084947795 = score(doc=458,freq=2.0), product of:
              0.16761789 = queryWeight, product of:
                2.8237708 = boost
                5.733723 = idf(docFreq=368, maxDocs=41962)
                0.010352714 = queryNorm
              0.50679433 = fieldWeight in 458, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                5.733723 = idf(docFreq=368, maxDocs=41962)
                0.0625 = fieldNorm(doc=458)
          0.24800444 = weight(abstract_txt:pages in 458) [ClassicSimilarity], result of:
            0.24800444 = score(doc=458,freq=5.0), product of:
              0.31784979 = queryWeight, product of:
                5.499145 = boost
                5.5830626 = idf(docFreq=428, maxDocs=41962)
                0.010352714 = queryNorm
              0.78025675 = fieldWeight in 458, product of:
                2.236068 = tf(freq=5.0), with freq of:
                  5.0 = termFreq=5.0
                5.5830626 = idf(docFreq=428, maxDocs=41962)
                0.0625 = fieldNorm(doc=458)
          0.55428797 = weight(abstract_txt:pagerank in 458) [ClassicSimilarity], result of:
            0.55428797 = score(doc=458,freq=3.0), product of:
              0.6781688 = queryWeight, product of:
                8.67614 = boost
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.010352714 = queryNorm
              0.8173304 = fieldWeight in 458, product of:
                1.7320508 = tf(freq=3.0), with freq of:
                  3.0 = termFreq=3.0
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.0625 = fieldNorm(doc=458)
        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.16869593 = sum of:
      0.16869593 = product of:
        0.7028997 = sum of:
          0.004557684 = weight(abstract_txt:have in 1219) [ClassicSimilarity], result of:
            0.004557684 = score(doc=1219,freq=1.0), product of:
              0.03590112 = queryWeight, product of:
                1.0670325 = boost
                3.2499464 = idf(docFreq=4422, maxDocs=41962)
                0.010352714 = queryNorm
              0.12695102 = fieldWeight in 1219, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                3.2499464 = idf(docFreq=4422, maxDocs=41962)
                0.0390625 = fieldNorm(doc=1219)
          0.020663092 = weight(abstract_txt:quickly in 1219) [ClassicSimilarity], result of:
            0.020663092 = score(doc=1219,freq=1.0), product of:
              0.078054644 = queryWeight, product of:
                1.1125205 = boost
                6.776985 = idf(docFreq=129, maxDocs=41962)
                0.010352714 = queryNorm
              0.26472598 = fieldWeight in 1219, product of:
                1.0 = tf(freq=1.0), with freq of:
                  1.0 = termFreq=1.0
                6.776985 = idf(docFreq=129, maxDocs=41962)
                0.0390625 = fieldNorm(doc=1219)
          0.009683882 = weight(abstract_txt:that in 1219) [ClassicSimilarity], result of:
            0.009683882 = score(doc=1219,freq=12.0), product of:
              0.029667541 = queryWeight, product of:
                1.1879824 = boost
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.010352714 = queryNorm
              0.32641336 = fieldWeight in 1219, product of:
                3.4641016 = tf(freq=12.0), with freq of:
                  12.0 = termFreq=12.0
                2.4122221 = idf(docFreq=10221, maxDocs=41962)
                0.0390625 = fieldNorm(doc=1219)
          0.053092375 = weight(abstract_txt:algorithm in 1219) [ClassicSimilarity], result of:
            0.053092375 = score(doc=1219,freq=2.0), product of:
              0.16761789 = queryWeight, product of:
                2.8237708 = boost
                5.733723 = idf(docFreq=368, maxDocs=41962)
                0.010352714 = queryNorm
              0.31674647 = fieldWeight in 1219, product of:
                1.4142135 = tf(freq=2.0), with freq of:
                  2.0 = termFreq=2.0
                5.733723 = idf(docFreq=368, maxDocs=41962)
                0.0390625 = fieldNorm(doc=1219)
          0.26847267 = weight(abstract_txt:pages in 1219) [ClassicSimilarity], result of:
            0.26847267 = score(doc=1219,freq=15.0), product of:
              0.31784979 = queryWeight, product of:
                5.499145 = boost
                5.5830626 = idf(docFreq=428, maxDocs=41962)
                0.010352714 = queryNorm
              0.8446527 = fieldWeight in 1219, product of:
                3.8729835 = tf(freq=15.0), with freq of:
                  15.0 = termFreq=15.0
                5.5830626 = idf(docFreq=428, maxDocs=41962)
                0.0390625 = fieldNorm(doc=1219)
          0.34643 = weight(abstract_txt:pagerank in 1219) [ClassicSimilarity], result of:
            0.34643 = score(doc=1219,freq=3.0), product of:
              0.6781688 = queryWeight, product of:
                8.67614 = boost
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.010352714 = queryNorm
              0.51083153 = fieldWeight in 1219, product of:
                1.7320508 = tf(freq=3.0), with freq of:
                  3.0 = termFreq=3.0
                7.550175 = idf(docFreq=59, maxDocs=41962)
                0.0390625 = fieldNorm(doc=1219)
        0.24 = coord(6/25)