Every topic so far has started from a collection that already exists. On the web, someone has to build the collection first, by downloading pages one at a time from millions of servers that owe the downloader nothing. A web crawler does this. It starts from a few known pages, fetches them, extracts their links, and follows those links to new pages, indefinitely.
Stated that way, crawling is breadth-first search on a graph, and a toy crawler takes an afternoon to write. The difficulty is everything around the search. The graph is effectively infinite, since programs generate pages on demand. The servers belong to other people, who may not want to be visited often or at all. Much of the web is copied, much of it changes, and much of it cannot be reached by following links. A crawler that runs for months has to cope with all of it without harming the sites it visits.
The course treated crawling briefly, as the stage that feeds the indexing and ranking methods of the earlier topics. This topic follows the same outline, adds the duplicate detection and link analysis that crawling makes possible, and ends with the case most people meet in practice: a small, polite program that watches a few specific pages for changes.
Articles
What a crawler does
- What a web crawler does: the crawl loop, traced on a small web with a spider trap, the parts of a URL, and the features a crawler must provide (robustness and politeness) and should provide (quality, scale, efficiency, distribution, freshness, and extensibility).
- Politeness and robots.txt: rate limits and what they cost a crawler, identifying the crawler, and the Robots Exclusion Protocol as standardized in RFC 9309.
How a crawler is built
- Crawler architecture: the modules of a crawler, URL normalization, the URL frontier with its priority and politeness queues traced step by step and in an interactive demo, and a crawl of this site.
- Near-duplicate detection: fingerprints, shingling, the Jaccard coefficient, estimating it with MinHash, banding, and simhash, each worked by hand on two sentences.
- Freshness and recrawling: how often pages change, deriving expected freshness and age, and why revisiting pages in proportion to their change rate is not optimal, with the optimal rates found by a Lagrange multiplier.
The web beyond the crawl
- The deep web: content behind forms, logins, and scripts, and how crawlers reach some of it, including the informativeness test for surfacing forms.
- Distributed crawling and connectivity servers: dividing the web among machines with consistent hashing, and storing the link graph compactly for fast queries.
- PageRank: ranking pages by the links that point to them, built up from the link matrix through the stochastic and Google matrices to the eigenvector, with the Perron-Frobenius argument, power iteration and its convergence rate, the random surfer as a Markov chain, personalized PageRank, and HITS, all worked through on a five-page example with an interactive demo.
In practice
- Monitoring websites: watching specific pages for changes, politely, with conditional requests and content fingerprints, and choosing how often to check.
Related topics
- Search engine architecture places crawling in the full pipeline.
- Index construction covers the distributed indexing that follows a large crawl.
- Search at scale discusses how freshness of the index depends on the crawl.
- How web search answers a query uses the link analysis and duplicate removal described here.
Course materials
The course had no programming assignment for this topic. The experiments in these articles crawl a local copy of this site, never an outside server, and are in tools/experiments/crawling/ in the site repository.
References
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 19–21. Cambridge University Press.
- Croft, W. B., Metzler, D., and Strohman, T. (2010). Search Engines: Information Retrieval in Practice, chapter 3. Addison-Wesley.
- Olston, C., and Najork, M. (2010). Web crawling. Foundations and Trends in Information Retrieval, 4(3), 175–246.