Google 5X Faster?
Web Design & Technology News, May 27, 2003

May 27, 2003

Users of the Google search engine like it because it's fast, but a team at Stanford University has come up with ways to make it up to five times faster.
Winston Chai

With the extra speed, Google could be tailored for each user, according to the team. For example, a sports-loving Google user looking for "tiger" will see pages only on golfer Tiger Woods, not large felines from Asia.

At present, Google's ranking system relies on a method called PageRank, an invention of co-founder Larry Page which calculates the popularity and relevance of Web sites based on how many other sites link to it.

"Computing PageRank for aB Web pages can take several days. Google currently ranks and searches threeB Web pages and each personalized or topic-sensitive ranking would also require a separate multi-day computation," the university said in a statement.

To speed up PageRank, Stanford researchers have developed a trio of techniques based on a branch of mathematics called numerical linear algebra. These methods are described in three papers.

The first method from the Stanford team, BlockRank, offers the most significant gain, speeding up PageRank by three times, they claim.

The researchers make use of their discovery that on most sites, up to 80 percent of links point to other pages on the same site--each site looks like a thick block of links.

PageRank processes each link individually, but with their more efficient BlockRank method, these same-site links are processed as a unit, before moving on to links outside the site.

The second method involves the use of extrapolation. Before scanning the Web, certain assumptions about a site's importance are drawn up.

As the scanning continues, these assumptions are either proven or disproved, with the accuracy increasing as more links are processed. A site's rank is extrapolated--guessed at--when a reasonable amount of evidence is acquired. Compared with PageRank, which only knows a site's rank after exhaustively trawling the Web, extrapolation works 50 percent faster, say the researchers.

The third method, called Adaptive PageRank, relies on the fact that lower-ranking sites tend to be computed faster than higher-ranking ones. By dropping further processing of such quickly-computed sites, a speed boost of up to 50 percent can be won, they said.

While these methods have their individual merits, the Stanford team believes they can offer even greater returns when combined.

"Further speed-ups are possible when we use all these methods," said Sepandar Kamvar, one of the members of this project. "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," he added.

The Stanford team's theories will remain theories for now--they don't appear to have any official ties to Google itself.

"Google appreciates any contributions that further the study of hyperlink analysis on the web," was a spokesman's reply to CNETAsia when asked whether Google will consider using the team's methods, or if the privately-held company was involved in the university team's efforts.

The Stanford team presented its paper on these Google enhancements at the Twelfth Annual Word Wide Web Conference in Budapest, Hungary, last week.