Information retrieval · 1998 · Sergey Brin & Lawrence Page

The Anatomy of a Large-Scale Hypertextual Web Search Engine

Use Web link structure as a ranking signal while engineering crawling, indexing, storage, and serving as one measurable large-scale system.

How to read the original

Read PageRank: Bringing Order to the Web and Description of PageRank Calculation.
Read System Features and separate link-based evidence from query matching.
Read Storage Requirements and System Performance as measurements of a complete search pipeline.

A ranking equation needs an index around it

Brin and Page combine link structure with textual and architectural mechanisms for a working Web search engine. The paper is broader than the PageRank recurrence: crawling, parsing, anchor information, storage, indexing, and query processing all contribute to the result. Read the mathematical signal and the system that maintains it as separate claims. A high graph score does not by itself establish relevance to a particular query or truth of a document.

Original reconstruction: a normalized three-page graph

Use pages A, B, and C. A links to B and C, B links to C, and C links to A. There are no dangling pages in this example. Let d=0.8 be the probability of following a link; with probability 0.2, a hypothetical surfer jumps uniformly to one of the three pages. Our normalized ranks sum to one. This is a teaching convention; check the paper’s normalization before comparing raw numbers from different presentations.

Start every page at rank 1/3. At each iteration, distribute a page’s rank equally among its outgoing links, multiply incoming contributions by 0.8, and add 0.2/3 to each destination. The first new rank of A is 0.066667+0.8×(1/3)=0.333333. B receives only half of A’s previous rank, so its rank becomes 0.066667+0.8×(1/6)=0.2. C receives half of A plus all of B, yielding 0.066667+0.8×(1/6+1/3)=0.466667.

The values still sum to one, a useful invariant for this normalized implementation. A second simultaneous update yields approximately A=0.44, B=0.2, C=0.36. Simultaneous means use the entire previous vector, not some newly updated entries mixed with old ones. The rank changes recursively because the importance of a linking page also changes.

Connect graph evidence to a query

Suppose a query asks about volcanic glass. Only A and B contain the required terms, while C is a popular unrelated page. A retrieval system first needs candidates matching the query’s meaning or chosen lexical conditions. Ranking C above every relevant document solely because of its graph score would ignore the task.

Build a tiny inverted index: each term maps to the documents containing it, possibly with positions and additional metadata. Intersect posting lists for a strict two-term query, or use another explicitly defined matching rule. Then compare candidate ranking using text alone and text combined with graph evidence. Anchor text can describe the destination using words absent from the destination’s own body, adding another signal with its own opportunities for error or manipulation.

Test the assumptions instead of admiring the graph

Add a fourth page that links only to one favored destination. Observe whether the ranking changes, then ask how a coordinated set of artificial pages might influence it. A hyperlink may indicate endorsement, criticism, navigation, sponsorship, or a mechanically generated reference. The algorithm computes a property of the recorded graph; interpreting that property as authority requires empirical validation.

Also inspect freshness. A perfect ranking over last year’s crawl cannot reflect a document published yesterday. Failures can originate in discovery, fetch, parsing, indexing, scoring, or serving. Record which stage excluded a known relevant page before adjusting the ranking formula.

A useful replication reports both relevance evidence and system costs: corpus size, crawl policy, index footprint, update lag, latency, and query judgments. The toy calculation is deliberately tiny so every edge contribution can be checked. Scaling changes engineering constraints, while the need to distinguish a mathematical score from the user’s actual information need remains.

Reconstruction exercise

Using the same graph and d=0.8, start with ranks A=0.5, B=0.25, C=0.25. Compute one simultaneous iteration and verify the sum. Then explain what extra rule is needed if C has no outgoing links, and why deleting C’s rank contribution without replacement breaks the probability interpretation.

Worked solution

The uniform jump contribution is 0.2/3, approximately 0.066667. A receives C’s 0.25 through its sole link, so A becomes 0.266667. B receives half of A’s 0.5, also yielding 0.266667. C receives the other half of A plus B’s full 0.25, yielding 0.466667. The results sum to one apart from rounding. If C has no outgoing links, the model must specify how the surfer proceeds from that dangling page. One common convention redistributes its probability uniformly, though other teleportation policies can be defined. Simply dropping the dangling mass makes the next vector sum to less than one and no longer describes the stated stochastic process. Finally, a correctly normalized ranking still needs a query-matching and relevance evaluation policy; conservation of probability is an implementation invariant, not a measure of search usefulness.

Test the limits and transfer the idea

1. Linear algebra and proof · allow 50 minutes

Solve and justify a PageRank fixed point

Use the normalized random-surfer model with damping d = 4/5 and uniform teleportation over three pages. A links to B and C equally, B links to C, and C links to A. There are no dangling pages. Derive and solve the stationary equations exactly, with ranks summing to one.

Let P be the column-stochastic link transition matrix. Show that F(r) = (1-d)u + dPr is a contraction in the L1 norm on probability vectors. Explain what this says about uniqueness and iteration, and what it does not say about topical relevance or the entirety of the paper's search-ranking system.

