Scientist Finds PageRank-Type Algorithm from the 1940s | Hacker News Reader

Scientist Finds PageRank-Type Algorithm from the 1940s

technologyreview.com

25 pointsca98am7911 comments

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.

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.

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.

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

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.

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.

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.

Agreed, basic research is worlds different than business.

What does Pittsburgh have to do with search engines?

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

AFAIK, Google PageRank is part-technology, part-PR.

As Paul Graham says (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.

Reply on news.ycombinator.com