3 ms·
PageRank actually had a predecessor called HITS (according to some sources HITS were developed before PageRank, according to others they were contemporaries), a
by 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 agoPage'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.