Briefs

Stanford researchers published three methods that could collectively boost the speed of Google's Web page rankings by up to a factor of five. The techniques, developed by graduate students Sepandar Kamvar and Taher Haveliwala, together with computer science professor Christopher Manning and numerical analyst Gene Golub, are presented in numerical linear algebra.

The first technique consists of "extrapolation" methods that facilitate a fast, simple computation of Google's Computing PageRank algorithm, even though the methods make a few false assumptions about the Web's link architecture; the researchers have demonstrated that PageRank could be accelerated by 50 percent to 300 percent under certain conditions using extrapolation methods.

The second technique, BlockRank, could realistically speed up PageRank computation by 300 percent. It is based on estimates that roughly 80 percent of the pages on any given Web site directs users to other pages on the same site, which allows the researchers to calculate numerous single-site PageRanks, connect the rankings, and enable the rankings to serve as a jumping-off point for the original PageRank algorithm.

Evidence that PageRank computes rankings for certain pages faster than others forms the basis of the third technique, which is called Adaptive PageRank; the method boosts PageRank computation by as much as 50 percent by omitting superfluous computations associated with pages calculated early in the PageRank process. Kamvar says the biggest speed increases could be yielded by combining the three methods. However, PageRank would be need to be even faster to take personalized rankings into account. The research was backed by the National Science Foundation.

See http://www.newswise.com/articles/2003/5/GOOGLE.NSF.html