4 ms·

Scientist Finds PageRank-Type Algorithm from the 1940s

25 points by ca98am79 17y ago

pgbovine 17y ago
very cool, i like how the author didn't do any trollish editorializing like "lulz brin and page were soooooo unoriginal, omgz pagerank is so not innovative it's been around for 60 yearz, anybody could've built googlez" scientific discoveries inevitably build off of prior work, so it's nice to see this sort of article acknowledging predecessors to seemingly-modern ideas without denigrating them.
beagle3 17y ago
PageRank is essentially a version of the "stationary probability distribution of a discrete markov process" applied to web pages being states and link being transitions. I remember learning the math back in '96, and it was old then -- perhaps 40 years old. What is interesting about this finding, is that it was _already_ applied to evaluating scientific papers and quotes.
ruang 17y ago
Makes you wonder why none of these people made their own search engine.
- wanderr 17y ago
  In the 40's? By the time they would have had an opportunity to apply this to making a search engine, its unlikely that they would be in a position to drop everything they were doing and create a startup, assuming they would even remember the research they did so long ago and realize the insane value of making a search engine like that.
  - chancho 17y ago
    I think ruang was referring to Kleinberger, who applied the idea directly to web pages, as opposed to scientific journals or economies. He did it only short while before Page and Brin, and they even cited him. As to why he didn't make a search engine, I'm guessing it's because CMU is in Pittsburgh.
    - neilc 17y ago
      Kleinberg, not Kleinberger, and he's a prof at Cornell, not CMU. I'd guess it has less to with geography, and more to do with the fact that Kleinberg is a (brilliant, celebrated) academic who probably wasn't very interested in doing a startup.
      - elblanco 17y ago
        Agreed, basic research is worlds different than business.
    - joshu 17y ago
      What does Pittsburgh have to do with search engines?
- awa 17y ago
  During the time when Google came up, there was a considerable interest in search engines in academia, E.g. Some papers by Udi Manber, a prof at Uni of Arizona at that time had these papers: U. Manber, and Peter Bigot, ``The Search Broker,'' First Usenix Symp. on Internet Technologies and Systems, Monterey, CA (December 1997), pp. 231-240. # R. Muth, and U. Manber, ``Approximate Multiple String Search,'' the 7th Annual Combinatorial Pattern Matching Symp., Laguna Beach, CA (June 1996), pp. 75-86. # U. Manber, M. Smith, and B. Gopal, ``WebGlimpse -- Combining Browsing and Searching,'' Usenix 1997 Annual Technical Conference, Anaheim, CA (January 1997), pp. 195-206. U. Manber and P.A. Bigot, ``Connecting Diverse Web Search Facilities,'' Bulletin of the Technical Committee on Data Engineering 21 (June 1988), pp. 21-27. Ofcourse he was gobbled up by Yahoo at that time and is now a VP at Google
- resdirector 17y ago
  AFAIK, Google PageRank is part-technology, part-PR. As Paul Graham says (http://www.paulgraham.com/revolution.html#f1n http://www.paulgraham.com/revolution.html#f1n), what made Google wasn't PageRank: they would have succeeded with a different algorithm. What made Google was that they cared about search and did it really well.
elblanco 17y ago
Everybody knows about Markov's work in this sense. The reason it worked so well was not just Google's application of Markov probability distributions, but their integration with the then predominant search strategy of vector space models for page retrieval. The key insight Brin and Page had was to incorporate Markov's work as a scoring metric along with the results from a vector space search (it's all matrices anyways) and then generalize that to include other metrics to help weight pages to the top that are more likely to be what people are looking for. PageRank != Markov processes only, it's not even just Markov + Vector retrieval, if it was they'd be good to go and their staff of search quality engineers would be in the single digits. But Google has a large number of engineers who's sole purpose is to find ways of tweaking that basic weighting formula, using the user's query (and a handful of other metrics like custom search preferences, language, etc.) to float up good pages and sink down bad pages. I wouldn't be surprised if even Kleinberg's HITS hasn't made it into the formula in some way.

