Search Engines: Information Retrieval

The Scale Problem: Why a Search Engine Cannot Just "Search the Internet"

Type "why does ice float on water" into a search box, and a ranked list of relevant pages appears in well under a second, pulled from a collection of pages larger than any library humanity has ever built. The obvious mental model — "the search engine goes out and reads the internet right now to find matches" — is completely wrong, and seeing exactly why it is wrong is the fastest way into how search actually works.

Do the arithmetic. Suppose, just as an illustrative assumption for this calculation, an engine has crawled on the order of 10 billion pages (10¹⁰), and each page has roughly 1,000 words on average. To answer one query by brute-force scanning — opening every page and checking whether it contains the query words — you would need to inspect roughly N × L = 10¹⁰ × 10³ = 10¹³ words. Even a generous 10⁹ word-comparisons per second (a fast, tight loop on a single modern core) gives 10¹³ / 10⁹ = 10⁴ seconds — about 2.8 hours, for a single query, on a single machine. Real engines answer billions of queries a day in a fraction of a second each. Brute-force scanning is off by many orders of magnitude, and no amount of extra hardware closes a gap that large economically.

The resolution is that almost all of the expensive work happens long before you type anything. A background process continuously discovers and downloads pages (crawling), extracts and organizes their words into a data structure built for fast lookup (indexing), and even scores links between pages for importance (covered later in this chapter). Query time then does none of that heavy lifting — it only looks things up in a structure that was already built. This chapter is about that structure, how it is built, how results are ranked once you have it, and how search quality itself is measured.

The Inverted Index: Flipping the Problem

A "forward index" stores, for each document, the list of words it contains — that is exactly how a document is naturally stored, and it is useless for search. If someone asks "which documents contain the word 'chandrayaan'?", a forward index forces you to open every document and scan it, which is precisely the brute-force disaster above.

An inverted index flips the relationship: for each word (called a term), it stores the sorted list of document IDs that contain it (called a postings list). Answering "which documents contain 'chandrayaan'?" is now a single dictionary lookup, not a scan of billions of documents. This one structural inversion is the single most important idea in information retrieval — everything else in this chapter either builds the inverted index or ranks results using it.

Consider three tiny documents:

D1: "isro launched chandrayaan mission to the moon south pole"
D2: "reserve bank of india regulates upi digital payments"
D3: "chandrayaan mission by isro landed near the moon south pole"

Building the index has two stages: first tokenize and normalize each document (next section), then invert. Here is the inversion step in Python, assuming tokenization has already lower-cased and split the text on whitespace:

docs = {
    1: "isro launched chandrayaan mission to the moon south pole",
    2: "reserve bank of india regulates upi digital payments",
    3: "chandrayaan mission by isro landed near the moon south pole",
}

stopwords = {"to", "the", "of", "by", "near"}

def build_inverted_index(docs, stopwords):
    index = {}
    for doc_id, text in docs.items():
        for token in text.lower().split():
            if token in stopwords:
                continue
            index.setdefault(token, set()).add(doc_id)
    return {term: sorted(ids) for term, ids in index.items()}

index = build_inverted_index(docs, stopwords)
print(index["isro"])     # [1, 3]
print(index["upi"])      # [2]
print(index["moon"])     # [1, 3]

Trace it by hand for D1: text.lower().split() gives ["isro","launched","chandrayaan","mission","to","the","moon","south","pole"]. Two tokens, "to" and "the", are in the stopword set and get skipped; the remaining seven tokens each add document ID 1 to their entry in index. Repeat for D2 (drops "of") and D3 (drops "by", "near", "the"). The three printed lines are exactly [1, 3], [2], and [1, 3] — you can verify this by walking through the loop yourself. The diagram below shows the same pipeline end to end, including every term this three-document corpus produces.

Tokenization and Normalization

Before anything gets inverted, raw text must become a clean stream of terms. Four steps matter most for a Grade 10 understanding:

