In 1994 one of the first search engines for the Web, the World Wide Web Worm, indexed about 110,000 pages. By late 1997 the leading engines claimed to index between 2 million and 100 million, and the authors expected the Web to pass a billion documents by the year 2000. At that size, matching keywords stops being enough. A query for a common word finds tens of thousands of pages, and most of them are junk.
Sergey Brin and Larry Page, then PhD students at Stanford, described their answer in a 1998 paper: a prototype called Google. It made two big bets. Use the links between pages as a signal of quality, and build the whole system around the physical limits of disks and networks.
Google ranked pages by PageRank, the idea that a page matters if important pages link to it, and by the text of the links that point to it. Behind that sat a pipeline of crawlers, a compressed repository and an inverted index built to avoid slow disk seeks.
PageRank: links as votes
Think of a link from page A to page B as a vote for B. A page with many votes looks worth reading. But not all votes are equal. A link from a respected page counts for more than a link from an unknown one. The paper says a page has a high PageRank if many pages point to it, or if a few highly ranked pages do.
The authors give a simple story to make this concrete: the random surfer. Someone starts on a random page and keeps clicking links, never pressing back. Now and then they get bored and jump to a random page. The probability that the surfer is on a page at any moment is its PageRank.
The boredom is controlled by a damping factor, d, which the paper usually sets to 0.85. With probability d the surfer follows a link, and with probability 1 minus d they jump anywhere. Written as a formula, a page's score is the jump share plus its share of every ranking that flows in through links:
