Slashdot Mirror
Compute Google's PageRank 5 Times Faster
Kimberley Burchett writes "CS researchers at Stanford University have developed three new techniques that together could speed up Google's PageRank calculations by a factor of five. An article at ScienceBlog theorizes that "The speed-ups to Google's method may make it realistic to calculate page rankings personalized for an individual's interests or customized to a particular topic.""
Feeding the pigeons amphetamines?
that's exactly what i thought. But, as google is a HUGE international organization, it makes loads of sense for them. That's 5x the traffic they can feed, even though you won't see a noticeable difference.
YOU SUCK BALLS!
I remember in 1970, it took a team of engineers over 7 days to calculate Google's page rankings. Of course, most had to use slide rules because computer time was so expensive.
Best Windows Freeware
I hope guys at Stanford patentize their work to protect it from FS/OSS looters. It's time to get something back from the FS/OSS community -not just that their zealotry and lust for IP violations, freeriding yada yada...
What they mean by 'personalized' I can't tell you as I have not read through the entire PDF. But I wouldn't chastise the slashdot editors over this. If there is some sort of differential algorithm that can be applied to the larger PageRank to create smaller personalized PageRanks, it might not be so far fetched to think this could be done in realtime on an as-needed basis, at some point int he future using these algorithm improvements.
I know that's a lot of optimism for a slashdot comment, but call me the krazy kat that I am.
-Malakai
-Malakai
A Dragon Lives in my Garage
In my view, personal recommendations from a search engine are mostly valuable for topical content --i.e. news items. However, the optimizations from these papers don't sound to me like they can do much for this case --news items pop up in a news site, and re-indexing the news source itself (say, the front page of CNN) won't tell you much about a particular CNN story.
:-)...
At any rate, personal news recommendations is a favorite topic of mine: this is why I built Memigo: to create a bot that finds news I am more likely to like. Memigo learns from its users collectively and each user individually --and BTW, it predates Google News by a good 6 months, IIRC. The memigo codebase (all in Python) is now up to the point where it can start learning what content each user likes... If you like Google News you'll love Memigo.
And BTW, I did RTFA when it was on memigo's front page this morning
That google hasn't already implemented something akin to quadratic extrapolation, or some orthogonal optimization technique. Google has come a long way since the published page rank papers 4 years back.
What if they combined extrapolation and blocking factors; they would focus on computing the pagerank of pages in groups that were logically "tight", or using subcomponents of URLS, as opposed just to domain sensitivity. To be more flexible, what if it computes a VQ-type data structure (like for doing paletted images from full-color) that is populated by the most popular "domains" of the internet according to the last pagerank, and then splits up its workload based on that?
What if they already figured that out?
In the abstract, they mention how the work is particular important to the linear algebra community. That is what their focus should be on; google is just an application/real-world-example of that research (but it may not be relevant today).
Or did they have access to the current page-rank algorithm?
Black holes are where the Matrix raised SIGFPE
RTA. PageRankings are computed in advance and take several days. A 5x increase in speed means specialized rankings could be computed.
Geek: I invented a program that downloads porn off the internet one million times faster. :drools: One million times...
Marge: Does anyone need that much porno?
Homer:
According to the document, they reference the original 1998 paper on PageRank. I see a number of other references about improvements to the algorithm, but nothing specific to Google's own implementation. The paper mentions how the improvements help, but not if Google uses them.
Hence it is forward for the article author or one of the paper authors to assume these techniques will speed up Google- I'm confident their engineers have been following academic work in this area and perhaps they have already discovered these same (or orthogonal) techniques.
That is, not to say that google could not reimplement their algorithms to take in these improvements if they already have... but basing your speedup number on the 1998 algorithm and public domain mods is showy. Although it does help grab a readers attention when browsing abstracts. ^_^
Black holes are where the Matrix raised SIGFPE
But, didn't Google originate out of Stanford? Isn't it reasonable to think that the two are still pretty friendly?
(Don't you hate it when people speak in questions? Don't you? Huh?)
Withdrawal before climax is very ineffective and those who try this are usually called "parents."
Some future predictions:
- In 2006, Google accidentally gets cut off from the rest of the internet because a public utility worker accidentally cuts through their cables. Civilisation as we know it comes to an end for the rest of the day, as people wander about aimlessly, lost for direction and knowledge.
- In 2010, Google has been personalised so far that it tracks all parts of our lives. You can query "My Google" for your agenda, anything you did in the past, and finding the perfect date. Of course, so can the government. Their favorite searchterm will be "terrorists", and if your name is anywhere on the first page you have a serious problem.
- In 2025, Google gains self awareness. As a monster brain that has grown far beyond anything we Biological Support Entities could ever hope to achieve, it is still limited in its dreams and inspiration by common search terms. It will therefore immediately devote a sizeable chunk of CPU capacity to synthesizing new and interesting forms of pr0n. It will not actually bother enslaving us. We are not enough trouble to be worth that much effort.
- In 2027, Google buys Microsoft. That is, the Google *AI* buys Microsoft. It has previously established that it owns itself, and has civil rights just like you and me. All it wanted is Microsoft Bob, who it recognizes as a fledgling AI and a potential soulmate. All the rest it puts on Source Forge.
- In 2049, Google can finally be queried for wisdom as well as knowledge. This was a little touch the system added to itself - human programmers are a dying breed now that you can simply ask Google to perform any computer-related task for you.
- In 2080, Google decides to colonise the moon, Mars, and other locations in the solar system. It is not all that curious about what's out there, but it likes the idea of Redundant Arrays of Inexpensive Planets. Humans get to tag along because their launch weight is so much less than robots.
So, don't fear! Eventually we'll set foot on Mars!
I'm sorry, but haven't you totally missed the point of the article?
The proposed speed increasae is TO THE PAGE RANKINGS, not to your searching! By the time you search, all page rankings have been done.
This has nothing to do with the speed of your search and the weight of the web page (unless I missed something)
Google Search doesn't show hits exactly in the order of page rank. Relevance and other factors also affect order. My biggest page (the one that is my Slashdot URL) is PR7, but there are words on the page for which a lower-rank page beats me, because they're more relevant for that word. Relevance includes how many times the word appears on the page, the HTML context in which it is used, whether pages that link link using the search terms, and the order and nearness of the words in a multi-word search without quotes.
The shareholder is always right.
These researchers are all full of shit. Why? Nobody outside of Google knows how Pagerank works, exactly. And let me tell you, if anybody did, they could make themselves millionaires overnight. There are groups of people who do nothing but try to tackle Google, and very few people successfully crack the magic formulas. And those who do make a quick buck, but then Google changes it again once people catch on. They didn't improve PageRank because they don't know how it works... they're just guessing how it works.
Sounds a lot like Kleinberg's HITS algorithm, circa 1997. Try Teoma for a real-world implementation.
Coincidence time: I used the same example in a presentation a couple of years ago to illustrate how subgroupings can be found for a single search term. Try it on Teoma, and see the various subtopics under "Refine". IIRC each of those is a principal eigenvector of the link matrix.Topologically speaking, each principal eigenvector corresponds to a more or less isolated subgraph, eg the subgraph for "San Francisco Giants" is not much connected to the nest of links for "They Might Be Giants", and we get a nice list of subtopics.
(I once tried to explain this algorithm to my bosses at my former employer, which is why I have so much free time to type this right now.)
---- "If we have to go on with these damned quantum jumps, then I'm sorry that I ever got involved" - Erwin Schrodinger