1.3.4 - Search indexing and PageRank

Discovering and revisiting pages

A crawler, also called a spider or bot, fetches pages for a search engine. It discovers addresses through sources such as known pages' hyperlinks and submitted site information. When it reads a page, it can identify links to other pages and add suitable new addresses to its work list. It revisits pages because content and links change.

For an original miniature site, page A links to B and C, B links to C, and C links back to A. Starting at A can discover B and C. Recording already visited addresses avoids endlessly following the A-to-C-to-A cycle. A fourth page D with no links from any discovered page is not reachable by this traversal, even if D links to C: links are directed. D needs another discovery route, such as an already known address or a sitemap.

Fetching is not the same as indexing. A crawler may discover an address but be unable to fetch its content because of access restrictions or errors. A search engine may fetch a page yet decide not to keep it as a separate indexed result, for example where it duplicates another page. Its index is not an instantaneous or complete copy of every Internet page. A recently edited page may still be represented by older stored information until it is revisited and processed.

The crawling stage gathers material; the next stage makes that material efficient to search. Loading every public page anew for every user's query would be slow and impose vast repeated network work.

Building and searching an index

Indexing organises extracted information so matching pages can be retrieved efficiently. A simplified inverted index maps a term to the pages containing it, rather than requiring a scan of every page to find that term. Stored information can include term positions and useful page fields such as titles and headings. Those features can help distinguish a phrase match or a prominent topic from an incidental word.

Consider three original page summaries, treated here as their entire content. Our simplified token rule converts words to lower case and splits on spaces, without removing any words.

The index includes river → M,N, birds → M,P, walks → N, and garden → P. For a query requiring both river and birds, intersecting the two sets produces M. A query allowing either term uses their union and produces M, N and P. The query's rule must be stated; “contains the keywords” is ambiguous about AND versus OR.

If phrase positions are stored, “river birds” can be distinguished from a page where the two words are far apart. Index lookup returns candidates; a ranking stage orders suitable results using relevance and other signals. The search engine searches its stored index, not a fresh live traversal of the whole Web for each query. A result's link leads to the actual page, whose current contents may have changed since indexing.

How PageRank passes importance through links

PageRank is a link-analysis algorithm. Model pages as nodes in a directed graph and hyperlinks as directed edges from the linking page to the linked page. An incoming link contributes importance to its destination, but the contribution depends on the linking page's importance and how many outgoing links share it. A link from an important page with few outgoing links can contribute more than one from a low-ranked page with many outgoing links.

This makes the definition recursive: a page's importance depends on other pages' importance. Repeated updates propagate importance through the graph. PageRank is not simply the count of visitors, the count of outgoing links a page creates, or the number of times a keyword appears. Incoming links matter; creating more outgoing links does not directly add that same amount to the source page's own score.