5 ms·

Didn't read the document, but hopefully it mentions PageRank, the prime example of using probabilistic graphical models to rank nodes in a directed graph. More

Didn't read the document, but hopefully it mentions PageRank, the prime example of using probabilistic graphical models to rank nodes in a directed graph. More info: https://www.amazon.com/Probabilistic-Graphical-Models-Principles-Computation/dp/0262013193 https://www.amazon.com/Probabilistic-Graphical-Models-Princi... I've heard that Google and Baidu essentially started at the same time, with the same algorithm discovery (PageRank). Maybe someone can comment on if there was idea sharing or if both teams derived it independently.

mach1ne 5y ago
Didn't Larry Page and Sergey Brin openly publicize the PageRank algorithm? It'd seem more likely that Baidu just copypasted the idea.
- swyx 5y ago
  Baidu's patent predated theirs by 2 years https://news.ycombinator.com/item?id=30419414 https://news.ycombinator.com/item?id=30419414
oneoff786 5y ago
The basic concept behind page rank is pretty obvious. If you stare at a graph for a while, it’ll probably be your big idea if you try to imagine centrality calculations. Implementing it and catching edge cases isn’t trivial
andi999 5y ago
I heard that the first approach of google was using/adapting an published algorithm which was used to rank scientific publications from the network of citations. Not sure if this is the algorithm you mentioned though.
- divbzero 5y ago
  The ranking of scientific publications based on citations you’re describing is impact factor [1]. I haven’t heard that as an inspiration for Larry Page’s PageRank [2] but that is plausible. [1]: https://en.wikipedia.org/wiki/Impact_factor https://en.wikipedia.org/wiki/Impact_factor [2]: https://en.wikipedia.org/wiki/PageRank https://en.wikipedia.org/wiki/PageRank
  - andi999 5y ago
    Impact factor ranks Journals, not Authors or papers. I googled the original paper: https://scholar.google.de/scholar?hl=de&as_sdt=0%2C5&q=the+page+rank+author%3Apage&btnG= https://scholar.google.de/scholar?hl=de&as_sdt=0%2C5&q=the+p... (I do not want to link directly to the pdf shown in the search result). Section 2.1 deals with related work: "There has been a great deal of work on academic citation analysis [Gar95]. Go man [Gof71] has published an interesting theory of how information flow in a scienti c community is an epidemic process......" (and more) I think that paper is worth a read.
ppsreejith 5y ago
From the wikipedia page of Robin Li, co-founder of Baidu: https://en.wikipedia.org/wiki/Robin_Li#RankDex https://en.wikipedia.org/wiki/Robin_Li#RankDex > In 1996, while at IDD, Li created the Rankdex site-scoring algorithm for search engine page ranking, which was awarded a U.S. patent. It was the first search engine that used hyperlinks to measure the quality of websites it was indexing, predating the very similar algorithm patent filed by Google two years later in 1998.
nabla9 5y ago
Page Rank is just application of eigenvalues into ranking. The idea came first up in the 70's. https://www.sciencedirect.com/science/article/abs/pii/0306457376900480 https://www.sciencedirect.com/science/article/abs/pii/030645... and several times afterward before PageRank was developed.
bjourne 5y ago
PageRank actually had a predecessor called HITS (according to some sources HITS were developed before PageRank, according to others they were contemporaries), an algorithm developed by Jon Kleinberg for ranking hypertext documents. https://en.wikipedia.org/wiki/HITS_algorithm https://en.wikipedia.org/wiki/HITS_algorithm However, Kleinberg stayed in academia and never attempted to commercialize his research like Page and Brin did. HITS was more complex than PageRank and context-sensitive so queries required much more computing resources than PageRank. PageRank is kind of what you get if you take HITS and remove the slow parts. What I find very interesting about PageRank is how you can trade accuracy for performance. The traditional way of calculating PageRank by means of squaring a matrix iteratively until it reaches convergence gives you correct results but is sloooooow. For a modestly sized graph it could take days. But if accuracy isn't that important you can use Monte Carlo simulation and get most of the PageRank correct in a fraction of the time of the iterative method. It's also easy to parallelize.
- jll29 5y ago
  Page's PageRank patent references HITS: Jon M. Kleinberg, "Authoritative sources in a hyperlinked environment," 1998, Proc. Of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 668-677.
screye 5y ago
Given that Pagerank was literally invented and named after Larry Page, I would think that Google had a head start. That being said, Page Rank is a more a stellar example of adapting an academic idea into practice, than a statistical idea in and of itself. Afterall, it is 'merely' the stationary distribution for a random walk over an undirected graph. I say 'merely' with a lot of respect, because the best ideas often feel simple in hindsight. But, it is that simplicity that makes them even more impressive.
- alanbernstein 5y ago
  > Given that Pagerank was literally invented and named after Larry Page, I would think that Google had a head start. I don't think this means much. The history of science and technology is full of examples of results named after someone other than the first person to find them. https://en.wikipedia.org/wiki/List_of_examples_of_Stigler%27s_law https://en.wikipedia.org/wiki/List_of_examples_of_Stigler%27.... In fact, based on the other comments in this thread, it seems that Pagerank being named after Larry Page is itself one of these examples.
