Web Search Challenges, Size Estimation, Near Duplicates and Crawling

12.1 Web Search Stages and Content Challenges

12.1.1 Three Stage Pipeline of Fetch Index and Query

Why does a web query return in a fraction of a second when the web holds billions of pages? The answer is that almost all the heavy work happens before the user types anything.

Think of a library that prepares for visitors overnight. Librarians fetch new books from publishers (crawl), file index cards by every important word (index), and only then answer a visitor who asks for a book (query). The visitor sees only the last step, but the first two steps decide what can be found at all. The analogy breaks at one point: library books arrive neatly catalogued, while web pages arrive messy, duplicated, and sometimes hostile.

Crawling (automatic fetching of pages through a program that follows links) comes first. A crawler (the program that visits pages, downloads content, and hands pages over for parsing and indexing) starts from a few known pages, follows outgoing links, downloads what it finds, and repeats the loop. Indexing (storing posting lists and page data so queries run fast) works like the index at the back of a book. For each word it stores the list of pages that hold it, called a posting list (the list of document identifiers for one term, for example all pages with the word "crawler"). At query time the engine looks up posting lists instead of re-reading the web, so answers come back in a very short duration. The query stage then retrieves candidates and ranks them for the user need.

The same three stages appear in large commercial engines and in small course projects built with Streamlit, web crawl, pre-processing, and recommendation parts joined into one product. A student team can build a tiny engine with the same shape: a fetch script, a small inverted index, and a ranking page.

12.1.2 Static Content and Dynamic Content

Not every page sits on the web waiting to be picked up. Some pages are printed in advance, and some are cooked only after the visitor orders.

Flight ticket booking pages and railway booking pages are the running examples. The exact list of flights, seats, and prices does not sit as a fixed file. It is built after the user enters source, destination, and date. A crawler that visits the booking site without entering any details sees only an empty form, not the thousands of route pages hidden behind it. The open problem is how a crawler can pick the most relevant pages from such request-driven sites and pass useful pages to the indexer. Which source-destination pairs should it try? How many dates? Each guess costs a fetch, and the combinations are endless.

Picture a chart with number of possible form inputs on the horizontal axis and number of pages the crawler must fetch on the vertical axis. For static sites the curve stays nearly flat: one fetch per page. For dynamic sites the curve shoots up steeply, because each new input value multiplies the pages behind the form. The takeaway is that dynamic sites turn a linear fetch job into a combinatorial one.

Common traps: treating a booking form page as if it were the booking result, and assuming that fetching the form equals indexing the inventory behind it. A form fetch gives almost no searchable content.

One-line recap: static pages can be fetched as stored, while dynamic pages must be triggered by inputs, which is why crawlers struggle to cover them. That gap leads straight to the next challenge, because even the pages a crawler does fetch may not be in one language.

12.1.3 Multilingual Content and Interface Support

Queries do not always come in one language, and neither do pages.

About 90 percent of web users know English, but the rest cannot be ignored. A user may write a query in Japanese or Chinese and still expect a match returned in English. The reverse also happens. A user may write a query in English and expect a French document because the query concerns French philosophy or history. Supporting multilingual pages and a multilingual interface is a major challenge. The engine must match across languages and present results in a form the user can read.

Think of a post office that must deliver letters written in many scripts. Sorting by stamp shape alone fails; clerks need a shared address book that maps each local name to one canonical destination. The shared address book is the multilingual vocabulary or translation layer. The analogy breaks where meaning shifts with culture: one query string can mean different things to different readers, so translation alone does not settle ranking.

12.1.4 Duplicate and Low Quality Content

The web holds many identical and near identical pages. They arise as mirrors, copied content, repeated URLs, and auto-generated pages. Some near duplicates are made on purpose to attract traffic. Some happen by accident when many sites cover the same domain with similar words.

Removing or grouping duplicates improves diversity of results. Two trending news stories were used as running examples, a court related news item and a hunger strike story. A search on either topic returns many documents with almost identical information. Showing all of them as top ranked results would waste result slots. The engine must spot exact copies and near copies and keep only a diverse set.

