adaptive pagerank

Google’s Adaptive PageRank Patent

by

Sharing is caring!

Added July 16, 2019 Yesterday a story at Search Engine Roundtable told us: Former Google Engineer: Google Hasn’t Used PageRank Since 2006. There was a new version of PageRank which I wrote about in 2006, not the adaptive PageRank that this post is about, but a different method of calculating PageRank in the post, PageRank Update.

The Google Search Engineer who posted that about PageRank, Jonathan Tang included some more information at Hacker News about that change to the algorithm behind PageRank.

The comments here that PageRank is Google’s secret sauce also aren’t true – Google hasn’t used PageRank since 2006. The ones about the search & clickthrough data being important are closer, but I suspect that if you made that public, you still wouldn’t have an effective Google competitor.

Tang told us this about the change away from that version of PageRank:

They replaced it in 2006 with an algorithm that gives approximately similar results but is significantly faster to compute. The replacement algorithm is the number reported in the toolbar and what Google claims as PageRank (it even has a similar name, and so Google’s claim isn’t technically incorrect). Both algorithms are O(N log N), but the replacement has a much smaller constant on the log N factor because it does away with the need to iterate until the algorithm converges. That’s fairly important as the web grew from ~1-10M pages to 150B+.

That last reason seems to fit this adaptive PageRank very well.

Google’s Adaptive Pagerank Patent

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 – in short, an adaptive PageRank. This work doesn’t aim at changing rankings or determinations of the 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 anything new, it’s interesting to see how the ideas in the paper can be implemented as part of a search engine. The adaptive PageRank 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 fewer 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 references many 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 adaptive PageRank patent and paper. While the patent mentions personalization, it doesn’t cover the topic in much depth. It also doesn’t address historical data, seasonality, burstiness, user behavior, and other areas that 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 are disclosed. A ranking function for a set of document rank values is iteratively solved concerning a set of linked documents until a first stability condition is satisfied. After such a condition is satisfied, some of the ranks will have converged. The ranking function is modified to consider these converged ranks to reduce the ranking function’s computation cost. The modified ranking function is then solved until a second stability condition is satisfied. After such a condition is satisfied, more of the ranks will have converged. The ranking function is again modified, and the process continues until complete.

The adaptive PageRank 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 in the adaptive PageRank patent:

Last Updated July 16, 2019.

Other cited references:

Sharing is caring!

2 thoughts on “Google’s Adaptive PageRank Patent”

  1. Pingback: You know you are a Bill Slawski fan, when..
  2. Pingback: On Personalized PageRank and Personalized Anchor Text Scores -SEO by the SEA

Comments are closed.