CS PAPERS DEEP-READ · PAPER 41
Sergey Brin & Lawrence Page · Stanford · WWW7 · 1998
In 1998, two Stanford PhD students, Sergey Brin and Larry Page, wrote a paper describing a search-engine prototype they'd built — called Google. With one key idea, it turned web search (slow and frustrating at the time) into something that "puts the page you most want to see right at the top, whatever you search for." This paper is, quite literally, the company's birth certificate.
By the mid-1990s the web was exploding, but search engines were still dumb: you typed a word, and they went looking for "which pages contain this word, and contain it a lot." The trouble is that "contains the word" and "is a good page" are two completely different things. A junk page stuffed with keywords could easily outrank a genuinely authoritative one. Search "university" and the top hit might be no university at all. Back then people even relied on hand-curated web directories (like early Yahoo) to find things — but the web grew far faster than people could catalog it.
Brin and Page's insight was beautifully simple: don't just look at what a page says about itself — look at how others treat it. Web pages are wired together by links. A link on page A that points to page B is like A casting a vote for B, saying "this page is worth seeing." The more pages link to you, the more trustworthy you probably are.
But there's a subtler layer: not every vote counts the same. One recommendation from an authoritative page is worth more than a hundred from unknown ones. So "importance" becomes a recursive thing — important pages cast heavier votes, and they in turn were voted up by other important pages. This "who's important depends on who's recommended by whom" score is called PageRank.
Picture someone aimlessly clicking links across the web: land on a page, click one of its links at random, jump to the next, and keep going; occasionally, bored, they type a fresh address into the bar and jump somewhere at random to start over. After countless clicks, the fraction of time they spend on a given page is its PageRank — well-connected important pages get passed through constantly, obscure ones almost never. This "random surfer" picture is exactly what PageRank really is.
One more trick is just as crucial: how others refer to you is often more accurate than how you describe yourself. Countless pages linking to Google label the link text "search engine" — so even if the target page never says those words, the engine knows to surface it for that query. This "text on a link" is called anchor text. It lets a search engine make sense of images and downloadable files (which contain no text of their own), and describe pages it hasn't even crawled yet.
Layering these two signals — "the votes" and "how others refer to you" — on top of the old "does the word appear" approach set result quality apart overnight: ten links on the first page, every one on target. This machinery grew into Google and rewrote how the whole internet finds information. It has a cost too (one honest note): once ranking rides on links, people start manufacturing links and faking votes to game it — an arms race that continues to this day.
Don't just read what a page says about itself — look at who links to it, and who links to those linkers. Treat links as weighted recommendations (PageRank), add "what words others use to refer to it" (anchor text), and you can surface the page most worth seeing out of an exploding web. This is where Google began.
Want the link-voting diagram, the random-surfer formula, and the prototype's architecture? → switch to the deep read
This paper introduces the search-engine prototype Google, built on two ideas that turn the web's hyperlink structure into a quality signal: PageRank — a recursive global importance score for every page based on "who links to you, and how important those pages are" (equivalent to the long-run probability that a "random surfer" lands on the page); and anchor text — describing a page using the text on links that point to it. Layered on top of traditional text matching, these made large-scale web search "on-target on the first page" for the first time, with a full system architecture that scales to the whole web.
The authors are Stanford PhD students Sergey Brin and Lawrence (Larry) Page; the paper appeared at the Seventh International World Wide Web Conference (WWW7) in 1998. Its intellectual root is academic citation analysis (a paper is more important the more — and the more authoritatively — it is cited); a contemporary alternative was Jon Kleinberg's HITS, which splits pages into "authorities" and "hubs." Downstream, this paper grew into Google and made "judge a page's quality by link structure" the industry-wide paradigm for search.
By the late 1990s the number of web pages was growing exponentially, but a person's daily reading capacity was not — most users look only at the top ten results. Search engines of the day ranked mainly by text matching: the more a word appears on a page, and the closer to the title, the higher it ranks. This had two fatal flaws.
First, "contains the word" isn't "is a good page." The authors note that on some engines, searching a well-known company's name wouldn't even surface its own homepage near the top. Second, text matching is trivially manipulated — stuff a page with keywords and you climb, so junk results "wash out any results a user is actually interested in." The other option was hand-curated directories (like early Yahoo): high quality, but hopelessly unable to keep pace with the web's growth. The core tension emerges: the web hides an extraordinarily valuable, almost unused quality signal — the hyperlinks themselves. Someone willingly placing a link to another page is a costly "endorsement."
PageRank's intuition in a line: a page's importance comes from how many pages link to it, and how important those linking pages are themselves. Each link is a vote, but votes are weighted — one vote from an important page is worth far more than one from an unknown. That gives a recursive definition: to know how important A is, you first need to know how important A's linkers are, which depends on their linkers…
How do you compute this chicken-and-egg recursion? The paper uses the random surfer model: imagine someone starting on any page who, with probability d (set to 0.85), clicks a random out-link on the current page and jumps onward; and with probability 1−d (0.15) "gets bored" and jumps to a random page anywhere to start over. Let them walk forever, and the long-run probability of being on a given page is defined as its PageRank. As a formula:
PR(A) = (1−d)/N + d · Σ PR(Tᵢ)/C(Tᵢ)
In plain terms: A's score = a baseline "random-jump" share everyone gets, plus the score passed in by every page Tᵢ that links to A — each Tᵢ splits its own score PR(Tᵢ) evenly across its C(Tᵢ) out-links, and A receives one such share. That 1−d baseline also quietly fixes two headaches: "dead-end" pages with no out-links don't swallow all the score, and a small clique of pages linking only to each other can't hoard score forever.
Mathematically, PageRank is the principal eigenvector of this enormous link matrix; rather than solve an astronomically large system, you just do power iteration — give every page an initial score, update once by the formula, feed the results back in, and repeat until the scores stop changing appreciably. The paper reports that on a graph of about 322 million links, it converges in roughly 52 iterations, and the iteration count grows slowly as the graph doubles — so it scales with the web.
The second key idea is anchor text: the clickable text on a link usually describes not the page it sits on, but the page it points to. The authors attribute that text to the target page. This buys three things: first, the collective way others refer to a page is often more accurate and concise than the page's self-description (countless pages link to Google with "search engine"); second, it lets the engine index objects with no text of their own — images, programs, databases; and third, it can even describe pages the crawler hasn't fetched yet. Relatively uncommon at the time, it hugely improved recall and relevance.
PageRank is a global, query-independent importance score; on its own it would surface pages that are "important but off-topic." So the real ranking is a fusion of signals: for every occurrence of a word, Google records its position, font size, capitalization, and whether it's in the title / anchor / URL (the paper calls these "hit lists," split into "fancy hits" and "plain hits"); it then combines the proximity of terms in multi-word queries, the weights of hit types, and finally multiplies by PageRank to get the ordering. Below is the full data flow, from crawl to answer.
What the paper delivers is a real running system (hosted at google.stanford.edu). At scale: it crawled and indexed about 24 million pages, discovered about 76 million URLs, with a lexicon of about 14 million words and a compressed page repository in the tens of gigabytes. On quality, the authors show a set of representative queries whose results are markedly more relevant than several commercial engines of the day — most strikingly on broad queries where "one word matches countless pages," where PageRank's lift of authoritative pages shows best. The paper also stresses that storage, indexing, and querying were all engineered to scale as the web keeps growing.
This paper set the underlying paradigm of modern search: a page's value is written not only in the page itself, but in the links pointing to it. "Judge quality by link structure" became standard for search engines, spawned Google directly, and reshaped how the entire internet retrieves information. It engineered an academic insight (citation analysis) to web scale and proved the power of the combination "link analysis + text retrieval + scalable architecture." Together with Kleinberg's contemporaneous HITS, it launched "web link analysis" as a research direction that ran for over two decades.
① In one line: the paper introduces the search prototype "Google," whose core is scoring page quality by hyperlink structure — PageRank + anchor text.
② The pain: 1990s search ranked by text matching alone, "contains the word" ≠ "is a good page," and it was trivially gamed by keyword stuffing; hand-curated directories couldn't keep pace.
③ PageRank: treat links as weighted votes, important pages cast heavier votes, defined recursively; equivalent to a "random surfer's" long-run probability of being on the page.
④ Mechanism: PR(A)=(1−d)/N + d·Σ PR(Tᵢ)/C(Tᵢ), d=0.85; the link matrix's principal eigenvector, computed by power iteration, converging in ~52 iterations and scaling.
⑤ Anchor text: describe a page by the text on links pointing to it — often more accurate than self-description, and it indexes images / uncrawled pages.
⑥ Fused ranking: PageRank (global) × text hits (position / font / title / proximity); with a full scalable crawler → repository → index → searcher architecture.
⑦ Results and impact: a ~24-million-page prototype with markedly more relevant results; set the "quality via links" paradigm, spawned Google, reshaped how the internet finds information.
⑧ Limits: query-independent, easily spammed via links, rich-get-richer; only one piece of modern ranking's hundreds of signals; the authors' warning on advertising bias is especially ironic.