• Tokenization — splitting text into individual words on whitespace and punctuation. "UPI's growth" becomes tokens like "upi" and "growth", with the apostrophe-s handled by the tokenizer's rules.
• Case folding — lowercasing everything, so "ISRO", "Isro", and "isro" all map to the same postings list. Without this, the index would treat identical words as different terms and searches would silently miss matches.
• Stopword removal — dropping extremely common words ("the", "is", "of", "to") that appear in nearly every document and therefore carry almost no power to distinguish one document from another. Removing them shrinks the index and speeds up query processing, since these words would otherwise generate enormous postings lists that every query touches.
• Stemming/lemmatization — reducing words to a common root, so "regulates", "regulated", and "regulation" can all map toward "regul-" or "regulate". This lets a search for "payment" also surface documents containing "payments" or "paying". Real engines use more nuanced algorithms than a Grade-10 chapter needs to derive, but the goal — collapsing surface variation so meaning-equivalent words share a postings list — is the important idea.

Each of these is a small, mechanical transformation, but skipping any one of them means real queries fail to match real documents that are obviously relevant to a human reader. This is also where a search engine can go wrong: overly aggressive stemming merges words that shouldn't be merged (stemming "university" and "universe" toward the same root, for instance, in some algorithms), while too little normalization means exact-string matching fails constantly. Production systems tune this carefully per language.

Boolean Retrieval: Merging Postings Lists

Once you have an inverted index, answering "chandrayaan AND moon" means intersecting two postings lists; "chandrayaan OR upi" means their union; "moon NOT chandrayaan" means a set difference. Because every postings list is stored sorted by document ID (this is a deliberate design choice, not an accident), intersection can be done with a simple merge — the same idea as the merge step of merge sort — in a single linear pass over both lists:

def intersect(p1, p2):
    result = []
    i = j = 0
    while i < len(p1) and j < len(p2):
        if p1[i] == p2[j]:
            result.append(p1[i])
            i += 1
            j += 1
        elif p1[i] < p2[j]:
            i += 1
        else:
            j += 1
    return result

print(intersect([1, 3], [1, 3]))   # postings for "chandrayaan" AND "moon" -> [1, 3]

Trace it: i = j = 0. p1[0] = 1 equals p2[0] = 1, so 1 is appended and both pointers advance to 1. p1[1] = 3 equals p2[1] = 3, so 3 is appended and both pointers advance to 2. Now i = 2 is not less than len(p1) = 2, so the loop stops. The result is [1, 3], matching the comment.

Why does this matter beyond correctness? Complexity. Each pointer only ever moves forward, and each step advances at least one pointer, so the total work is bounded by len(p1) + len(p2) — linear in the combined size of the two postings lists, not in the size of the whole document collection. If "chandrayaan" appears in 40,000 pages and "moon" in 60,000, intersecting them costs at most 100,000 simple comparisons, regardless of whether the collection has ten million or ten billion documents. This is exactly why sorting postings lists by document ID is a design decision worth making at index-build time — it converts every future Boolean query into cheap, linear merges. Real engines add "skip pointers" inside long postings lists to let the merge jump ahead instead of stepping one ID at a time, but the underlying sorted-merge idea is unchanged.

Ranking with TF-IDF

Boolean retrieval answers "does this document match?" but not "how well does it match, and in what order should results appear?" A query like "chandrayaan moon isro" might match thousands of documents; users need the best ones first. This requires a numeric relevance score, and the classic starting point is TF-IDF: term frequency times inverse document frequency.

Term frequency, tf_t,d, is simply how many times term t appears in document d. The intuition is that a document mentioning "chandrayaan" five times is probably more about Chandrayaan than one mentioning it once. Used alone, though, term frequency is a poor ranking signal, because it treats every word as equally informative — repeating a very common word many times would score highly for no good reason. That gap is filled by the second factor.

Inverse document frequency down-weights terms that appear in many documents (and are therefore poor at distinguishing between them) and up-weights terms that appear in few documents (and are therefore highly discriminating). With N total documents and df_t the number of documents containing term t, the standard definition is:

idf(t) = log10( N / df(t) )