Imagine a result page as a shelf with ten slots. If eight slots hold the same news wire copy with different headlines, the user gets two useful choices instead of ten. A diversity filter that keeps one copy and drops the rest hands back eight fresh choices. The horizontal axis of the mental picture is rank position from 1 to 10 and the vertical axis is new information per slot; without dedup the curve drops to near zero after position 2, while with dedup it stays high much longer.

12.1.5 Spam Techniques That Distort Ranking

Spam (manipulative methods used to push a chosen document higher while bypassing the ranking algorithm) attacks the signals rankers trust.

Instant loan apps were discussed at length, with fast payout followed by high interest and harsh recovery pressure, and with victim stories appearing in daily news. Video thumbnails and colored click buttons show how attention grabbing design feeds lander page traffic. Each trick maps to one abused signal: stuffing abuses term frequency, hidden text abuses index text, doorway pages abuse query match, and lander pages abuse click behavior.

Modern engines use spam detectors and penalty methods, yet spam remains a challenge even for large engines. Detection is a moving target because each new ranking signal invites a new trick that mimics it.

Picture detection as a filter between indexing and ranking: pages enter with raw scores, the spam detector lowers or zeroes the scores of manipulative pages, and only then does the final order get fixed. The takeaway is that ranking quality needs both filters — dedup for diversity and spam control for honesty.

12.1.6 Student Questions and Answers

12.2 Estimating the Size of a Web Search Engine

12.2.1 What Size Means and Why Index Size Matters

Bigger should mean better, not just more junk pages. That single sentence sets the whole measurement goal: a size number is useful only if it tracks useful coverage.

Think of counting books in a library versus counting pages versus counting shelf meters. Each number is correct on its own terms, yet none of them alone tells which library serves readers better. The size debate for search engines has the same shape: pick the unit that tracks what users actually get.

An early class exchange fixed this idea: crawler page count looks impressive, but index count is the right size signal, because only parsed and stored entries can answer queries.

The class also raised a scoping rule for a page. Storing only the first 4000 bytes of a page is not full indexing. Anchor text alone once described billions of pages in past systems, but anchor text alone is not enough in the present age. The engine must store and process page content itself. A page that is only half stored is only half searchable.

12.2.2 Why Counting Domain Names Fails

One idea is to count domain name server registers, since those registers hold domain names. In words the idea was described as go and count the registers in engine one and engine two and call the larger one bigger. This fails.

Not every domain hosts a website, so the register count overstates the web. One domain can also host many distinct sites — think of university subdomains or hosted blogs — so the same count understates it elsewhere. Both errors strike at once, and there is no fixed correction factor. Counting registers is so not a sound size measure.

A tiny case shows the flaw. Suppose engine one covers 100 domains that each hold 1 site, while engine two covers 10 domains that each hold 50 sites. Register counts say engine one is ten times bigger, while true site counts say engine two is five times bigger. The register proxy points the wrong way, which is why the lecture drops it and moves to sampling.

12.2.3 IP Address Sampling With Fractions

A second idea is to count IP addresses by brute force. Compared with counting domain names it makes a little more sense, because an IP address is closer to a real machine than a name entry is. But counting every address by hand is tiring and not feasible at web scale. Dynamic addresses add more trouble, since the same machine can wear different addresses over time. Even if thought is restricted to static addresses only, full counting does not scale. This is where sampling helps. Take a subset and generalize to the whole, the same idea used in data pre-processing when data is too large to handle in full.

A concrete pass makes the arithmetic visible. Sample $S=1000$ addresses, find $V=80$ valid servers, so $f=80/1000=0.08$. If the universe holds $N_{total}=100$ million addresses, the estimate is $N_{valid}=0.08\times 100,000,000=8,000,000$ valid sites. The sense-check is direct: about 8 in every 100 sampled addresses answered, so about 8 percent of the universe should answer too, as long as the sample was fair.

