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.

Re:Mis-title

[naoiseo]

This post doesn't make sense...

Google, when it's 'reading' a page, is having a bot spider it. If google is spidering a page and comes across a link to a page it has not 'read', then it follows the link, spiders the page, and includes it in the index.

As for returning results to the 'unread page' based on the context of the link, what do you mean by 'returned results to the page'? Do you mean, is now capable of displaying that page in its results set for a specific query?

You *might* mean that a 'freshbot', which is googlebot's little bro, can go and pick up a new page and temporarily add it to the google index for the month, without calclulating its true PageRank (it waits until after the next update, so it can compair the new page to everything else in context).

in this sense an 'unread' page could mean a page that is not properly indexed yet, but is a new addition.

It's true that google can return a page in its results that don't have the search phrase on it, if that search phrase has been used to point to the page in question, but it doesn't mean google hasn't 'read' the page in question, it has.

but google does not return pages in its results set that it hasn't spidered, and has only seen the links to. If google sees a link, it goes and indexes the page.

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 Obsession: Today's UF Topic

[Anonymous Coward]

What a coincidence. Today's UF topic covers patent obsession. Check it out. Although amazon.com is the target of the joke, it shows how patent-obsessed software companies can be. I'd say it sure does a good job satirizing it. Who knows? Maybe Google will be targeted in tomorrow's strip.

Re:Novel and innovative?

[Sir Runcible Spoon]

May be, may be not.

Some have been talking about similar techniques since before this patent was filed:

http://www.carnet.hr/cuc/cuc2000/radovi/prezenta ci je/F/F3/F3_f.pdf

http://citeseer.nj.nec.com/context/856618/0

How I Got Ranked Highly at Google

[MichaelCrawford]

Many of my pages show up in the first page of Google's results for relevant search terms, sometimes even being the number one result. For example, lately a google search for software consultant resume lists my resume as the #1 search result. (Your search results may vary.)

I didn't pay a search engine optimization service to make this happen. I didn't use any tricks like "doors" either. It cost me no money, but it did take time and hard work to achieve it.

I explain everything I did in How To Promote Your Business On the Internet.

What's my secret? No secret at all:

• Put stuff on your site that people find interesting and useful
• Ask people for links, and give them reciprocal links in return.

That's it. But read my article for the full discussion, as well as an explanation of why I'm telling everyone my secret.

Other pages I have that you may find helpful are:

• Market Yourself - Tips for High-Tech Consultants
• Search Engine Submission Form Index

My most popular page is a C++ style guide called Pointers, References and Values.

and finally, from my K5 diary, A Webmaster's Strange But True Tale.

Thank you for your attention.

Patent # 6,526,440

[esme]

read the patent

How to remove your support for Google

[nagora]

Create a robots.txt file in your site's root directory with:

User-agent: googlebot
Disallow: /

and then go to the "Urgent URL removal" page on google (click here and follow the instructions. Your site should be removed within 24hrs. I've taken mine off and I suggest that any programmer that is concerned about being able to work freely should too.

TWW

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:Why not?

[Fulcrum of Evil]

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)....

How is this even relevant? Anyway, which countries did you have in mind?

They already do

[yerricde]

The patent notice contains a U.S. patent number. When entered into the USPTO search engine, a patent number calls forth a complete description of how to implement an invention.

Re:OMG MORE PATENTS!!!

[mentin]

One piece of prior art is known to every science student who needed to find most important articles on a subject. Without any computers, we looked the references (now hyperlinks) and searched for articles that are referenced most, thus finding articles with highest "rank".

But since USPTO considers "find a common knowlegde algorithm and patend a way to do it with computers" a valid patenting method, they probably would not consider it a prior art.

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