A term in every document (df_t = N) gets idf = log10(1) = 0 — it contributes nothing to ranking, which matches the intuition that a word present everywhere cannot help you pick a "best" document. A rare term with small df_t gets a large idf. The final weight combining both signals is:

tf-idf(t, d) = tf(t, d) x idf(t)

Work through a concrete five-document corpus:

D1: isro launched chandrayaan mission moon south pole
D2: reserve bank india regulates upi digital payments
D3: chandrayaan mission isro landed moon south pole
D4: upi transactions grew rapidly india year
D5: nasa studies moon mars

(These are D1–D3 from before, plus D4 and D5, each already stopword-stripped.) N = 5. For the query "chandrayaan moon isro", find each term's document frequency: "chandrayaan" appears in D1 and D3 only, df = 2. "isro" appears in D1 and D3 only, df = 2. "moon" appears in D1, D3, and D5, df = 3 — it is the least discriminating of the three because it shows up in an extra, otherwise-unrelated document about NASA and Mars.

idf(chandrayaan) = log10(5/2) = log10(2.5)   ~ 0.398
idf(isro)         = log10(5/2) = log10(2.5)   ~ 0.398
idf(moon)         = log10(5/3) = log10(1.667) ~ 0.222

Notice "moon" gets a noticeably lower idf than "chandrayaan" or "isro" purely because it is less selective — this is the mechanism, laid bare with real numbers, not an abstract claim. Each document occurs once per query term where present (tf = 1), so its tf-idf weight along a query-term dimension equals that term's idf. Restricting attention to just the three query-term dimensions (chandrayaan, isro, moon) — a valid simplification because a dot product with the query only picks up terms present in the query anyway — the document vectors are:

D1 = (0.398, 0.398, 0.222)   [has all three terms]
D2 = (0,     0,     0    )   [has none]
D3 = (0.398, 0.398, 0.222)   [has all three terms]
D4 = (0,     0,     0    )   [has none]
D5 = (0,     0,     0.222)   [has only "moon"]

The query vector, built the same way (each query term has tf = 1, so its weight is just its idf), is Q = (0.398, 0.398, 0.222). Scoring each document by the dot product Q·D:

D1.Q = 0.398(0.398) + 0.398(0.398) + 0.222(0.222) = 0.366
D3.Q = 0.366  (identical to D1)
D5.Q = 0.222(0.222) = 0.049
D2.Q = D4.Q = 0

The ranking D1 = D3 > D5 > D2 = D4 is exactly right by inspection: D1 and D3 genuinely discuss the Chandrayaan/ISRO Moon mission and tie for first; D5 mentions the Moon only in passing alongside Mars and NASA and correctly scores far lower; D2 and D4, about banking and UPI, correctly score zero. The arithmetic didn't just produce a plausible-looking order — it produced the correct order, and you can see exactly which term contributed how much to each score.

From Dot Product to Cosine Similarity

The dot product above has a flaw: it rewards long documents unfairly. A document that repeats every query term many times, or simply contains a huge number of distinct words, accumulates a larger dot product even if it isn't proportionally more relevant. The fix is to normalize by vector length, turning the score into the cosine of the angle between the query vector and the document vector:

cos(Q, D) = (Q . D) / (|Q| |D|),   where |V| = sqrt(sum of V_i^2)

This works because the dot product of two vectors equals |Q||D|cos(theta) by definition of the angle between vectors (a standard identity from vector algebra); dividing both sides by |Q||D| isolates cos(theta) directly. A cosine of 1 means the vectors point in exactly the same direction — the document's term-weight profile is proportionally identical to the query's, regardless of the document's overall length. A cosine near 0 means they share almost no direction in common.

Compute |Q| for the query above: |Q| = sqrt(0.398² + 0.398² + 0.222²) = sqrt(0.1584 + 0.1584 + 0.0493) = sqrt(0.3661) ≈ 0.605. Restricted to these same three dimensions, D1's vector is numerically identical to Q, so |D1| ≈ 0.605 too (within this reduced view — D1's true vector also has nonzero weight on "launched", "mission", "south", "pole", which would slightly increase its real magnitude and pull its true cosine with Q just under 1; the reduced view is a teaching simplification). cos(Q, D1) ≈ 0.366 / (0.605 × 0.605) ≈ 1.0 — a near-perfect directional match, as expected for a document that is essentially "about" exactly the query's terms.