In theory this gives a defensible magnitude. In practice it is biased because many sites share one IP address through virtual hosting, and one site can span many IP addresses. Shared hosting hides many sites behind one address, while replicated hosting spreads one site over many addresses, so the same fraction idea can both miss and double count. The same fraction idea can be moved from site level to URL level by taking the fraction of sampled URLs that are valid and using it to estimate page counts.

12.2.4 Static Web Scope and Student Questions and Answers

Size talk must fix scope first. Count static pages only, remove duplicates, and then estimate. Dynamic pages, rarely connected servers, and personal devices are left out. Every later sampling method in this lecture inherits that scope.

12.3 Capture Recapture for Relative Index Size

12.3.1 Method Borrowed From Field Counts and Overlap Equation

How do biologists count fish they cannot see? They catch a few, tag them, release them, catch again, and read the share of tagged fish in the second catch. That share reveals the lake total without draining the lake.

Think of two overlapping fishing nets thrown into the same ocean. Each net catches its own share of marked fish, and the overlap between the catches tells how big each net is relative to the other. The fish-to-web mapping is direct: tagged fish are pages indexed by one engine, and recaptured fish are pages found in the other engine too. The analogy breaks where engines are not random nets: real engines favor popular, linked, and fresh pages, so their catches are skewed in similar ways.

Why does equating work? The overlapping pages are one fixed set counted from two sides. From engine one's side they form share $x$ of $S_1$; from engine two's side they form share $y$ of $S_2$. Both products estimate the same overlap count, so they must match. Dividing both sides by $S_2$ and by $x$ gives the handy ratio form:

$$\frac{S_1}{S_2}=\frac{y}{x}$$

so a larger $y$ relative to $x$ means engine one is larger relative to engine two.

12.3.2 Numeric Worked Example With 60 Percent and 40 Percent

A second sense-check uses the ratio form: $S_1/S_2=0.4/0.6=2/3$, so $S_2=1.5\times S_1$, which matches the 1000 to 1500 result. If instead both shares were equal, the engines would be judged equal in size.

12.3.3 Pictorial Grid Example With 4 Cells and 12 Cells

A small picture made the same point without large numbers. Universe A has 4 cells. The overlap A intersect B covers 2 of those 4 cells. The verbal share was 2 out of 4. The grid pictorial overlap half against sixth giving triple size starts here:

$$\frac{|A\cap B|}{|A|}=\frac{2}{4}=\frac{1}{2}$$

where $|A|$ is cell count of universe A and $|A\cap B|$ is shared cell count. Universe B is a 3 by 4 grid with 12 cells. The four cell against twelve cell grids comparison continues: the overlap there is 2 cells. The share is 2 out of 12:

$$\frac{|A\cap B|}{|B|}=\frac{2}{12}=\frac{1}{6}$$

where $|B|$ is cell count of universe B. Equate the two scaled sizes:

$$\frac{1}{2}\times S_A=\frac{1}{6}\times S_B$$

Multiply both sides by 6 to solve:

$$S_B=3\times S_A$$

So B is thrice as large as A. The picture and the fish count share one logic. Overlap shares reveal relative size.

Picture the drawing: a small 2 by 2 square for A with 2 shaded cells, next to a 3 by 4 rectangle for B with the same 2 shaded cells tucked in one corner. The horizontal axis is just cell position and the vertical axis is membership, but the visual punch is the density of shading: half of A is shaded while only a sixth of B is, so B must hold three times the cells to host the same overlap. That density contrast is the whole method in one glance.

12.3.4 Student Questions and Answers

12.4 Query Based Sampling

12.4.1 Random Queries Built From Rare Terms

Sampling still leaves one open choice. How is the random sample drawn? Four procedures were compared. Two use queries and two avoid queries. Random queries are the first query based method.

Term choice matters. Rare terms were used in the class example, vocalist and RSI. The query was a conjunction of word one and word two, in words word one and word two. Rare terms keep result sets small enough to handle: a common word returns millions of hits that cannot be checked by hand, while a rare conjunction returns a short list that can. The procedure does not count every page directly. It uses query driven random results to estimate overlap and then index size.