mianos 5y ago
The sort of methods 'PageRank' uses already existed. It reminds of Apple `inventing` (air quotes) the mp3 player. It didn't, it applied existing technology, refined it and publicized it. They did not invent it but maybe 'inventing' something is only a very small part of making something useful for many people.

mach1ne 5y ago

Didn't Larry Page and Sergey Brin openly publicize the PageRank algorithm? It'd seem more likely that Baidu just copypasted the idea.

swyx 5y ago
Baidu's patent predated theirs by 2 years https://news.ycombinator.com/item?id=30419414 https://news.ycombinator.com/item?id=30419414

oneoff786 5y ago

The basic concept behind page rank is pretty obvious. If you stare at a graph for a while, it’ll probably be your big idea if you try to imagine centrality calculations. Implementing it and catching edge cases isn’t trivial

andi999 5y ago

I heard that the first approach of google was using/adapting an published algorithm which was used to rank scientific publications from the network of citations. Not sure if this is the algorithm you mentioned though.

divbzero 5y ago
The ranking of scientific publications based on citations you’re describing is impact factor [1]. I haven’t heard that as an inspiration for Larry Page’s PageRank [2] but that is plausible. [1]: https://en.wikipedia.org/wiki/Impact_factor https://en.wikipedia.org/wiki/Impact_factor [2]: https://en.wikipedia.org/wiki/PageRank https://en.wikipedia.org/wiki/PageRank
- andi999 5y ago
  Impact factor ranks Journals, not Authors or papers. I googled the original paper: https://scholar.google.de/scholar?hl=de&as_sdt=0%2C5&q=the+page+rank+author%3Apage&btnG= https://scholar.google.de/scholar?hl=de&as_sdt=0%2C5&q=the+p... (I do not want to link directly to the pdf shown in the search result). Section 2.1 deals with related work: "There has been a great deal of work on academic citation analysis [Gar95]. Go man [Gof71] has published an interesting theory of how information flow in a scienti c community is an epidemic process......" (and more) I think that paper is worth a read.

ppsreejith 5y ago

From the wikipedia page of Robin Li, co-founder of Baidu: https://en.wikipedia.org/wiki/Robin_Li#RankDex https://en.wikipedia.org/wiki/Robin_Li#RankDex > In 1996, while at IDD, Li created the Rankdex site-scoring algorithm for search engine page ranking, which was awarded a U.S. patent. It was the first search engine that used hyperlinks to measure the quality of websites it was indexing, predating the very similar algorithm patent filed by Google two years later in 1998.

nabla9 5y ago

Page Rank is just application of eigenvalues into ranking. The idea came first up in the 70's. https://www.sciencedirect.com/science/article/abs/pii/0306457376900480 https://www.sciencedirect.com/science/article/abs/pii/030645... and several times afterward before PageRank was developed.

bjourne 5y ago

PageRank actually had a predecessor called HITS (according to some sources HITS were developed before PageRank, according to others they were contemporaries), an algorithm developed by Jon Kleinberg for ranking hypertext documents. https://en.wikipedia.org/wiki/HITS_algorithm https://en.wikipedia.org/wiki/HITS_algorithm However, Kleinberg stayed in academia and never attempted to commercialize his research like Page and Brin did. HITS was more complex than PageRank and context-sensitive so queries required much more computing resources than PageRank. PageRank is kind of what you get if you take HITS and remove the slow parts. What I find very interesting about PageRank is how you can trade accuracy for performance. The traditional way of calculating PageRank by means of squaring a matrix iteratively until it reaches convergence gives you correct results but is sloooooow. For a modestly sized graph it could take days. But if accuracy isn't that important you can use Monte Carlo simulation and get most of the PageRank correct in a fraction of the time of the iterative method. It's also easy to parallelize.

jll29 5y ago
Page's PageRank patent references HITS: Jon M. Kleinberg, "Authoritative sources in a hyperlinked environment," 1998, Proc. Of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 668-677.

screye 5y ago

Given that Pagerank was literally invented and named after Larry Page, I would think that Google had a head start. That being said, Page Rank is a more a stellar example of adapting an academic idea into practice, than a statistical idea in and of itself. Afterall, it is 'merely' the stationary distribution for a random walk over an undirected graph. I say 'merely' with a lot of respect, because the best ideas often feel simple in hindsight. But, it is that simplicity that makes them even more impressive.

alanbernstein 5y ago
> Given that Pagerank was literally invented and named after Larry Page, I would think that Google had a head start. I don't think this means much. The history of science and technology is full of examples of results named after someone other than the first person to find them. https://en.wikipedia.org/wiki/List_of_examples_of_Stigler%27s_law https://en.wikipedia.org/wiki/List_of_examples_of_Stigler%27.... In fact, based on the other comments in this thread, it seems that Pagerank being named after Larry Page is itself one of these examples.

mianos 5y ago

The sort of methods 'PageRank' uses already existed. It reminds of Apple `inventing` (air quotes) the mp3 player. It didn't, it applied existing technology, refined it and publicized it. They did not invent it but maybe 'inventing' something is only a very small part of making something useful for many people.