About the series
Lecturer: Professor Gene Golub, Fletcher Jones Professor of Computer Science Stanford University Member of National Academy of Engineering and National Academy of Sciences
Google's PageRank algorithm for web search involves computing the principal eigenvector of a stochastic matrix describing the hyperlink structure of the World Wide Web. Since the web is a highly dynamic structure, with new pages constantly being added or removed, the update problem is an important problem in web search. We address the problem of efficiently recomputing the principal eigenvector of the web hyperlink matrix after small perturbations in the link structure of the web.
We present an algorithm that is motivated by the empirical observation that the convergence patterns of web 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. This algorithm, called Adaptive PageRank, avoids redundant computations associated with the PageRanks of pages that have already converged.
We show empirically that Adaptive PageRank speeds up the computation of PageRank even in the standard case, and that is much more effective in the context of updates.
Prof. Gene H. Golub received his Ph.D. from University of Illinois in 1959. After an NSF Fellowship at the University of Cambridge and an industrial position, he joined the faculty of Stanford University in 1962. He is currently Fletcher Jones Professor of Computer Science and Scientific Computing and Computational Mathematics (SCCM) Program at Stanford University. He served as chairman of the computer science department at Stanford 1981-1984 and the founding director of the SCCM at Stanford 1988-1998. He has received numerous awards honorary degrees and a member of National Academy of Engineering and National Academy of Sciences.
Prof. Golub is noted for his work in the use of numerical methods in linear algebra for solving scientific and engineering problems. This work has resulted in a book, Matrix Computations, co-authored with Charles Van Loan. Prof. Golub has served as President of the Society of Industrial and Applied Mathematics (1985-87). He is the founding editor of two SIAM journals: The SIAM Journal of Scientific and Statistical Computing and The SIAM Journal of Matrix Analysis and Applications. He is the originator of na-net.
For information, please contact Haesun Park, CISE/CCF, 703-292-7096, hpark@nsf.gov
Google's PageRank algorithm for web search involves computing the principal eigenvector of a stochastic matrix describing the hyperlink structure of the World Wide Web. Since the web is a highly dynamic structure, with new pages constantly being added or removed, the update problem is an important problem in web search. We address the problem of efficiently recomputing the principal eigenvector of the web hyperlink matrix after small perturbations in the link structure of the web.
We present an algorithm that is motivated by the empirical observation that the convergence patterns of web 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. This algorithm, called Adaptive PageRank, avoids redundant computations associated with the PageRanks of pages that have already converged.
We show empirically that Adaptive PageRank speeds up the computation of PageRank even in the standard case, and that is much more effective in the context of updates.
Prof. Gene H. Golub received his Ph.D. from University of Illinois in 1959. After an NSF Fellowship at the University of Cambridge and an industrial position, he joined the faculty of Stanford University in 1962. He is currently Fletcher Jones Professor of Computer Science and Scientific Computing and Computational Mathematics (SCCM) Program at Stanford University. He served as chairman of the computer science department at Stanford 1981-1984 and the founding director of the SCCM at Stanford 1988-1998. He has received numerous awards honorary degrees and a member of National Academy of Engineering and National Academy of Sciences.
Prof. Golub is noted for his work in the use of numerical methods in linear algebra for solving scientific and engineering problems. This work has resulted in a book, Matrix Computations, co-authored with Charles Van Loan. Prof. Golub has served as President of the Society of Industrial and Applied Mathematics (1985-87). He is the founding editor of two SIAM journals: The SIAM Journal of Scientific and Statistical Computing and The SIAM Journal of Matrix Analysis and Applications. He is the originator of na-net.
For information, please contact Haesun Park, CISE/CCF, 703-292-7096, hpark@nsf.gov