Now D5: |D5| = sqrt(0² + 0² + 0.222²) = 0.222. cos(Q, D5) = 0.049 / (0.605 × 0.222) ≈ 0.049 / 0.134 ≈ 0.367. Compare this to the raw dot-product picture: D5 scored 0.049, thirteen percent of D1's 0.366. But its cosine is 0.367, roughly a third of D1's near-1.0 cosine — a smaller relative gap. This is the concrete payoff of normalizing: it separates "how much of this document overlaps with the query, proportionally" from "how many words does this document happen to have." A search engine that skipped normalization would systematically favor long pages over short, precisely on-topic ones.

Two Misconceptions, Corrected

Misconception 1: "The search engine reads the live web the instant you press Enter." As the opening arithmetic showed, this is exactly backwards. Crawling and indexing happen continuously, in the background, independent of any particular user's query. What happens at query time is index lookup and arithmetic on numbers computed in advance — cheap and fast precisely because the expensive part was already done. This is also why search results can occasionally be stale: if a page changed five minutes ago and the crawler hasn't revisited it yet, the index still reflects the old version.

Misconception 2: "Repeating your target keyword many times will make your page rank first." This confuses raw term frequency with relevance. It's true that tf is part of TF-IDF, but idf and (as the next section shows) link-based signals exist precisely to counteract naive keyword stuffing — a page that repeats "chandrayaan" five hundred times without any of the surrounding vocabulary a genuine Chandrayaan article would use looks statistically unnatural and, worse for the spammer, still scores zero on every other term a real query might use. Production ranking systems also explicitly detect and penalize this pattern. Relevance is about the whole document's evidence profile matching the query's, not about maximizing one number.

Beyond Keywords: Link Analysis and PageRank

TF-IDF ranks purely on word statistics inside documents. It has no way to distinguish a well-researched, authoritative page from a low-quality page that happens to use the same words. The insight behind PageRank, introduced by Larry Page and Sergey Brin at Stanford in the paper that helped found Google, is to treat the web itself as a directed graph — pages are nodes, hyperlinks are directed edges — and to say a page is important if important pages link to it. This is recursive by design: a page's importance depends on the importance of pages linking to it, which depends on the importance of pages linking to them.

The classic formula, for page P with damping factor d (Page and Brin used 0.85, modeling the idea that a "random surfer" follows a link 85% of the time and jumps to a random page the other 15%, which keeps the process from getting stuck in dead ends or infinite loops around a small cluster of mutually linking pages):

PR(P) = (1 - d)/N + d * sum over pages T that link to P of [ PR(T) / C(T) ]

Here N is the total number of pages, and C(T) is the number of outgoing links on page T — a page splits its "vote" of importance evenly among everywhere it links to. Work through a tiny 3-page graph: page A links to B and to C; page B links only to C; page C links only to A. Out-degrees: C(A) = 2, C(B) = 1, C(C) = 1. With d = 0.85 and N = 3, the constant term (1 - d)/N = 0.15/3 = 0.05. Start every page at PR = 1/3 ≈ 0.333 and iterate:

Iteration 1 (only C links to A; only A links to B; A and B link to C):
PR(A) = 0.05 + 0.85 * (0.333/1)               = 0.333
PR(B) = 0.05 + 0.85 * (0.333/2)               = 0.192
PR(C) = 0.05 + 0.85 * (0.333/2 + 0.333/1)     = 0.475
   check: 0.333 + 0.192 + 0.475 = 1.000

Iteration 2, using iteration 1's values:
PR(A) = 0.05 + 0.85 * (0.475/1)               = 0.454
PR(B) = 0.05 + 0.85 * (0.333/2)               = 0.192
PR(C) = 0.05 + 0.85 * (0.333/2 + 0.192/1)     = 0.355
   check: 0.454 + 0.192 + 0.355 = 1.000