25 points by ca98am79 17y ago

very cool, i like how the author didn't do any trollish editorializing like "lulz brin and page were soooooo unoriginal, omgz pagerank is so not innovative it's been around for 60 yearz, anybody could've built googlez" scientific discoveries inevitably build off of prior work, so it's nice to see this sort of article acknowledging predecessors to seemingly-modern ideas without denigrating them.

beagle3 17y ago

PageRank is essentially a version of the "stationary probability distribution of a discrete markov process" applied to web pages being states and link being transitions. I remember learning the math back in '96, and it was old then -- perhaps 40 years old. What is interesting about this finding, is that it was _already_ applied to evaluating scientific papers and quotes.

ruang 17y ago

Makes you wonder why none of these people made their own search engine.

wanderr 17y ago
In the 40's? By the time they would have had an opportunity to apply this to making a search engine, its unlikely that they would be in a position to drop everything they were doing and create a startup, assuming they would even remember the research they did so long ago and realize the insane value of making a search engine like that.
- chancho 17y ago
  I think ruang was referring to Kleinberger, who applied the idea directly to web pages, as opposed to scientific journals or economies. He did it only short while before Page and Brin, and they even cited him. As to why he didn't make a search engine, I'm guessing it's because CMU is in Pittsburgh.
  - neilc 17y ago
    Kleinberg, not Kleinberger, and he's a prof at Cornell, not CMU. I'd guess it has less to with geography, and more to do with the fact that Kleinberg is a (brilliant, celebrated) academic who probably wasn't very interested in doing a startup.
    - elblanco 17y ago
      Agreed, basic research is worlds different than business.
  - joshu 17y ago
    What does Pittsburgh have to do with search engines?
awa 17y ago
During the time when Google came up, there was a considerable interest in search engines in academia, E.g. Some papers by Udi Manber, a prof at Uni of Arizona at that time had these papers: U. Manber, and Peter Bigot, ``The Search Broker,'' First Usenix Symp. on Internet Technologies and Systems, Monterey, CA (December 1997), pp. 231-240. # R. Muth, and U. Manber, ``Approximate Multiple String Search,'' the 7th Annual Combinatorial Pattern Matching Symp., Laguna Beach, CA (June 1996), pp. 75-86. # U. Manber, M. Smith, and B. Gopal, ``WebGlimpse -- Combining Browsing and Searching,'' Usenix 1997 Annual Technical Conference, Anaheim, CA (January 1997), pp. 195-206. U. Manber and P.A. Bigot, ``Connecting Diverse Web Search Facilities,'' Bulletin of the Technical Committee on Data Engineering 21 (June 1988), pp. 21-27. Ofcourse he was gobbled up by Yahoo at that time and is now a VP at Google
resdirector 17y ago
AFAIK, Google PageRank is part-technology, part-PR. As Paul Graham says (http://www.paulgraham.com/revolution.html#f1n http://www.paulgraham.com/revolution.html#f1n), what made Google wasn't PageRank: they would have succeeded with a different algorithm. What made Google was that they cared about search and did it really well.

elblanco 17y ago

Everybody knows about Markov's work in this sense. The reason it worked so well was not just Google's application of Markov probability distributions, but their integration with the then predominant search strategy of vector space models for page retrieval. The key insight Brin and Page had was to incorporate Markov's work as a scoring metric along with the results from a vector space search (it's all matrices anyways) and then generalize that to include other metrics to help weight pages to the top that are more likely to be what people are looking for. PageRank != Markov processes only, it's not even just Markov + Vector retrieval, if it was they'd be good to go and their staff of search quality engineers would be in the single digits. But Google has a large number of engineers who's sole purpose is to find ways of tweaking that basic weighting formula, using the user's query (and a handful of other metrics like custom search preferences, language, etc.) to float up good pages and sink down bad pages. I wouldn't be surprised if even Kleinberg's HITS hasn't made it into the formula in some way.