Get a starting hint

Write a = 1/15 + (4/5)c, b = 1/15 + (2/5)a, and c = 1/15 + (2/5)a + (4/5)b. For the proof, each column of P has nonnegative entries summing to one.

Compare your reasoning with the worked solution

The equations come from incoming links: C contributes all its rank to A, A splits its rank between B and C, and B contributes all its rank to C. Solving them with a+b+c=1 gives a = 61/159, b = 35/159, and c = 63/159. Numerically these are approximately 0.383648, 0.220126, and 0.396226. Substitution verifies all three equations; C ranks slightly above A even though A is C's sole destination.

For any vector x, the triangle inequality gives ||Px||₁ ≤ ΣᵢΣⱼ Pᵢⱼ|xⱼ| = Σⱼ|xⱼ|ΣᵢPᵢⱼ = ||x||₁. Therefore ||F(r)-F(s)||₁ = d||P(r-s)||₁ ≤ d||r-s||₁. Since d < 1, two fixed points would have distance at most d times their own distance, forcing that distance to zero. Iteration contracts the error by at least a factor d per step in this bound.

The normalization and teleport vector are specified for this exercise; check conventions when comparing formulas printed in historical sources. The proof depends on a stochastic transition matrix, so dangling columns need an explicit repair rather than silently violating the premise.

This fixed point measures a link-based process. It does not identify which page answers a particular query, establish factual authority, or reconstruct all ranking signals in the 1998 system. The paper also describes text, anchors, indexing, and other retrieval mechanisms. Solving one component exactly is useful precisely because it makes that component's scope visible.

Check your reasoning

Obtains the exact normalized vector (61,35,63)/159 and verifies it.
Proves the L1 contraction using column sums and d < 1.
States dangling-node and relevance limitations instead of equating PageRank with complete search quality.

2. Index construction · allow 45 minutes

Keep a phrase query separate from a bag of words

Index three documents using zero-based token positions: D1 = red blue red; D2 = blue red; D3 = red green blue. Build postings for red and blue. Return documents for the conjunction red AND blue and for the exact body phrase red blue. Assume D3 has the highest link score, followed by D2, then D1.

Now suppose another page links to D2 using anchor text red blue. Explain how an anchor-aware search policy might retrieve D2 while a body-only phrase policy still rejects it. Specify how your index should preserve field provenance, and show why ranking first cannot repair an incorrect candidate filter.

Get a starting hint

A two-word phrase requires a blue position exactly one greater than a red position in the same document and field. Document membership alone cannot establish adjacency.

Compare your reasoning with the worked solution

The red postings are D1:{0,2}, D2:{1}, D3:{0}. The blue postings are D1:{1}, D2:{0}, D3:{2}. All three documents satisfy the conjunction because both terms occur. For the phrase, D1 has red at 0 and blue at 1, so it qualifies. D2 has the reverse order. D3 has an intervening token. The body-phrase result is therefore only D1, regardless of D3's higher link score.

red = {'D1':{0,2},'D2':{1},'D3':{0}}
blue = {'D1':{1},'D2':{0},'D3':{2}}
conjunction = set(red) & set(blue)
phrase = {d for d in conjunction
          if any(i+1 in blue[d] for i in red[d])}
assert conjunction == {'D1','D2','D3'}
assert phrase == {'D1'}

An anchor-aware policy can associate the anchor phrase with its target D2, as the paper's anchor treatment motivates. That does not make the phrase occur in D2's body. Store field identifiers such as body versus incoming-anchor, and for anchors preserve the source link or anchor unit so positions from unrelated anchors are not accidentally joined. The query contract must say which fields can satisfy it.

If a supposed phrase query retrieves all conjunction matches and merely sorts by link score, it returns D3 first despite its failure to contain the phrase. Ranking adjusts order among candidates; it cannot make a false match true. This exercise models a small positional index and explicit query semantics, not the exact tokenization or present-day ranking behavior of Google.

Check your reasoning

Builds correct positional postings and distinguishes all-three conjunction from D1-only phrase.
Preserves body/anchor provenance and avoids combining unrelated anchor positions.
Shows why link ranking cannot substitute for correct query semantics.

Check your understanding

Why does B receive only half of A’s rank in the example?

A has two outgoing links sharing its contribution.
B has half as many words.
The damping factor is one half.
Only every second iteration updates B.

Explanation

A’s outgoing probability is divided among its two destinations.

A page has the highest PageRank but does not match the query. What follows?

It must be the best answer.
The query should be ignored.
It is necessarily fraudulent.
Graph importance alone does not establish query relevance.

Explanation

Search combines candidate matching and ranking signals; a graph score is not the entire relevance criterion.

Original paper and sources

Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 1998.

Read the original paper →

Read the primary paper: Heriot-Watt University, primary-paper mirror

The Anatomy of a Large-Scale Hypertextual Web Search Engine: Heriot-Watt University, primary-paper mirror