Think of fishing with a very specific bait that only a few fish bite. The catch is small, so it can be counted fully, and the tagged share inside it still reveals the lake. The analogy breaks where bait choice skews the catch: rare-term bait only samples pages that hold those rare terms, which is exactly the query bias discussed below.

12.4.2 Random Search Drawn From User Logs

Random search is the second query based method. Instead of inventing a query, take a query from the user log. All interaction data is logged, so pick a logged query, run it on engine one and engine two, keep only queries with a small result set, and compute the overlap ratio.

Because the queries are real, they reflect actual human search patterns. A made up conjunction such as vocalist and RSI looks nothing like a normal human need, while logged queries mirror what users type. That match to lived use is the main strength of this method. A query log is a diary of what people truly asked, so sampling from it samples real demand rather than an inventor's guess.

Picture two bars side by side: invented queries cluster around rare dictionary words, while log queries cluster around popular names, shopping, and current events. The horizontal axis is query popularity and the vertical axis is share of samples. The takeaway is that the two methods probe different corners of the index, so their overlap numbers can disagree even on the same engine pair.

12.4.3 Biases and Limits of Query Methods

Both query methods are statistically neat but carry biases.

Random search adds its own limits. Samples correlate with the source log, so they inherit log skew toward popular topics and one language community. Duplicates have high chance because of repeated popular queries asking the same thing many times. Queries must have non zero results in both engines. A zero result query breaks the overlap math because shares cannot be formed from empty sets. Neither method is good or bad in isolation. Each has trade offs, which is why the lecture keeps all four sampling designs on the table before recommending.

Pick invented queries for a controlled experiment and log queries for a user-weighted comparison; report which one was used, because the numbers are not interchangeable.

12.4.4 Student Questions and Answers

12.5 Sampling Without Queries

12.5.1 Random IP Address Sampling Step by Step

Random IP sampling avoids queries and samples the web itself instead of sampling through an engine's ranker. That independence is its whole appeal.

Think of throwing darts at a wall map where each dart picks a street address, then knocking on the door and interviewing one resident. The dart throw (random IP address) does not depend on any guidebook's recommendations, so the sample escapes the guidebook's taste. The analogy breaks where buildings differ wildly: a dart that hits a tower block (a host with thousands of pages) and a dart that hits a hut (a host with one page) get equal weight at the address step, which skews page chances unless corrected.

This path looks clean in theory. It is statistically sound and independent of crawling strategy because pages are picked across hosts rather than through engine ranking. One noted limit is duplicate handling. If the working scope is already static pages with duplicates removed, this limit matters less. The larger limit is hosting reality. Many hosts share one IP through virtual hosting or refuse requests, so some sites are missed, over counted, or under counted. There is also no promise that all pages link back to a root page. A company site may hold employee pages with no direct link from the home page, so host level collection can miss them. Even with these limits, this method was ranked as the preferred choice among the first three studied, because its biases are better understood than query and ranking biases.

12.5.2 Random Walk Sampling on a Link Graph

Random walk sampling uses network science instead of address throws. View the web as a directed node graph where each page is a node and each link is a directed edge.

Picture a board game where the next square depends only on the current one: from each page, roll a die over its outgoing links and step to the winner, sometimes teleporting back to a fresh start to escape loops. After many steps the share of visits to each page settles into a steady pattern called the stationary distribution (the long-run visit shares of the walk, with one number per page). Pages visited more often in that steady pattern are sampled more often. When the directed graph for each engine is available, this method is statistically very clean and can even work on an endless web, because the walk never needs the full address list up front.

Practical limits remain. Seed nodes must be chosen, and a bad seed set traps the early walk in one corner. Approximations may not hold, because the real web is not strongly connected and the walk may never settle. Real world graphs have non uniform distributions, so frequent paths or loops can skew the sample toward hubs that every path crosses.

