Google Patents Search Algorithm

blastedtokyo writes "Google gets the first web search patent. According to this News.com.com article, Google was able to patent how they crawl and rank web pages. They claim "an improved search engine that refines a document's relevance score based on interconnectivity of the document within a set of relevant documents.""

Comments

Mis-title

[Amsterdam Vallon]

It's not really their Search algorithm, it's their method of comprehensive PageRanking.

They basically measure Web pages as either 1) portals, or 2) authorities.

Sites like Kuro5hin and *nix have a lot of "Google juice" (i.e. weight in their ranking system) because they have so many links to other sites, while also garnering a slew of links to their main page.

Re:Mis-title

[MilTan]

PageRank doesn't actually distinguish between "portals" and "authorities." It "only" does a link-analysis of the web by essentially mutiplying some ranking vector by a matrix representing the links in the web, with a random jump to another location taking place with a certain probability to create a new ranking vector. Once this converges, you have the new "PageRank."

PageRank scores are calculated completely independently of the search query. You are probably thinking of Kleinbergs HITS (or Hubs and Authorities) algorithm which uses an initial search query to prune the search space, and then identifies hubs and authorities in the web. In contrast to PageRank, which only uses forward links to calculate its rankings, HITS uses both forward and "backward" links to figure out its ratings. Furthermore, unlike PageRank, HITS produces different scores for different queries.

The above tells us the following: That Kuro5hin and Slashdot have high pageranks not because of their excessive numbers of outlinks, but because many people point to their frontpages. Similarly, these high PageRanks mean that people that Slashdot or Kuro5hin point to get higher scores as well.

Oh Please - Eugene Garfield did this is 1961

[tiltowait]

Google didn't invent the concept behind PageRank, just its name. See my E2 writeup on citation analysis for more.

Re:Oh Please - Eugene Garfield did this is 1961

[zmahk31]

In fact, the algorithm as a computational method goes back to Jacobi 1804-1851, and is essentially an iterative solver for large systems of linear equations.
<p>
Of course, it's still a significant contribution to see the application of the Jacobi method to ranking web pages, and I assume that they have done some clever and many more dirty tricks to get more realistic results, weed out duplicate pages, etc., which may or may not be part or the patent.
<p>
In any case, the basic page rank algorithm is quite intuitive to anyone who has worked with iterative numerical methods, and in fact a very nice illustration of the power of such methods.

And if you try to fool..

[Frank of Earth]

..google, you will feel their wrath

Software patents

[killmenow]

I find it interesting that because it's google, some /.-ers are saying essentially "good for them!" But at the heart of it, it makes no difference who it is or what their intention is.

Kids, software patents are bad, mm-kay...

Not necessarily...

[TopShelf]

Patents are also widely used as a means of rewarding an inventor by giving them an avenue to license their technology to one or many users who can then implement it into commercial products. In that way you don't get a monopoly, nor does the inventor have to provide the capital required to bring something to market. You only get a monopoly if the patent holder refuses to sell licenses, or sells it to a single user.

Think fuel injectors, for example, which are made by several suppliers, but have a patent holder who gets license revenue.

Patent # 6,526,440

[esme]

read the patent

Re:OMG MORE PATENTS!!!

[iocat]

Now that they've been awarded a patent for page-rank, it's required for them to make it public so that people can license it. You can't patent a trade secret and still have it be secret. People now have the opportunity to build new methods and innovate with Pagerank as a basis for that innovation. (Real innovation, not MS innovation.)

Actually, they are required to disclose it, but not to license it. The patent gives them a 17 year legal monopoly to do whatever they want with it (use it, license it, bury it, etc.). As an example, Capri Sun never licensed their patented "juice bag" technology, forcing others to use inferior "drink boxes" to deliver product. Now that the patent is expired, other "drink bags" are on the market.

More worrying is that software patents are sometimes granted using such general language that the entity getting the patent *doesn't* really have to disclose anything, enabling them to get both protection while keeping their invention secret, which is exactlty the opposite effect of what patents were intended for -- to get duplicable knowledge into the public domain after a period of protection for the original inventor.

Why not?

[FallLine]

In fact, I bet a few hours of research into Sociology, Psychology, and Linuquistics papers will turn up generic proofs and observations of the very same things that page rank takes care of in a different context. A context shift shouldn't be patentable. Much software (but not all) involves making these logical leaps. Many times they are leaps from pure science that is copyrighted (on the one hand) but (increasingly less so) open on the other. This is human knowledge we are dealing with. The Scientific Method... all that crap. It doesn't work unless everyone shares their toys. Start locking them up and you stifle innnovation (at the least) or become dictatorial master of (increasingly more of) everyone's lives.

What a bunch of psychobabble. Google should be able to patent what they have done because:

A) The algorithm is highly useful.

B) It required a significant amount of risk and technical effort to make it worthwhile.

C) The scope of the patent really just covers what it is that they've added, i.e., the ideas that they are supposedly deriving from are not being locked up.

What more do you really need to know? Regardless of what language you wish to put your claims in, that they've just made a "context shift" or what have you, it is a worthwhile effort and it is the kind of effort that requires the potential for substantial profits to secure continued efforts. People don't take risk without at least the potential to profit and the greater the potential reward the greater risks people are willing to take. Are you really going to argue that the idea was obvious or easy? If so, then explain why no one did it before, when billions of dollars and many years were (and are) being spent on such internet technology. There was a considerable lag time between the appreciation of the need for a good search engine (and the resources to develop them) and google's appearance. What's more, keep in mind that:

a) Google's core methodology is no secret now

b) The patent's life is limited.

c) The ideas that they presumedly derived from a still as open as they were prior to this patent

d) This country produces far more than any country despite the fact that we arguably "share our toys" less than most countries, even more than countries with much larger populations (even technically educated ones)....

Now I agree that there are dangers in allowing people to patent any and everything, e.g., well known sorting algorithms and other fundamental building blocks, but this clearly is not happening here.

Re:Good for them...

[Xofer D]

Well, actually...

See J.M. Kleinberg, "Authoritative Sources in a Hyperlinked Environment", Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, ACM Press, New York and SIAM Press, Philadelphia, 1998, pp.668-677

That discusses the HITS algorithm, which is the core of PageRank (which is a simplified version of HITS). Sergey Brin and Lawrence Page in fact developed [1] Google from HITS [2].

References:
[1] S. Brin and L. Page, "The Anatomy of a Large Scale Hypertextual Web Search Engine", Proceedings of the 7th World Wide Web Converence, Elsevier Science, Amsterdam, 1998. pp. 107-117

[2] Chakrabarti, Dom, et. al., "Mining the Web's Link Structure", Computer, August 1999. pp. 60-66