Summary 20 — Web Crawling, Part II (Scheduling Policies & Crawler Examples)

Source: 13_WebCraw_Part-II.pdf

1. Table of Contents (Topics Covered)

Scheduling as three policies: selection, re-visit, politeness
Selection policy: off-line limits vs. on-line selection (breadth-first, backlink-count, partial PageRank, OPIC)
Focused crawling (predicting relevance, context graphs)
Re-visit policy: freshness & age, modeling page events (Poisson), uniform vs. proportional
Estimating freshness (change rate λ)
Politeness policy: robot identification, robots.txt exclusion protocol, bandwidth/crawl-delay
Combining policies (expected profit q×(1−p))
Examples of real crawlers (Heritrix, Mercator, Nutch, WIRE, etc.)

Gist (2–3 paragraphs)

A crawler balances contradictory objectives — download new pages, refresh old ones, use bandwidth efficiently, avoid bad pages — yet can’t know a page’s value before downloading it. Its behavior decomposes into three policies. The selection policy decides which pages to visit, via off-line limits (max hosts, max depth, max pages/bytes, accepted MIME types) and on-line selection using an importance metric. Studies found partial PageRank and breadth-first orderings work well (breadth-first captures high-PageRank pages early because they have many in-links); OPIC (On-line Page Importance Computation) distributes “cash” among linked pages as a fast PageRank-like guide. Focused crawling filters by topic, exploiting topical locality and using anchor text / context graphs to predict relevance before downloading.

The re-visit policy copes with the Web’s dynamic nature (creations, updates, deletions). Two cost functions drive it: freshness (binary: is the local copy up-to-date?) and age (how outdated it is). Page changes are modeled as a Poisson process with rate λ (estimated from observed changes per visit). Surprisingly, a uniform re-visit policy (visit all pages equally often) beats a proportional one (visit frequently-changing pages more), because constantly re-crawling fast-changing pages wastes effort — the optimal lies closer to uniform. In practice, engines use a few queues with different turnaround times (news refreshed several times daily, popular sites daily/weekly, the rest in a large slow queue).

The politeness policy protects sites: a crawler must identify itself (HTTP user-agent with contact info), obey the robot exclusion protocol (robots.txt for server-wide exclusion; meta-tags noindex,nofollow for page-wise; nocache for cache exclusion), and limit bandwidth (one connection at a time, 10–30 second delays, honoring Crawl-delay). These combine via short-term scheduling (politeness) and long-term scheduling (selection + freshness); a natural combined rule sorts pages by expected profit q×(1−p) (quality × probability the page changed since last fetch). The lecture closes with real crawler examples: global-scale (Heritrix for the Internet Archive, Google’s early crawler, FAST), modular (Mercator, WebFountain, WebSPHINX), and open-source (Nutch, WIRE, Crawlee).

2. Key Terminologies — Meaning & Use Cases

Term	Meaning	Use Case
Selection policy	Which pages to crawl next	Prioritizing quality/coverage
Off-line limits	Preset caps (depth, hosts, bytes, MIME)	Bounding the crawl
On-line selection	Importance computed during crawl	Adaptive prioritization
Breadth-first	Level-by-level traversal	Captures high-PageRank early
Partial PageRank	PageRank on the crawled subgraph	Ordering heuristic
OPIC	Cash-distribution importance estimate	Fast on-line guidance
Focused crawling	Topic-filtered crawling	Vertical/niche search
Context graphs	Infer relevance of un-downloaded pages	Focused crawling
Re-visit policy	When to refresh pages	Maintaining freshness
Freshness / age	Up-to-date? / how outdated?	Re-visit cost functions
Poisson change model	Changes at rate λ	Estimating refresh need
Uniform vs. proportional	Equal vs. change-weighted revisits	Uniform wins for freshness
Politeness policy	Avoid overloading servers	Responsible crawling
robots.txt	Server-wide exclusion file	Robot exclusion protocol
Crawl-delay	Delay between requests a site requests	Bandwidth control
Expected profit q×(1−p)	Quality × change-probability	Combining policies
Heritrix / Mercator / Nutch	Real crawler implementations	Archiving / modular / open-source

3. Process Workflow Diagram

flowchart TD
    A[Crawler] --> B[Selection Policy]
    B --> B1[Off-line limits
depth, hosts, bytes]
    B --> B2[On-line selection
breadth-first / partial PR / OPIC]
    B2 --> C[Focused crawling?
topic + anchor text]
    A --> D[Re-visit Policy]
    D --> D1[Track freshness & age]
    D1 --> D2[Estimate change rate λ
Poisson model]
    D2 --> D3[Uniform-leaning revisits
multi-queue by turnover]
    A --> E[Politeness Policy]
    E --> E1[Identify via user-agent]
    E --> E2[Obey robots.txt / meta-tags]
    E --> E3[Crawl-delay, 1 connection]
    B2 --> F[Combine: sort by expected profit
q × 1−p]
    D3 --> F
    E3 --> F
    F --> G[Download next page]

4. ELI5 — Complex Terms Explained Simply

Selection policy: Deciding which page to grab next when you can’t grab them all — go for the important ones first.
Breadth-first: Explore everything one click away, then everything two clicks away — it happens to find the popular pages quickly.
OPIC (“cash”): Each page hands out its pocket money equally to the pages it links to; pages collecting the most cash get crawled first.
Focused crawling: A robot on a mission — only chase links that look like they lead to the topic you care about.
Freshness vs. age: Freshness asks “is my copy still correct?” (yes/no); age asks “how stale is it?” (how many days old).
Uniform vs. proportional revisits: Surprisingly, checking every page on the same schedule beats obsessively re-checking the pages that change constantly (those just waste your time).
Poisson change model: A way to estimate how often a page changes so you know how often to come back.
Politeness / robots.txt: A “house rules” file websites post telling robots which rooms they may enter and how slowly to knock.
Crawl-delay: The website saying “please wait N seconds between knocks so you don’t wear out my doorbell.”
Expected profit q×(1−p): Crawl the page that gives the biggest payoff — high quality and likely to have changed since you last looked.