One-line recap: the random walk trades the address book for the link graph, gaining freedom from queries at the price of graph skew and seed dependence.

12.5.3 Comparison and Choice

Four methods were placed side by side. Random queries are easy to build but carry query and ranking bias. Random search reflects real use but inherits log skew and duplicate risk. Random IP sampling is clean and independent of rankers but struggles with shared IPs and unlinked pages. Random walk sampling is elegant on graphs but needs graph data and care with seeds and skew.

The reason for all four is one shared goal. Estimate index size so engines can be compared as bigger or better on cleaned static coverage. For revision, memorize the methods as two pairs: query based methods differ in where the query comes from, and query-free methods differ in whether they throw address darts or walk the graph.

12.6 Near Duplicate Detection With Shingles and Sketches

12.6.1 Exact Duplicates by Hash Fingerprints

Why does a highly relevant page suddenly look useless? Put it just below its twin and the user gains nothing from the second copy.

Think of fingerprints as luggage tags: two identical suitcases get identical tags, so baggage handlers can spot the pair without opening either case. The tag check is fast because number comparison is easier than word comparison. The analogy breaks for near copies: two suitcases with one swapped shirt get different tags even though they are almost the same, which is why exact fingerprints cannot catch near duplicates.

The hard part is near duplicates. A highly relevant document turns non relevant for a user if it appears just below a near identical copy. The web holds a huge count of such near copies, so near duplicate removal is a central ranking quality step. Dedup protects both size counts (the cleaned static set) and result diversity (ten slots should not hold one story ten times).

12.6.2 Shingles as Word N Grams and Jaccard Similarity

Similarity between two shingle sets uses Jaccard similarity. In words it was described as ratio of common words to the whole universe of words, A intersect B by A union B. The Jaccard similarity of shingle sets as intersection over universe is:

$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$$

where $A$ and $B$ are shingle sets, $|A\cap B|$ is the count of shared shingles, and $|A\cup B|$ is the count of distinct shingles across both documents. A score of 0 means not similar. A score of 1 means similar. A threshold must be fixed for near duplicate calls, for example 80 percent, 70 percent, or 60 percent, based on content type and task. A 100 percent match is not required because the goal is near copies. Reference texts often quote 0.9 as a strict default, while this lecture varies the cut by task; keep the lecture's task-dependent thresholds for exam answers and note 0.9 as the strict textbook variant.

A tiny Jaccard example used two short documents with four shingle slots. Only the first shingle was shared. With universe A plus B plus C style counting, the shared part was A and the universe was A plus B plus C, so the score was intersection over universe for that toy case. In set terms, one shared shingle out of a larger union gives a low score, so the pair is judged dissimilar.

Cosine on term vectors was raised as a first thought, and it can catch syntactic overlap. It struggles when two pages say the same thing in different words with synonyms swapped. Semantic copies that differ in wording are not treated as near duplicates by this syntactic method. That limit matters for plagiarism checks but keeps the web dedup task tractable: the lecture targets word-level near copies, not paraphrase detection.

Picture Jaccard as two overlapping circles. The horizontal axis is shingle identity and the shaded lens in the middle is the intersection; the score is lens area divided by total inked area. The takeaway is that shared material counts only relative to everything either document holds.

12.6.3 Sketches Hashing Permutation and Minimum Values

Shingle vocabularies grow huge even with 2 gram or 4 gram windows, so full set comparison is too heavy. Comparing every pair of billion-page sets is out of reach. The fix is to keep a small summary called a sketch (a cleverly chosen random subset of shingles that approximates the full set). Sampling again solves a web scale problem. Take sketch A and sketch B and apply the Jaccard measure on sketches to call near duplicates.

Plot those numbers on a one dimensional number line. Then apply one random permutation of the whole hash space, which reorders every possible hash value into a random order, and read off where each document's values land. From the permuted values keep the minimum value. That minimum is the sketch summary for one round. Repeat for about 100 or 200 independent permutations. Compare minima round by round across the two documents with the same hash and same randomization. When minima match in 60 or 70 of 200 rounds, the same syntactic material recurs in both documents, and one copy can be discarded.

