PageRank-Type Algorithm From the 1940s Discovered 108
KentuckyFC writes "The PageRank algorithm (pdf) behind Google's success was developed by Sergey Brin and Larry Page in 1998. It famously judges a page to be important if it is linked to by other important pages. This circular definition is the basis of an iterative mechanism for ranking pages. Now a paper tracing the history of iterative ranking algorithms describes a number of earlier examples. It discusses the famous HITS algorithm for ranking web pages as hubs and authorities developed by Jon Kleinberg a few years before PageRank. It also discusses various approaches from the 1960s and 70s for ranking individuals and journals based on the importance of those that endorse them. But the real surprise is the discovery of a PageRank-type algorithm for ranking sectors of an economy based on the importance of the sectors that supply them, a technique that was developed by the Harvard economist Wassily Leontief in 1941."
Good advice for all developers (Score:5, Insightful)
Well, this is actually pretty good advice for any developer; Don't reinvent the wheel. Look around, search for what's been done before and adapt it to suit your needs. Of course, as a last resort, one can design something new once he has done his homework and made sure nothing that has been done before may be re-used.
Through my life, I have seen a amazing high level of work that has been done in vain because it yielded poor results and that something doing the same better already existed anyway.
Don't get me wrong here, once you have made sure that nothing already existing suits your needs or can be reused, it is fine to innovate and create real new stuff. Just don't get caught trying to reinvent the wheel unless you reinvent it better ;-)
Also, an exception to that principle could be allowed for trivial tasks that are really quick to implement and where searching for an existing solution might cost more than implementing it yourself but be really careful applying that exception rule, it is an open door that leads to trying to reinvent the wheel sometimes ;-))
Re:Good advice for all developers (Score:5, Funny)
It would have been a pretty exhaustive search without google.
Re: (Score:3, Informative)
They could have used one of the other search engines in existence in 1997-98, like Altavista or Lycos or Magellan or WebCrawler or Yahoo or Excite or Hotbot.
Re:Good advice for all developers (Score:5, Funny)
I can see that you must be young enough never to have used the search engines you list, if you suggest that you would have been able to find anything useful.
Re: (Score:1, Interesting)
You must be the one who hasn't. While they can't be compared to what we have today, they were useful. I particularly liked Infoseek. Oh and GOOGLE SUCKED at first, I remember this VERY WELL, i tried it when it started and it wasn't any good. I guess it took a while to gather enough data to really show their algorithms' potential, now i always use google of course...
Re: (Score:2)
I particularly liked Infoseek.
Infoseek was my flavor, too. Then Disney bought it, changed the name to Go.com, brought in a terrible new design, and all of a sudden the search results went to shit. Hope it was worth the money, Disney.
Re: (Score:3, Insightful)
I can see that you must be young enough never to have used the search engines you list, if you suggest that you would have been able to find anything useful.
Well the results were there, somewhere between all the adverts.
Re: (Score:2, Insightful)
Remember the internet was a LOT smaller in 1997, so while my preferred engine at that time (altavista) may not have been as good as google today, there was also a lot fewer websites to search through.
>>>I can see that you must be young enough never to have used the search engines you list
I'm familiar with the slashdot practice of not RTFA (reading the frakking article), but when did people stop reading user names? You think I'm young? My first computer was a Commodore and my second an Amiga. I w
Re: (Score:1)
I would use Yahoo primarily and Altavista occassionally. But I don't know why you claim that you're so old to have done that stuff. I was young then. I remember the Commodore64. What is your definition of old then? I'm nostalgic about that too but I think of that as being because I was (and still am sorta) young and I get nostalgic - whereas an older person would be less sentimental because that wasn't the first computer and also because it wasn't that great. really.
Re: (Score:2)
I'm 24, I had my Commodore 64 when I was 4, I wasn't surfing the web until about 1997 either. I don't consider myself old (Sometimes I do, I just don't "get" this modern music nonsense). I can remember using AltaVista and Yahoo search. Sometimes searching through Geocities directories back in the day.
I've forgotten what my point was.
Anyway. I'm not old.
Re: (Score:2)
I can understand C64_love's frustration. When some mods purposely damage your reputation/karma, you lose your ability to post for 1-2 days time. You feel that you are being muzzled like a Chinese citizen instead of a free person.
NOBODY should set out to destroy another slashdotter like that.
Re: (Score:2)
In that era, search engines were like mini databases. You had to put in exactly the right query to get results.
I was famous for being able to find anything, and I mean anything, using AltaVista, when others couldn't. It was a lot like programming in a way, which explains why I was good.
I used to be able to be king of Google until they made it much more natural-language tolerant. Now my 10 year old neighbor can find things when I can't.
On the plus side, I can now type in "When is the damn stupid bowl muth
Re: (Score:3, Funny)
I can see that you must be young enough never to have used the search engines you list, if you suggest that you would have been able to find anything useful.
What are you talking about? I found useful results all the time! I just wish my interest in being a porn connoisseur could be turned into a career.
Re: (Score:1)
NATIONAL DEBT is ~$130,000 per US home and growing $10,000/yr.
So what? It's not like that makes anyone poorer.
Re:Good advice for all developers (Score:4, Insightful)
Re:Good advice for all developers (Score:4, Interesting)
"don't reinvent the wheel" is kindof dumb advice when you think about it.
If I didn't already have a wheel, it would take me a really long time to traverse the world in search of a wheel to see if it had been invented yet. If it has, and it's got sufficient penetration into the market that I know about them already, then, sure, it's a no brainer not to reinvent it. On the other hand, if no one in my immediate vicinity has ever heard of the wheel, then inventing one -- quickly -- is a lot smarter than traversing the known world until I run into a culture that already has wheels. Especially if they might exploit their superior technology to subjugate and enslave my people. Better to have a home-brewed shitty wheel to start off with, and upgrade quickly if I discover that there are other friendly cultures that have better wheels already, and have at least something if I don't discover anyone else, or discover hostiles who already have them.
As long as the cart is loosely integrated with the wheels I have, upgrading to better wheels when they are found to be available should be easy. And I might just learn something about wheels while studying them that applies to other problems, or could even possibly improve the existing state of the art with respect to wheels.
Re: (Score:2)
http://en.wikipedia.org/wiki/Reinventing_the_wheel [wikipedia.org]
Re: (Score:3, Insightful)
Reinventing the wheel is a phrase that means to duplicate a basic method that has long since been accepted and even taken for granted. [wikipedia.org]
K, so how is Brin and Page developing PageRank when an obscure economics paper published at Harvard in 1941 and only re-discovered in 2010 reinventing the wheel?
Would Page and Brin have gotten there faster if they'd rooted through Harvard's economics library in the hopes that the best-yet algorithm for search results ranking would be there, somewhere? Was the Harvard paper "
who says it was rediscovered in 2010? (Score:2)
K, so how is Brin and Page developing PageRank when an obscure economics paper published at Harvard in 1941 and only re-discovered in 2010 reinventing the wheel?
Who says it was first re-discovered in 2010, and not in the 90's, by two guys from Stanford?
There are a million possible ways Brin and Page could have come across that paper. A friend who was studying economics, maybe a magazine like the Economist mentioned it, etc.
Pretty funny claiming to be the first to re-discover something, though. What
Re: (Score:2)
It's an obvious idea that they most likely implemented independently. I say this because the only similarity between the models is a trivial feedback loop summed up as 'x is important if it is endorsed by important x', the methodology is completley different in each case.
Re: (Score:3, Informative)
Dude; it's just Jacobi iteration applied to a particular, reasonably intuitive model. This isn't to knock it -- just to say that it was probably easier to reinvent it than to find some obscure paper --- especially one which probably isn't in the electronic databases.
Re: (Score:2)
They didn't reinvent anything, the analogy is poor. If anything, they took the idea and found a new application for it, then created a functional product based on it.
I was in college around the time Google was just getting up and running, and it was widely known that the quality of a paper could be measured in how many times it was cited by other people, in fact IIRC, some journal search engines would even show the number of citations when you did a search. So the idea that important documents were "linked
Re: (Score:3, Insightful)
Wow, +5 Pedantic.
Reinventing the wheel implies that they set out to find a measure of importance. So they would have had to decide to make a search engine, have it produce relative results, decide that relative importance is the key, and then go searching for ways to find relative importance. There's a major gap there, a leap in thinking that simply wasn't present at the time. How important a page is indicates what order it should be in results. That makes sense, but it wasn't obvious at the time. Prev
Re: (Score:1)
A side effect of this was the introduction of the term 'dogfooding' which was then re-invented by Microsoft.
Maybe.
Re: (Score:1)
Don't reinvent the wheel. Look around, search for what's been done before and adapt it to suit your needs.
What if I need a cog or a chassis? Scrapheap Challenge [wikipedia.org] rings a bell? With, in most of the occasions, better build the chassis yourself than struggle to get it free and work furiously to adapt it?
Re: (Score:3, Interesting)
There is a second rule of advice that goes with this, but that unfortunately usually is forgotten:
Don’t imitate. Innovate!
Yes, it is a good idea to not reinvent the wheel. But it’s even better to invent an airplane! (You know: Thinking outside the box. “Inside the box” would be a square wheel. ;)
Re: (Score:3, Informative)
Re: (Score:2, Funny)
Re: (Score:1)
Ha ha, then you won't be able to publish any paper.
The research world is now filled with researchers who simply don't read others' works, and just keep writing. Even if it's been done before (or even if it doesn't make any sense at all), eventually they will be able to find a venue that will accept the paper, because no reviewer can know everything.
And worries not about citation! Those work will be cited because of exactly the same reasons, or even worse, because the party who cites it has performed work th
Re: (Score:2)
Well, this is actually pretty good advice for any developer; Don't reinvent the wheel.
That is some good folksy wisdom for your intrepid yound developer. Also:
"Don't count your chickens before they're hatched!"
"A little too late is much too late!"
"A small leak will sink a great ship!"
"Lost time is never found!"
"A chain is as strong as its weakest link!"
"A bad broom leaves a dirty room!"
Anyway, my point is not that your advice is bad. But are you seriously suggesting that Brin, when he had this idea, should have gone straight for the library until he found this 1941 Economics paper? I wonde
Re: (Score:2)
> But are you seriously suggesting that Brin
I am not suggesting anything, I even said that it was OK to innovate re-invent in some circumstance. And if one really thinks that he can innovate, he should go for it, that's what we call progress ;-)
I perceived Google algorithm like something very innovative and I wouldn't have guessed that it was based on such an old concept so I thought that it was appropriate to write about it.
We all like to re-invent and innovate, it is human nature and I am no exception.
Re: (Score:2)
Also, an exception to that principle could be allowed for trivial tasks that are really quick to implement and where searching for an existing solution might cost more than implementing it yourself but be really careful applying that exception rule, it is an open door that leads to trying to reinvent the wheel sometimes
I think you just reinvented the principle of marginal gains in utility of information gathering. It's in every Microeconomy 101 text book, in the paragraph about asymmetry of information.
And I just reinvented the exploding irony-meter.
Re: (Score:2)
> I think you just reinvented the principle of marginal gains in utility of information gathering. It's in every Microeconomy 101
Basic principles are sometimes expressed differently form one field of activity to another. When you encounter the same principle expressed differently, the spirit of the principle becomes some kind of "meta-principle" and the specific definition made in every field become application of the "meta-principle". This is usually a sign that the principle is valid ! ;-))
So, I didn't
Re: (Score:3, Interesting)
> As for ranking pages by links to other important pages, that's rather flawed?
I hinted that it was OK to innovate or even re-invent. You have to know what you are doing although.
Actually, I totally agree with you on the quoted phrase but I am still looking for a solution (Holy Grail?) to supplant Google implementation. ;-))
Seriously, I really spent some time thinking about this...
Re: (Score:1, Interesting)
I'm beginning to suspect I'm being targeted. Nearly every one of my posts has been demodded -1 point (which drops me down to (0) score).
And there's nothing "offtopic" about agreeing with the previous poster's statement: "Don't reinvent the wheel. Look around, search for what's been done before and adapt it to suit your needs." That really is what I do in my day-to-day routine as an engineer.
Re: (Score:2)
If that sort of thing happens relatively often, it does sound like one of your "foes" might be targeting you. I don't see anything that could be considered a troll in your post.
In reference to your OP, though, have you looked in to the original infoseek formula?
Re: (Score:2)
If you pay attention to the moderation scheme on here, that isn't very likely.
"moderators" are any average user. They get 10 points at a time to spend as they'd like. If they write a comment to a particular story, they can't moderate on that story.
"Metamoderation" lets you re-evaluate moderations, but you get limited information on the comment, basically the comment itself. Only 10 of these really count. More metamoderations can be done, but don't count as hi
Nah -it's the commodore thing (Score:1)
Since everyone knows that Linux is superior to whaterver else, why would one heretical comment start a war against you? Aren't linux-lovers the most gentle and forgiving people on earth?
What I think it is? your nick: Loving a commodore 64 puts you in the same age group as Bill Gates, too old to post on /.
- Oh and worrying about the National debt: that means you don't live in your mom's basement anymore. Definitely not someone one would like to have on /.
Patent? (Score:2)
Re: (Score:3, Funny)
Re: (Score:1, Insightful)
CHECKLIST:
Is Google a megacorp? Check.
Did Google threaten to move to India if Obama raises corporate taxes? Check.
Does Google spy on users and collect data? Check.
Did Google receive monetary assistance from the Taxpayer's Public Treasury? Not sure.
Okay. I'll let them slide and not try to invalidate their pagerank patent, but that likely won't stop Microsoft from making the attempt.
Re: (Score:2)
Re:Patent? (Score:5, Informative)
So it could be used as previous art to invalidate Google's patent?
From my read of the linked article it seems that Sergey and Larry cited the previous art in their publications. So it looks like there was no plagiarism, just building a new idea using the tools provided by an earlier idea.
Re: (Score:1)
Re: (Score:2)
ah, so it is a patent of the type: ... but now we do it on a computer"
"the same as
Knew about this before I first used google (Score:2)
Re:Patent? (Score:4, Informative)
No, since the one from 1941 didn't say "on the internet" or "with a computer".
Re: (Score:2)
No, since the one from 1941 didn't say "on the internet" or "with a computer".
Neither did Google's PageRank patent. You shouldn't use Slashdot as your source for patent law, particularly when search engines like Google exist to help you find out facts.
Re:Patent? (Score:5, Funny)
Better patent your time-machine too! (Score:2)
.. while you're in the process.
Re: (Score:2)
Yes, facts. That's what I was trying for.
Re: (Score:2)
Re: (Score:1, Insightful)
Patent?
I think the way the Google maintains its search superiority has more to do with massive banks of machines and keeping their algorithms secret rather than sending lawyers after anyone. The PageRank algorithm is little more than a useful application of Markov Chains... hardly seems patentable. (Of course, RSA doesn't seem like it should have been patentable either...)
Just more proof... (Score:3, Interesting)
linearity (Score:4, Interesting)
What really shocked me when someone first described page rank to me was that it was linear. I felt that this just had to be wrong, because it didn't seem right for a *million* inbound links to have a *million* times the effect compared to a single inbound link. Maybe this is just the elitist snob in me, but I don't feel that the latest American Idol singer is really a thousand times better than Billie Holliday, just because a thousand times more people listen to him than to her. If it was me, I'd have used some kind of logarithmic scaling. I think people do usually describe page ranks in terms of their logarithms, but that's taking the log on the final outcome. I'm talking about taking logs at each step before going on to the next iteration.
To me, this has an intuitive connection to the idea that the internet used to be more interesting and quirky, and it was more about individuals expressing themselves, whereas now it's more like another form of TV.
Of course that's not to say that I want to go back to the days before page rank. God, search engine results were just horrible in those days.
From an elitist snob point of view, one good thing about page rank is that it doesn't let you just vote in a passive way, as Nielsen ratings do for TV. In order to have a vote, you have to do something active, like making a web page that links to the page you want to vote for.
Re: (Score:1)
Re:linearity (Score:5, Insightful)
Re: (Score:2)
I think the best search engine is the one that can tailor it's algorithms to the specific users tastes. I'm certain that custom-algorithms would be the way to go for instance.
When some people search for stuff they usually have a good idea and class of information they are looking for. Either way it would be an interesting project/
Re: (Score:2)
Yes, but if you look back at my GP post, I explained that I'm not talking about taking the log of the final result (which would be irrelevant for sorting).
Re:linearity (Score:5, Informative)
The algorithm is not at all linear in the effect of inbound links. Two inbound links don't have the same effect, instead their effects are first weighted by the PageRank of each node of origin.
Now the distribution of PageRank among nodes is approximately power-law distributed on the web. Intuitively, this means that among all inbound links of a particular node, when that number is high, then 99% have practically no effect on the rank of that node, exactly as you probably thought in the first place. More precisely, you can expect a pareto (or similar) distribution for the influence of incoming nodes, which is not unexpected since these sorts of distributions occur a lot in social sciences.
That said, the PageRank algo is actually linear, but only in the sense of being a linear operator on weight distributions. If you normalize the weights after each iteration, the algo is actually affine (on normalized distributions) rather than linear.
Re:linearity (Score:4, Informative)
The reason why PageRank 'has to be' linear is essentially mathematical; treating importance as a linear function of the importance of inbound links means that the core equations that need to be solved to determine importance are linear and the answer can be found with (essentially) one huge matrix inversion. If you make importance nonlinear then the equations being solved become computationally infeasible.
What's interesting to me is how close the connections are between PageRank and the classic light transfer/heat transfer equations that come up in computer graphics' radiosity (see James Kajiya's Rendering equation); I wonder if there's a reasonable equivalent of 'path tracing' (link tracing?) for computing page ranks that avoids the massive matrix inversions of the basic PageRank algorithm.
Re:linearity (Score:5, Insightful)
You understand neither how the parent post is using the word "linear" nor the PageRank algorithm itself. You can rewrite the eigenproblem at the heart of PageRank as the solution to a linear system, but very few people do. Moreover, this is not the correct intuition to employ to understand what's going on: there are no "massive matrix inversions" here, just a simple iterative algorithm for extracting the dominant eigenvector of a matrix.
Furthermore, you've got it exactly backwards regarding the "connection" between PageRank and light transfer. Since the Markov process used to model a web surfer in the PageRank paper is operating on a discrete domain with an easily-calculable transition function, the stationary distribution (or ranking) can be determined exactly. In rendering, you have a continuous problem for which Markov chain Monte Carlo techniques provide one of the most efficient ways to approximate the solution...but you have to actually simulate a Markov chain to get it (see, for instance, Veach's seminal paper on Metropolis Light Transport). Computing PageRank is an "easy" problem, by comparison.
Re: (Score:1, Redundant)
Re: (Score:3, Insightful)
Maybe this is just the elitist snob in me, but I don't feel that the latest American Idol singer is really a thousand times better than Billie Holliday, just because a thousand times more people listen to him than to her.
You are measuring the wrong thing. Google isn't measuring who is 'better,' it is trying to measure what page is more interesting to a web surfer, and pages tend to be more popular because they are more interesting to more people. Thus if you do a search for Brittany, you are more likely to find Brittany Spear's fan club than you are an academic study of why her beautiful innocence was so popular (and oh yes was it beautiful!). People who are looking for more specific academic things learn to add extra sea
Re: (Score:2)
> if Google knows that you are mainly interested in academic sorts of things, then it can automatically return that sort of thing when you do a search for Brittany.
What would be better is if you can choose an "Aspect" or "Point of View" or "Stereotype" for a search. After all I could be doing a search on behalf of someone else. Or I could be interested at different things at different times.
So say I pick the "T
Re: (Score:3, Informative)
Pagerank isn't just a citation count; it's defined recursively, such that a link from a page with a high pagerank is worth more than a link from a page with low pagerank. Similarly, a link from a page with many outlinks is worth less than a link from a page with the same rank but few outlinks.
It does turn out to be more of a popularity contest than a quality metric, though. I think yo
Re: (Score:1)
It would be a problem if your search for "Billie Holiday" would return links to American Idol. Pagerank is not the WHERE clause, it's the ORDER BY clause.
Or there's the number ... (Score:5, Funny)
indeed it is not new (Score:1, Insightful)
In many different types of jobs, people use the counts the number of times their research papers have been referenced and quoted with different "points" depending on where it was quoted. Fx. someone working with medicine hos has his work referenced in The Lancet, counts more than a reference in local-hillbilly-news.
I belive there are sources collects this information. Sorry for being so vague, but I can't remember the specifics. (but hey, isn't that just what we do i Slashdot comments)
additional ranking algorithm in the 1940s paper (Score:5, Funny)
allowed pages to be ranked and categorized according to whether it was "insightful," "interesting," "informative," "funny," "flamebait," or "troll."
Peer Review (Score:2, Offtopic)
is all page rank is.
Re: (Score:2)
Vistas in Information Handling, Spartan Press 1962 (Score:2, Interesting)
The most amazing computer book ever. It has Doug Englebart's first description of “augmenting the human intellect” using computers. It describes what we know now as windows (generic) with pointing devices. It has an early linear document retrieval system using page ranks based on word co-occurrences and it has an early language translation system (Russian to English with examples of translating Soviet missile papers). What a preview of things to come.
It is worth a read just to get into the h
Quite a difference from theory to practice! (Score:2)
I guess previous work had the idea right, but actually building a system which can handle millions of links and reply in no time is not a small feature.
This reminds me of the discussion we had previously about the gap from research prototype transistors to having factories actually deliver them.
I did the same thing, albeit not in the 40s (Score:2)
Back in the late 90s I created a relevance ranking system for my employer to rank the output of our legal research system. Similar to a hyperlink, legal documents have a unique references. Sometimes they're created by the publisher such as West (now Thomson) and their Federal Supplement and other times for unpublished documents it's a docket number from the court. Long story short, the documents were indexed and at run time using a combination of hit density and the number of times a document was referred t
Prior art? (Score:1)
Re: (Score:2)
Two things:
1) Google does not hold a patent on PageRank. Stanford does.
2) If you read the patent, it's more than just the ranking system. At least as far as I can
tell. I am not a patent lawyer, of course.
Re: (Score:2)
It is still a quite relevant question, since in the wikipedia article it says:
Google has exclusive license rights on the patent from Stanford University.
other prior work (Score:2)
The mathematics of PageRank go back a century. There have been many different applications since then, including to hypertext and the web. From Wikipedia:
As such, the algorithm wasn't new, but Google was the firs
I can show you one form the ~10s or ~20s (Score:2)
Re: (Score:2)
actually, could think of better ranking systems for movie stars: ranking factor for each role (lead=1000, other starring role=100, minor speaking role = 10, extra = 1) summed for all movies. maybe even scale by gross receipts for each movie GNP-deflator normalized to 1970 dollars.
link to the actual paper (Score:2, Interesting)
The summaries were intriguing but lame. Here's the real thing (preprint):
http://arxiv.org/abs/1002.2858 [arxiv.org]
Author's page is here:
http://users.dimi.uniud.it/~massimo.franceschet/ [uniud.it]
Interesting stuff.
Journalists Finally Put Two and Two Together (Score:1)
Sociologists use it in social networks too (Score:2)