We can make your web site easier to find, and easier to use.
«  
  »

Google's adaptive pagerank patent

By , on April 18, 2006, at 10:00 am



Google was granted a new patent involving pagerank last week, which appears to focus upon a paper from April of 2003, Adaptive Methods for the Computation of PageRank.

The paper does a nice job of describing what they were aiming at with this patent – a faster way of assigning query-independent rankings of value to pages on the web, based upon links to those pages. This work doesn’t aim at changing rankings, or determinations of relevance of web pages, but is instead aimed at making the computational elements of calculating rankings cheaper and faster.

While the methods and processes described in the patent aren’t really anything new, it’s interesting to see how the ideas in the paper can be implemented as part of a search engine. The patent provides a nice overview of how a search engine functions, covering topics such as crawling, filtering, indexing, index partitioning, caching, mapping links, and serving pages.

It then dives into the method they have devised to take advantage of the observation they made that some pages take less time, and less recalculations of pagerank to reach their final pagerank. As the authors note in the paper:

That is, many pages converge quickly, with a few pages taking much longer to converge. Furthermore, the pages that converge slowly are generally those pages with high PageRank.

The patent cited as references a number of other papers and patents, and I’ve linked to those below if you would like to follow the evolution of the work that helped lead to this patent and paper. While the patent mentions personalization, it doesn’t cover the topic in much depth. It also doesn’t address such things as historical data, seasonality, burstiness, user behavior, and other areas which we’ve seen included in other papers and patent applications from academia and patent filings.

Adaptive computation of ranking

Inventors: Sepandar D. Kamvar, Taher Haveliwala, and Gene H. Golub
Assigned to Google Inc.
US Patent 7,028,029
Granted April 11, 2006
Filed: August 23, 2004

Abstract

A system and method is disclosed in which a ranking function for a set of document rank values is iteratively solved with respect to a set of linked documents until a first stability condition is satisfied. After such condition is satisfied, some of the ranks will have converged. The ranking function is modified to take into account these converged ranks so as to reduce the ranking function’s computation cost. The modified ranking function is then solved until a second stability condition is satisfied. After such condition is satisfied more of the ranks will have converged. The ranking function is again modified and process continues until complete.

The patent also notes that it is related to Methods for ranking nodes in large directed graphs, published February 10, 2005, and invented by Sepandar D. Kamvar, Taher Haveliwala, Glen Jeh, and Gene H. Golub

U.S. patents and patent applications cited:

Other cited references:

LinkedInPinterestStumbleUponShare
10:00 am | Category: Search Engines and Directories | 2 comments - (Comments are closed)

2 comments to Google’s adaptive pagerank patent

Comments Policies

  • Relevant comments on the topic of a post are very much appreciated.
  • Please use your personal name rather your business name or keywords in the name field.
  • Comments filling the name field with anchor text to spam this site and search engines (in English or any other language) may be edited, have URLs removed, or deleted entirely.
  • If you include a link in the website field, please choose one about you rather than some product or service or site or blogpost that you are promoting.
  • No signature links in comments, please.