Slashdot Mirror

← Back to Stories (view on slashdot.org)

Compute Google's PageRank 5 Times Faster

Posted by timothy on from the hypercustom dept.

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

9 of 140 comments (clear)

  1. Let me guess... by RollingThunder · · Score: 5, Funny

    Feeding the pigeons amphetamines?

    1. Re:Let me guess... by irokitt · · Score: 5, Funny

      No, They'll replace the pigeons with roadrunners.

      --
      If my answers frighten you, stop asking scary questions.
  2. CmdrTaco, ScienceBlog editor? by jbellis · · Score: 5, Interesting
    A 5 times speedup is still many orders of magnitude too slow to personalize terabytes of data for millions of customers. That's just ludicrous. But somehow Science Blog puts "...may make it realistic to calculate page rankings personalized for an individual's interests" in their abstract when the actual article from National Science Foundation says nothing of the sort:
    Computing PageRank, the ranking algorithm behind the Google search engine, for a billion Web pages can take several days. Google currently ranks and searches 3 billion Web pages. Each personalized or topic-sensitive ranking would require a separate multi-day computation, but the payoff would be less time spent wading through irrelevant search results. For example, searching a sports-specific Google site for "Giants" would give more importance to pages about the New York or San Francisco Giants and less importance to pages about Jack and the Beanstalk.
    ...
    The complexities of a personalized ranking would require [far] greater speed-ups to the PageRank calculations. In addition, while a faster algorithm shortens computation time, the issue of storage remains. Because the results from a single PageRank computation on a few billion Web pages require several gigabytes of storage, saving a personalized PageRank for many individuals would rapidly consume vast amounts of storage. Saving a limited number of topic-specific PageRank calculations would be more practical.
    Clearly the ScienceBlog and /. editors share more than a work ethic, or, uh, lack thereof. Next up: CmdrTaco's secret double life revealed!
  3. How far we've come by L.+VeGas · · Score: 5, Funny

    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
  4. Re:Lets see... by Anonymous Coward · · Score: 5, Informative

    RTA. PageRankings are computed in advance and take several days. A 5x increase in speed means specialized rankings could be computed.

  5. Hmmm by Linguica · · Score: 5, Funny

    Geek: I invented a program that downloads porn off the internet one million times faster.
    Marge: Does anyone need that much porno?
    Homer: :drools: One million times...

  6. Why? by johannesg · · Score: 5, Funny
    Why, actually? Google is a free service, isn't it? And it is becoming more and more a normal part of many people's lifes. Coupled with an always on connection it has certainly become an extension of my own brain.

    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!

    1. Re:Why? by JDWTopGuy · · Score: 5, Funny

      You missed a step:

      2026 - Google introduces helper bot known as "Agent Smith." Hackers who mess with the Matri, I mean Google, suddenly disappear.

      --
      Ron Paul 2012
  7. Re:Bullshit by Klaruz · · Score: 5, Insightful

    Umm... For the most part Stanford Researchers == Google Researchers.

    Google came about from a stanford research project. There's a good chance the people who are responsable for the speedup either allready knew about pagerank from working with the founders, or signed an nda.

    I haven't read the article, but I bet it hints at that.