Why does the minimum carry the full overlap signal? In any fixed random ordering, every shingle in the union is equally likely to stand first. The two minima agree exactly when that first union element lies in the intersection. So the match chance over random permutations equals intersection size over union size, which is the Jaccard score:

$$P(x_1=x_2)=J(S(d_1),S(d_2))$$

where $x_1$ and $x_2$ are the per-document minima and $S(d_1)$, $S(d_2)$ are the shingle sets. The fraction of agreeing rounds over many permutations estimates Jaccard directly.

A numerical spot-check confirms the logic. If two documents share 1 shingle out of a 4 shingle union, Jaccard is 0.25, so about 50 of 200 permutation rounds should agree. If they share 3 out of 4, about 150 of 200 rounds should agree. The lecture's 60 to 70 matches out of 200 signals a Jaccard near 0.3 to 0.35, a moderate overlap rather than a near copy at a 0.7 threshold.

12.6.4 Worked Examples

The three document exercise with fifty percent at a seventy threshold decision extends the same loop. Final vectors were 1, 1 for document one, 0, 0 for document two, and 2, 0 for document three, under the two mod functions. First function finds no common minima between one and two and none between two and three. Second function finds one shared shingle between document two and document three. The Jaccard estimate for document one and two is 0. The estimate for document two and three is 0.5, or 50 percent.

12.6.5 Student Questions and Answers

12.7 Learning to Rank for Web Results

12.7.1 Why Ranking Is More Than Retrieval

For almost any query the web holds a very large number of candidate pages. The real challenge is not just finding matches but ordering them in the right order at scale.

Learning to rank (a machine learning method that improves ranking quality so relevant documents rank above less relevant ones for a given need) learns that ordering from data instead of hand tuning it. A published article was shared as reference for this part, with a PDF link for follow up reading.

Till now ranking used plain cosine similarity, TF-IDF, term proximity, in link and out link counts, and the PageRank algorithm. Those signals work, but ranking at web scale is a hard problem, because no single signal orders every query well. The learned approach collects textual match signals and user behavior on past results and outputs one learned rank function ordered by user need. Jaguar is the proof that one fixed order cannot serve all users; the rank function must condition on signals that separate the car need from the animal need.

Picture relevance as a moving target on a timeline: the horizontal axis is days and the vertical axis is the best page for the query. News queries swing daily, while Jaguar swings by user rather than by day. The takeaway is that ranking must adapt to time and to person, which fixed formulas cannot do alone.

12.7.2 Pipeline Features and Training Grades

Learning to rank is applied after first level retrieval, not from the start. Scoring billions of pages with a learned model on every query would be far too slow.

Feature extraction can use BM25, TF-IDF, title match, anchor text match, link based scores, page features such as freshness, quality, and load speed, and user signals such as clicks, turnaround time, and popularity. Many more features can be added when available. Each feature is one column: BM25 says how well words match, PageRank says how trusted the page is by links, title match says whether the query hits the headline, and clicks say what past users chose.

At training and testing time human judgment is needed because no gold data tells right from wrong on its own. Assessors give graded labels on a 5 to 1 scale from perfect to bad, and logged behavior helps validate. Training items can be single documents, pairs, or ranked lists. Single documents lead to pointwise methods, pairs lead to pairwise methods, and ranked lists lead to listwise methods. This session covers pointwise and pairwise only. Listwise is left out.

Think of training as exam marking: pointwise asks the marker to grade each answer alone, pairwise asks which of two answers is better, and listwise asks for the full class order. The lecture practices the first two marking styles on the laptop query.

12.7.3 Pointwise Ranking Worked Example

The pointwise limit is visible here: the model never compares documents during training, so it can assign close scores to pages users would strictly order. That gap motivates the pairwise upgrade.

12.7.4 Pairwise Ranking Worked Example

