Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

Researchers Develop Techniques for Computing Google-Style Web Rankingsup to Five Times Faster

14.05.2003


Speed-up may make "topic-sensitive" page rankings feasible

Computer science 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.

The Stanford team includes graduate students Sepandar Kamvar and Taher Haveliwala, noted numerical analyst Gene Golub and computer science professor Christopher Manning. They will present their first paper at the Twelfth Annual World Wide Web Conference (WWW2003) in Budapest, Hungary, May 20-24, 2003. The work was supported by the National Science Foundation (NSF), an independent federal agency that supports fundamental research and education in all fields of science and engineering.

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. For example, searching a sports-specific Google site for "Giants" would give more importance to pages about the New York or San Francisco Giants and less importance to pages about Jack and the Beanstalk.

"This work is a wonderful example of how NSF support for basic computer science research, including applied mathematics and algorithm research, has impacts in daily life," said NSF program officer Maria Zemankova. In the mid-1990s, an NSF digital library project and an NSF graduate fellowship also supported Stanford graduate students Larry Page and Sergey Brin while they developed what would become the Google search engine.

To speed up PageRank, the Stanford team developed a trio of techniques in numerical linear algebra. First, in the WWW2003 paper, they describe so-called "extrapolation" methods, which make some assumptions about the Web’s link structure that aren’t true, but permit a quick and easy computation of PageRank. Because the assumptions aren’t true, the PageRank isn’t exactly correct, but it’s close and can be refined using the original PageRank algorithm. The Stanford researchers have shown that their extrapolation techniques can speed up PageRank by 50 percent in realistic conditions and by up to 300 percent under less realistic conditions.

A second paper describes an enhancement, called "BlockRank," which relies on a feature of the Web’s link structure-a feature that the Stanford team is among the first to investigate and exploit. Namely, they show that approximately 80 percent of the pages on any given Web site point to other pages on the same site. As a result, they can compute many single-site PageRanks, glue them together in an appropriate manner and use that as a starting point for the original PageRank algorithm. With this technique, they can realistically speed up the PageRank computation by 300 percent.

Finally, the team notes in a third paper that the rankings for some pages are calculated early in the PageRank process, while the rankings of many highly rated pages take much longer to compute. In a method called "Adaptive PageRank," they eliminate redundant computations associated with those pages whose PageRanks finish early. This speeds up the PageRank computation by up to 50 percent.

"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 complexities of a personalized ranking would require even greater speed-ups to the PageRank calculations. In addition, while a faster algorithm shortens computation time, the issue of storage remains. Because the results from a single PageRank computation on a few billion Web pages require several gigabytes of storage, saving a personalized PageRank for many individuals would rapidly consume vast amounts of storage. Saving a limited number of topic-specific PageRank calculations would be more practical.

The reason for the expensive computation and storage requirements lies in how PageRank generates the rankings that have led to Google’s popularity. Unlike page-ranking methods that rate each page separately, PageRank bases each page’s "importance" on the number and importance of pages that link to the page.

Therefore, PageRank must consider all pages at the same time and can’t easily omit pages that aren’t likely to be relevant to a topic. It also means that 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’s conference paper and technical reports on enhancing the PageRank algorithm, as well as the original paper describing the PageRank method, are available on the Stanford Database Group’s Publication Server (http://dbpubs.stanford.edu/).

David Hart | National Science Foundation
Further information:
http://www.stanford.edu/~sdkamvar/research.html
http://www.www2003.org/
http://dbpubs.stanford.edu

More articles from Information Technology:

nachricht 'Building up' stretchable electronics to be as multipurpose as your smartphone
14.08.2018 | University of California - San Diego

nachricht New interactive machine learning tool makes car designs more aerodynamic
14.08.2018 | Institute of Science and Technology Austria

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Unraveling the nature of 'whistlers' from space in the lab

A new study sheds light on how ultralow frequency radio waves and plasmas interact

Scientists at the University of California, Los Angeles present new research on a curious cosmic phenomenon known as "whistlers" -- very low frequency packets...

Im Focus: New interactive machine learning tool makes car designs more aerodynamic

Scientists develop first tool to use machine learning methods to compute flow around interactively designable 3D objects. Tool will be presented at this year’s prestigious SIGGRAPH conference.

When engineers or designers want to test the aerodynamic properties of the newly designed shape of a car, airplane, or other object, they would normally model...

Im Focus: Robots as 'pump attendants': TU Graz develops robot-controlled rapid charging system for e-vehicles

Researchers from TU Graz and their industry partners have unveiled a world first: the prototype of a robot-controlled, high-speed combined charging system (CCS) for electric vehicles that enables series charging of cars in various parking positions.

Global demand for electric vehicles is forecast to rise sharply: by 2025, the number of new vehicle registrations is expected to reach 25 million per year....

Im Focus: The “TRiC” to folding actin

Proteins must be folded correctly to fulfill their molecular functions in cells. Molecular assistants called chaperones help proteins exploit their inbuilt folding potential and reach the correct three-dimensional structure. Researchers at the Max Planck Institute of Biochemistry (MPIB) have demonstrated that actin, the most abundant protein in higher developed cells, does not have the inbuilt potential to fold and instead requires special assistance to fold into its active state. The chaperone TRiC uses a previously undescribed mechanism to perform actin folding. The study was recently published in the journal Cell.

Actin is the most abundant protein in highly developed cells and has diverse functions in processes like cell stabilization, cell division and muscle...

Im Focus: Lining up surprising behaviors of superconductor with one of the world's strongest magnets

Scientists have discovered that the electrical resistance of a copper-oxide compound depends on the magnetic field in a very unusual way -- a finding that could help direct the search for materials that can perfectly conduct electricity at room temperatur

What happens when really powerful magnets--capable of producing magnetic fields nearly two million times stronger than Earth's--are applied to materials that...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

Within reach of the Universe

08.08.2018 | Event News

A journey through the history of microscopy – new exhibition opens at the MDC

27.07.2018 | Event News

2018 Work Research Conference

25.07.2018 | Event News

 
Latest News

Unraveling the nature of 'whistlers' from space in the lab

15.08.2018 | Physics and Astronomy

Diving robots find Antarctic winter seas exhale surprising amounts of carbon dioxide

15.08.2018 | Earth Sciences

Early opaque universe linked to galaxy scarcity

15.08.2018 | Physics and Astronomy

VideoLinks
Science & Research
Overview of more VideoLinks >>>