10 ms·
Google's PageRank patent has expired (2019)
- klez 4y agoPrevious discussion: https://news.ycombinator.com/item?id=20067712 https://news.ycombinator.com/item?id=20067712
- jedimastert 4y agoA CS YouTube channel (Reducible) just put out a fantastic video about the PageRank algorithm: https://www.youtube.com/watch?v=JGQe4kiPnrU https://www.youtube.com/watch?v=JGQe4kiPnrU
- DonHopkins 4y agoI though PageRank rated pages based on their rank smell. Now that the patent's expired, somebody can create a free open source implementation called PageStink.
- pvg 4y agoStill beyond what readily available tech can do. PageCrank, on the other hand...
- failTide 4y agoRevolutionary at the time - but have there have been any new breakthrough strategies/algorithms for search in the last decade?
- axg11 4y agoIn general the biggest breakthrough in that space has been machine learning powered relevance scoring and NLP. PageRank worked by using high level metadata (links between pages). We now have methods that can incorporate metadata information and analysis of the content itself.
- swiftDaemon 4y agoyes https://youtu.be/6HYdTtIoyts https://youtu.be/6HYdTtIoyts
- albertzeyer 4y agoThis is a video about the "21e8 index". I have never heard about that. There seem to be one scientific paper about it, by Provides Ng, "21E8: Coupling Generative Adversarial Neural Networks (GANS) with Blockchain Applications in Building Information Modelling (BIM) Systems" from 2021 which does not have any other citation. Also Google does not really provide any information on 21e8. How is this a representative example?
- atty 4y agoProof of work to rank pages? That sounds like the worst idea I’ve ever heard. I’m no fan of Google injecting ads into the top spots of their results but at least you can get to the “real” results by just scrolling down. With this paradigm, every link becomes paid “ad”, and the ranking is completely dominated by companies and individuals with big pockets, not any objective or even subjective measure of the quality. And they’re all ads paid for by wasting energy.
- dylan604 4y agoSure, SEO gammification(TM). You didn't specificy that the breakthrough needed to be useful to the users or the people wanting to monetize search.
- tyingq 4y agoI'm not sure how useful this might be to anyone anymore. Google still uses it for the base ranking. But, the results are then run through a variety of add-on ML pipelines, like Vince (authority/brand power), Panda (inbound link quality), Penguin (content quality), and many others that target other attributes (page layout, ad placement, etc). Then there's also more granular weightings for things like "power within a niche", where a new page might do well for plumbing (because of other existing pages on the site), but wouldn't automatically have any authority for medical topics.
- mceoin 4y agoIs there a way to figure out how a site (or page) is performing against Vince, Panda and Penguin?
- ramraj07 4y agoWhere can I learn more about all these models you mention?
- tyingq 4y agoI'm not sure. Most of that is from information Matt Cutts used to share when he was the public face of Google's search quality team. Since he left in 2014, they've been very quiet about the space. If you search for things like "matt cutts panda", "matt cutts vince", and so on, you'll see some of what he used to share.
- 5evOX5hTZ9mYa9E 4y agoAnd yet, the results are worse and worse.
- TuringNYC 4y agoCan anyone explain why the PageRank patent was valuable when an alternative (Prof Jon Kleinberg's Hypertext Induced Topic Search or HITS algo) was published at the same time and available for use? https://en.wikipedia.org/wiki/HITS_algorithm https://en.wikipedia.org/wiki/HITS_algorithm
- 988747 4y agoFrom your linked Wikipedia page: "it is executed at query time, not at indexing time, with the associated hit on performance that accompanies query-time processing" - for a search engine that planned to take over the Web that might have been a dealbreaker.
- iamcurious 4y agoSeems like an obvious optimization though. Is that enough to grant a patent?
- saiajc 4y agoKleinberg's HITS algorithm actually came first. PageRank simplified HITS and made it more practical, by performing the ranking mechanism in batch mode for the entire web graph. If you read the original HITS paper, you'll see that HITS computes the top two eigenvectors for the cluster of all pages containing the query word (and pages pointing to those pages). Computing new eigenvectors for every search query obviously is much slower than PageRank.
- srean 4y agoThe HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. For an algorithm that is used in the real world where commercial interests rules, sensitivity to adversarial attacks is very important -- Game Theory inspired algorithms will not be out of place. Note, one can definitely adopt 'hardening' strategies for both HITS and PageRank. Even around 2004 a naive, as presented in the tech-report, version of the PageRank algorithm was unusable without tweaks. Had you tried the unmodified version, you would have found that the top tier pages were mostly porn. There's also the fact that PageRank was presented as a query independent computation that could be done ahead of time and HITS as a query dependent computation. A resourceful enough person could however modify HITS into topic-wise precomputed HITS scores to be combined at run time based on the query. Ok so here is how one can game HITS. Create a harvester page that points to lots and lots of popular, high traffic pages on the internet. By virtue of doing this it can accumulate a lot of Hubs score which it can redirect as an Authority score to an intended page.
- swiftDaemon 4y ago21e8 replaces pagerank https://youtu.be/6HYdTtIoyts https://youtu.be/6HYdTtIoyts
- aneil 4y agoHow did they even get that patent? It's a well known 70s era bibliometric algorithm.
- dylan604 4y agoConan The Librarian should have protected us from the evil algo
- photochemsyn 4y agoThe patent was actually assigned to Stanford University, and Google then licensed it (this is also how most pharmaceutical discovery is patented and licensed). A fundamental problem is that these patents all rely on federal funds from US taxpayers to one extent or the other, and while it may make sense for Stanford to hold the patent, there's a strong argument that any US entity should be able to license it (not just one exclusive license in other words). Prior to Bayh-Dole legislation in the 1980s, this was the case for university-held patents: they could be not be exclusively licensed. Repealing that legislation would be a good idea to avoid the rise of monopolisitic behemoths like Google/Alphabet.
- tqkxzugoaupvwqr 4y agoDoesn’t answer the question. Rephrased: Why was the patent granted if prior art existed from the 70s?
- DANK_YACHT 4y agoThe patent approval process isn't perfect. Had you violated the patent, and had Google sued you, you could always argue prior art. What would your evidence be?
- IshKebab 4y agoAs I understand it it's much harder and more expensive to win a prior art claim after a patent has been granted.
- 4y ago
- scroot 4y agoCool. Now let's get the Library of Congress or NARA -- which are natural homes for this kind of thing -- to implement the public option free of profit-driven cruft.
- bogwog 4y agoThat would actually be pretty cool. Too bad government software has a tendency to come out shitty and expensive.
- NateEag 4y agoIf the government committed to the project being OSS, they might be able to recruit some reasonably skilled programmers.
- scroot 4y agoIt's true in the main, but orgs like TTS (tts.gsa.gov) and 18F (18f.gsa.gov) are really changing things. Library of Congress also has a labs group.
- stjohnswarts 4y agoThat's mostly because the bar for entry is very low and the bid goes either 1) guaranteed company because of congressional lobbying or 2) the company bidding the lowest price who has even a -bit- of a change to complete it rather than companies with proven track records to produce at scale.
- Workaccount2 4y agoGoogle search has gotten so bad compared to how it used to be that this might actually be useful.
- marginalia_nu 4y agoPageRank performs fairly poorly on the web as a whole these days, because the nature of linking has changed since 1998. If you constrain it to the parts of the web that is still basically hypertext documents, it's as good as ever. That's largely what I've been doing with my search engine.
- gnramires 4y agoHave you considered widening the definition of 'hyperlink'? For example, using references in text as well. Or also (lightweight) sentiment analysis. For example, I'm sure many people refer to wikipedia all the time, without giving a link. Or Hacker News. This seems like it should represent a "weak link" between those pages. It would probably be worthwhile to use some kind of normalization on pages/domains to avoid spamming to game this system. I also think it's worth exploring a simple reputation system. Why not have reputable users evaluate results? (approve/disapprove buttons) I think almost any reputation-free system will eventually fail to bots or cost a huge amount to win the tug of war against SEO. Reputation mostly solves the issue. Speaking of reputation, I think the great insight would be to apply a ranking algorithms to reputations themselves -- if you can't trust your users, you fall back on the same problem. To rank reputations, clearly PageRank doesn't work because it values all users equally, which is unfortunately not sybil-resistant. I think one approach is to have an "invite system", where your reputation is associated to who invited you, with earlier users having greater weight somehow (also the administrator can manually assign trustworthy users). This also suggests a way to formulate distributed trust. You can join a "trust network" by trusting a certain user(s), and then you import users who they trust as well. (I believe this is the rough idea behind Web of Trust, although I believe WoT is not algorithmic -- it should have been!) The problem with this approach for a practical search engine is that you can't aggregate results (you would need to store each user's vote and compute a personal ranking every time) -- so I think in practice a useful compromise is to give the user a choice of a few "trust sets". You trust <Public User A> here? Join this trust set. You trust <Public User B>? Join this other trust set. (Combining a small number of trust sets should be trivial) As for an algorithm, something like: -- By trusting other users, up to 100*(1-sqrt(N)/N)% [note] of your trust points will be redistributed (diminishing the impact of your choices). [note] Obs: Formula arbitrary, chosen to approach 100% -- The total trust conserves, and phenomena like cyclic trust are not a problem due to conservation.
- dylan604 4y agoThey should have copyrighted it. They could have received new protections each time it was tweaked. If it's good for the Big E Mouse Corp, it should be good for the DontBeEvil types as well. Protection in perpetuity.
- deleted 4y ago[deleted]
- geysersam 4y agoGreat idea. I wonder how that would have played out in court. Any lawyers around?
- TheRealDunkirk 4y agoGoogle is a victim of the googlification of the internet. With “the internet” consisting of about 5-10 walled gardens, each with their own custom search, I find I use general search engines a lot less now anyway.
- karmasimida 4y agoI don't think Google uses this anymore, this is just not relevant these days
- hubraumhugo 4y agoGoogle won because they started early and had the right algorithm. Back in 1998, Google's PageRank was an innovative algorithm that calculated relevance based on counting backlinks instead of parsing the word counts in embedded HTML text like other search engines. This made Google way better than any other available search engine back then (Lycos, Yahoo, AltaVista, etc.), and within weeks, everyone was switching to Google. A successful Google competitor just needs to be way better than what’s currently available. Nobody seems to have the next big idea for a better search engine yet.
- foobarian 4y ago> way better than what’s currently available Hand-curated walled garden sub-web that bans SEO spam with an iron hand.
- ricardo81 4y agowikipedia? Beyond their remit for some queries for sure, but they fit the mold.
- rvz 4y ago> A successful Google competitor just needs to be way better than what’s currently available. Nobody seems to have the next big idea for a better search engine yet. I would speculate that Apple could roll their own search engine using Siri. We'll see what happens in either WWDC or in a few years, but it seems to be quite early for that and certainly have a long way to go.
- vivekraghunatha 4y ago(Founder of Neeva here) Query-independent page and site signals like PageRank (or its site variants) have limited utility in a search ranker. Mostly, they are useful in weeding out bad pages and sites from your index, tie-breaking when you hit shard limits in retrieval and a few other edge cases. The signals that matter the most: 1. Anchor text (and all variants of smearing and distinguishing between high quality and low quality anchors) 2. In aggregate, which pages got clicked on on any given query (and all smearing variants -- using ngrams, embeddings, ...). At Neeva, we use it for retrieval and scoring. 3. Query understanding signals mined from the query-click bi-partite graph and the query-query session refinement graph. 4. Page summarization signals built on top of 1 and 2 and body text. 5. To a lesser extent, query-independent page quality signals Whether you use term-based retrieval or nearest neighbor (embedding) retrieval, a heuristic combination of signals or LambdaMart, whether you calibrate to human eval or clicks, whether your topical relevance function is hand crafted or uses a combination of deep learning and IR signals are all details past that. tldr; there's a lot of craft in a search ranker, and no one silver bullet. Definitely not just PageRank.
- onetokeoverthe 4y ago
- ChrisArchitect 4y agoPrevious discussion from when this was news: https://news.ycombinator.com/item?id=20067712 https://news.ycombinator.com/item?id=20067712
- LeonTheremin 4y agoEric Schmidt: However, our report says that it's really important for us to find a way to maintain two generations of semiconductor leadership ahead of China. Now, the history here is important. In the 1980s, we created a group called SEMATECH. We had a bunch of semiconductor manufacturing in America. Eventually that all moved to East Asia, primarily Singapore, and then South Korea and now Taiwan through TSMC. The most important chips are made in Samsung and TSMC, South Korea, and Taiwan. China has had over 30 years to plan to try to catch up. It's really difficult. Eric Schmidt: We don't want them to catch up. We want to stay ahead. We call for all sorts of techniques to try to make sure that we rebuild a domestic semiconductor and semiconductor manufacturing facility within the United States. This is important, by the way, for our commercial industry as well as for national security for obvious reasons. By the way, chips, I'm not just referring to CPU chips, there's a whole new generation, I'll give you an example, of sensor chips that sense things. It's really important that those be built in America. https://www.hoover.org/research/pacific-century-eric-schmidt-talks-about-great-sino-us-tech-war-and-how-win-it https://www.hoover.org/research/pacific-century-eric-schmidt... What are the chips that "sense things" and that Schmidt wants so much to prevent from being available to China and any other country? Short answer: electromagnetic sensors used to spy on everybody so Google can show them "relevant ads" and profit. You will find them embedded on your CPU, on the nearest cellphone tower's transmitter and on Starlink satellites. Slightly longer answer: since the 1980s, Silicon Valley has used semiconductor radars to collect data about what you think (your inner speech) by means of machine learning with data extract from wireless imaging of your face and body. It has proved very convenient for them, as this enables blackmail, extortion, theft, sabotage and murder like nothing else. They can do this because they design the semiconductor used on your phone, computer, TV, car and for your telecom supplier's network equipment, which makes possible to embed silicon trojans everywhere. Don't underestimate what machine learning can do. e.g. Study shows AI can identify self-reported race from medical images that contain no indications of race detectable by human experts. https://news.mit.edu/2022/artificial-intelligence-predicts-patients-race-from-medical-images-0520 https://news.mit.edu/2022/artificial-intelligence-predicts-p... Also, don't underestimate the number of people Silicon Valley is willing to kill to maintain a monopoly, as you may be the next victim.
- sydthrowaway 4y agoIt's becoming clear to me that building a new crawler and indexer is the next moon landing of our time.