Take plain differences of scores. With $s(D)$ for pointwise score, the three pairwise score differences ranking D1 D2 D3 in order are:

$$s(D_1)-s(D_2)$$

$$s(D_1)-s(D_3)$$

$$s(D_2)-s(D_3)$$

A positive difference means the first page should display above the second. The class values gave positive gaps from D1 over D2 and D3, and from D2 over D3, so final order is D1 first, D2 next, D3 last. The reverse subtraction changes sign but not inference. D3 minus D1 is about minus 2.9 when D1 scores 3.9, which still says D1 is higher than D3. Pointwise gives absolute labels while pairwise gives pairwise wins that then order the list. Real systems replace plain subtraction with richer math such as probability estimates, but the comparison thought stays the same.

A compact way to read the result: D1 beats both rivals so it ranks one, D2 beats only D3 so it ranks two, and D3 beats none so it ranks three. That win-count reading turns three pair outcomes into one ordered list without any extra model.

12.7.5 Models Evaluation and Student Questions and Answers

Many rank learners can sit on the same features, including support vector machines and RankNet style models reviewed in the shared paper. Evaluation reuses known measures: precision at K, mean average precision, mean reciprocal rank, normalized discounted cumulative gain, and precision recall curves. The single goal stays fixed. The most relevant document must come to the top.

12.8 Web Crawler Design and Architecture

12.8.1 Must Have Traits Robustness and Politeness

Crawling gathers pages for indexing, so bad crawl choices flow straight into bad search results. The objective is fast and efficient gathering. Two traits are non negotiable.

Think of a guest who visits many houses in one day. A robust guest keeps walking through rain, locked gates, and maze-like gardens without giving up. A polite guest knocks gently, reads the do-not-enter signs, and never rings the same bell ten times in a minute. The web crawler must be both guests at once. The analogy breaks where scale bites: one polite pause per site is nothing, but a million such pauses need careful scheduling across threads.

12.8.2 Good to Have Traits Freshness Distribution and Extensibility

Beyond the two must traits, successful crawlers add more. Distribution across machines brings scalability and efficiency: many workers fetch in parallel instead of one worker fetching alone.

Freshness and extensibility were marked as the two most important should have traits to address in a course crawler design. Assignment work with Request, BeautifulSoup, URL libraries, and Scrapy shows the same needs, since student crawlers must parse varied formats and revisit pages without overloading sites.

Picture freshness as a set of revisit timers, one per page, where fast-changing pages get short timers and stable pages get long ones. The horizontal axis is time since last fetch and the vertical axis is chance the copy is stale; refetching resets each page to zero. The takeaway is that crawl budget should follow change rate, not page count alone.

One-line recap: must-have traits keep crawling possible, while freshness, distribution, and extensibility keep it useful at scale. The next step is seeing where politeness rules live.

12.8.3 Robots Exclusion and URL Frontier Scope

Think of the robots file as the house rules pinned to the front door: guests may enter the living room, must skip the bedroom, and can find the full room list on the notice board (the sitemap). Ignoring the sign is trespass, and the host will lock the door.

The unseen web is the universe of URLs. Inside it sits the frontier, the list of URLs found but not yet crawled. Inside the frontier sits the smaller set already crawled and parsed. Frontier entries come from seed expansion and from newly found links, not from private crawler knowledge. In set terms: crawled pages form a small core, the frontier rings that core with known-but-unvisited URLs, and the unseen web stretches beyond both.

12.8.4 Seeds Frontier Queue and Crawler Threads

A crawling thread, also called the spider worker, takes one URL from the frontier, sends a request to the web server, downloads the page, parses content, and helps create index data. While parsing it finds more URLs and sends those new URLs back to the frontier. One crawler can do this loop, but many threads can work in parallel for much better throughput. That is why the diagram shows multiple threads.