Two things to notice. First, the ranks always sum to 1 (a probability-like distribution over pages) — a useful sanity check on any hand computation. Second, watch A: in iteration 1 it merely holds its starting value, but by iteration 2 it jumps to 0.454, the highest of the three, because C — which became highly ranked in iteration 1 — funnels all of its rank into A (C's only outgoing link). Importance genuinely flows through the graph structure across iterations; it isn't a static count of inbound links. A page with one link from a very important page can outrank a page with many links from unimportant ones. Repeating this update a few dozen more times, the values converge to a fixed point — the graph's principal eigenvector, for readers who go on to study linear algebra at the eigenvalue level, though that equivalence is well beyond what the iterative formula above requires you to know.

Modern search ranking blends signals like this with TF-IDF-style relevance and hundreds of other factors, but the core lesson generalizes far beyond web search: whenever "importance" is defined recursively through a network — citation networks in academic papers, influence in social graphs — the same iterative, eigenvector-flavored idea reappears.

Measuring Quality: Precision, Recall, and F1

Building a ranking function is only useful if you can measure whether it's actually good. Two numbers do most of the work. Suppose a system returns 10 results for a query, and a human judge determines that 7 of those 10 are genuinely relevant (3 are not), while the full document collection actually contains 12 relevant documents in total (so the system missed 5 of them).

Precision = relevant retrieved / total retrieved     = 7/10  = 0.700 (70.0%)
Recall    = relevant retrieved / total relevant exist = 7/12  = 0.583 (58.3%)
F1        = 2 * Precision * Recall / (Precision + Recall)
          = 2 * 0.700 * 0.583 / (0.700 + 0.583)
          = 0.817 / 1.283
          = 0.636 (63.6%)

Precision answers "of what you showed me, how much was actually useful?" — high precision, low recall means the results shown are trustworthy but a lot of relevant material was left out. Recall answers "of everything relevant that exists, how much did you find?" — high recall, low precision means almost nothing relevant was missed, but the results are cluttered with junk. Neither number alone tells the whole story: a system that returns just one, extremely confident result has perfect precision if that result happens to be right, but terrible recall if 11 other relevant documents exist and went unshown. F1, the harmonic mean of the two, penalizes systems that sacrifice one metric heavily to inflate the other — it stays low unless both precision and recall are reasonably high, which is exactly why it (rather than a simple average) is the standard single-number summary in information retrieval.

The Full Pipeline: Crawl, Index, Rank, Serve

Putting every piece together: a crawler starts from a set of seed URLs and follows outgoing hyperlinks breadth-first-ish, discovering new pages, respecting each site's robots.txt file (a standard that tells automated crawlers which parts of a site they may or may not fetch) and revisiting pages periodically to catch updates. Downloaded pages are handed to the indexer, which tokenizes and normalizes text (stripping HTML tags, lower-casing, removing stopwords, stemming) and folds each document into the inverted index, while a separate process computes link-based scores like PageRank from the same crawl's link graph. All of this — crawling, indexing, link analysis — happens continuously and offline, exactly as the opening section argued it must.

When a user actually issues a query, the query processor tokenizes and normalizes the query the same way documents were normalized (so "UPI" the query matches "upi" the indexed term), looks up each query term's postings list, and combines them — Boolean-style intersection for required terms, or scoring every document that contains at least one query term for a ranked result set. The ranker then scores each candidate document, typically blending a TF-IDF-style textual relevance signal with link-based authority signals like PageRank and often dozens of others (freshness, click patterns, mobile-friendliness, and more in real commercial systems), sorts by score, and the top results are what actually get served back to the browser — all within the fraction of a second the opening section's arithmetic said brute-force scanning could never achieve.

Where This Shows Up in Exams

The inverted index and sorted-list-merge idea is a direct application of dictionaries/hash maps and the merge step of merge sort — both explicit CBSE Computer Science topics, and a natural source of coding questions in informatics-olympiad-style programming rounds, where "merge two sorted lists in linear time" is a recurring pattern well beyond just search engines. The TF-IDF and cosine similarity derivation is genuine applied vector algebra — dot products, magnitudes, and the cos(theta) identity are Class 11–12 mathematics topics, and this chapter's worked example is exactly the kind of "compute this vector quantity from given data" question that shows up in applied-math or informatics practicals. PageRank's iterative update is a friendly, concrete on-ramp to eigenvectors and Markov chains, both of which appear in ISC/engineering-entrance-adjacent linear algebra and are worth recognizing early even though full eigenvalue theory is a later topic.

Active Recall

• Q1. A collection has N = 8 documents; the term "monsoon" appears in 4 of them. What is idf("monsoon") using log10(N/df)?
  Answer: idf = log10(8/4) = log10(2) ≈ 0.301.
• Q2. Postings lists for two terms are [2, 5, 9, 14] and [3, 5, 9, 20]. What does the sorted merge (AND) return, and in how many comparisons roughly?
  Answer: Walking both pointers together: 2 vs 3 (advance left), 5 vs 3 (advance right), 5 vs 5 (match, append 5), 9 vs 9 (match, append 9), 14 vs 20 (advance left), left list exhausted. Result: [5, 9], in at most len(list1) + len(list2) = 8 comparisons.
• Q3. Why does a term with idf = 0 contribute nothing to a TF-IDF ranking score, no matter how many times it appears in a document?
  Answer: idf = 0 means log10(N/df) = 0, i.e., df = N — the term appears in every document, so it cannot help distinguish one document from another. Since tf-idf = tf x idf, multiplying by zero zeroes out that term's contribution regardless of tf.
• Q4. In a link graph, page X has one inbound link from a very high-PageRank page, while page Y has ten inbound links from very low-PageRank pages. Which page necessarily ranks higher?
  Answer: Neither necessarily — it depends on the actual PageRank values and out-degrees of the linking pages, not the raw link count. PageRank is a recursive sum of PR(T)/C(T) over inbound linkers T, so one link from an important page with a small out-degree can outweigh many links from unimportant pages, but it is not guaranteed without the numbers.
• Q5. A system retrieves 5 documents, all 5 relevant, but the collection contains 20 relevant documents total. Compute precision, recall, and explain in one line why F1 is low despite perfect precision.
  Answer: Precision = 5/5 = 1.00. Recall = 5/20 = 0.25. F1 = 2(1.00)(0.25)/(1.00+0.25) = 0.5/1.25 = 0.40. F1 is low because it is the harmonic mean, which is dragged down heavily by the smaller of the two numbers — perfect precision cannot compensate for recall that misses 75% of what exists.

Summary

• Brute-force scanning every document per query is computationally impossible at web scale; search engines instead precompute a structure — the inverted index — offline, and only do cheap lookups at query time.
• An inverted index maps each normalized term to a sorted postings list of document IDs; sorting is what makes Boolean AND/OR/NOT computable via linear-time list merges instead of scans.
• Tokenization, case folding, stopword removal, and stemming turn raw text into the normalized terms the index actually stores.
• TF-IDF scores a term's importance in a document by combining how often it appears locally (tf) with how rare it is globally (idf = log10(N/df)); rare, discriminating terms get more weight than common ones.
• Cosine similarity normalizes the TF-IDF dot product by vector length, so long documents don't win purely by being long — it measures directional match, not raw overlap.
• PageRank scores a page's importance recursively through the link graph, using an iterative formula with a damping factor; importance genuinely flows through links across iterations rather than being a static inbound-link count.
• Precision, recall, and F1 quantify search quality in a way accuracy alone cannot, because the two failure modes — showing junk, and missing relevant material — trade off against each other.
• The real pipeline is crawl (discover pages) to index (build the inverted index and compute link scores) to query processing and ranking (combine textual and link signals) to serving results — with everything except the last, fast step happening continuously offline.

Think About It

Think about this: How would you explain search engines: information retrieval to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where search engines: information retrieval is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting search engines: information retrieval to at least 3 other topics you have studied.