Researchers at Stanford University have developed several new techniques that together may make it possible to calculate Web page rankings as used in the Google search engine up to five times faster. The speed-ups to Google's method may make it realistic to calculate page rankings personalized for an individual's interests or customized to a particular topic.
Computing PageRank, the ranking algorithm behind the Google search engine, for a billion Web pages can take several days. Google currently ranks and searches 3 billion Web pages. Each personalized or topic-sensitive ranking would require a separate multi-day computation, but the payoff would be less time spent wading through irrelevant search results.
To speed up PageRank, the Stanford team developed a trio of techniques in numerical linear algebra ('extrapolation' methods, 'BlockRank,' and 'Adaptive PageRank.') "Further speed-ups are possible when we use all these methods," Kamvar said. "Our preliminary experiments show that combining the methods will make the computation of PageRank up to a factor of five faster. However, there are still several issues to be solved. We're closer to a topic-based PageRank than to a personalized ranking."
The faster method will not affect how quickly Google presents results to users' searches, because the rankings are computed in advance and not at the time a search is requested.
The Stanford team includes graduate students Sepandar Kamvar and Taher Haveliwala, noted numerical analyst Gene Golub and computer science professor Christopher Manning. The work was supported by the National Science Foundation. >from *Researchers Develop Techniques for Computing Google-Style Web Rankings Up to Five Times Faster. Speed-up may make 'topic-sensitive' page rankings feasible*. may 13, 2003
> the anatomy of a large-scale hypertextual web search engine by sergey brin and lawrence page. "in this paper, we present google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext."
> the google cluster architecture by luiz andré barroso, jeffrey dean and urs hölzle. IEEE Micro, march-april, 2003
> exploiting the block structure of the web for computing pagerank by taher haveliwala and sepandar kamvar.
> the second eigenvalue of the google matrix by taher haveliwala and sepandar kamvar.
> word burstiness: scanning online trends. march 7, 2003
> arnold schönberg: music production by algorithms