Think of the frontier as an airport departure board with priority lanes: first in first out sets the base order, but freshness, politeness, domain, and policy lanes reorder who boards next, and many gates (threads) board passengers at once. The analogy breaks where politeness bites: two passengers for the same host cannot board together even if both are ready, because back-to-back hits on one server violate implicit politeness.

12.8.5 Process Steps and System Modules

The crawl loop in order is pick a URL, fetch the document, parse text and links, check seen state and robots rules, index unseen content, and return new allowed URLs to the frontier. Duplicate and near duplicate elimination runs before new URLs re enter the frontier, and robots filtering keeps only allowed URLs. That ordering matters: filtering before fetching saves bandwidth, and dedup before re-queueing saves queue space.

Modules map to those steps. The URL frontier manages URLs to fetch. DNS resolution translates human readable links such as encyclopedia or university names into machine readable IP addresses such as 93 dot form, because the fetch stage can only use IP form. The fetching module downloads the page. The parsing module extracts text and links. The duplicate elimination module builds document fingerprints and drops repeats. URL filters apply robots rules. From there text with HTML, XML, or JSON tags passes to the indexer, which builds inverted indexes for query and ranked retrieval use. Python libraries named for implementation were Request, BeautifulSoup, URL handling libraries, and Scrapy, with more met during build work.

Think of the pipeline as an assembly line with quality gates: each station does one job and rejects bad items before they reach the next station. Robots rejects banned URLs early, dedup rejects repeats mid-line, and only clean text reaches the indexer at the end.

12.8.6 Frontier Load Issues and Student Questions and Answers

Two frontier issues need care. The frontier may hold many pages from the same host. A course seeker may have no interest in first degree course links that share the same host, yet those URLs still sit in the frontier because the host served them. There is no easy way to avoid them at discovery time. Thread load also needs care. Every thread should stay busy, but starting 200 workers for a 5 worker job wastes resources. Keep worker count matched to load.

Exam Guidance Summary

Revise each item as a question you can answer from these notes. For duplicate handling, state why one copy must go and how Jaccard plus sketches find near copies. For size estimation, write the overlap equation $x\times S_1=y\times S_2$ from memory and redo the 60 percent against 40 percent numbers that give 1000 to 1500 pages. For sampling, contrast invented rare-term queries such as vocalist and RSI against log queries, and address throws against graph walks, naming one bias for each.

Assignment two is out and is lengthy, built as a Streamlit app joining web search, web crawl, recommendation, and pre-processing into one product, done in teams, with an early start advised because evening sessions on crawler and recommendation directly help the build. Treat the crawler traits (robustness, politeness, freshness, extensibility) and the frontier plus robots rules as build checklist items, not just exam lines. A compensation class was announced for the evening in place of a missed August date, with a request to attend live and to use the follow up material when absent.

Key Industry Applications

Flight and railway booking show dynamic request built pages that challenge crawlers: inventory behind forms cannot be fetched without generating inputs. Japanese, Chinese, English, and French queries show why multilingual matching and interface support matter for real traffic. Trending news on court matters and hunger strike stories show why near duplicate filtering protects result diversity on breaking topics.

Keyword stuffing for TF-IDF gains, hidden text in matching colors, easy money doorway pages to instant loan sites, and video thumbnail lander pages show live spam forms, with spam detectors and penalties still incomplete even at large engines. Fish in a lake counting motivates capture recapture for index size, and the web as ocean extends the same thought to engine comparison.

Vocalist and RSI as rare conjunctive queries and user log queries show query based sampling in practice. Virtual hosting on shared IPs and company sites with unlinked employee pages show why IP sampling misses despite its clean theory. Jaguar as car, animal, and operating system shows why relevance shifts by user and time, which is the business case for learning to rank.

BM25, TF-IDF, PageRank, title and anchor match, freshness, load speed, clicks, and popularity show production rank features, with support vector machines and RankNet style learners as model options. Shopping site robots files with allow, disallow, and sitemap lines show explicit politeness in action. University and encyclopedia seeds plus Request, BeautifulSoup, URL libraries, and Scrapy show practical crawler builds that students can run and extend.