Information Retrieval and Search Systems

The Problem: Finding a Needle Without Reading the Haystack

Type "newton second law" into any search box and, in under half a second, you get back a ranked list of the most relevant pages out of billions. No human, and no simple computer program that reads every page one by one, could do this in half a second. Something much cleverer than "scan everything and check" has to be happening. That "something" is a field with its own name, its own mathematics, and its own history going back to library science long before the web existed: Information Retrieval, or IR.

This chapter builds, from first principles, the actual machinery that makes searching a large collection of documents fast and the results ranked by relevance rather than dumped in random order. You will construct an index by hand, derive the formula real search engines use to weigh words, prove (not just state) why a particular similarity measure is the right one to rank documents, and compute the algorithm that made Google's founders famous — PageRank — on a small graph, iteration by iteration. Every formula here is one you will derive, not one you will be asked to memorise.

What Counts as "Information Retrieval"?

Formally, an IR system operates on three things:

• A corpus: the collection of documents to search — web pages, NCERT chapters, IRCTC help articles, or your own notes app.
• A query: the user's expression of what they want, usually a handful of words.
• A relevance judgement: for a given query, some documents genuinely answer it and some don't. The system's job is to find the relevant ones and, ideally, put the most relevant ones first.

This is different from a database lookup. A database query like "find the student with roll number 24" has one exact, unambiguous answer. An IR query like "Newton's second law" has no single correct answer — many documents partially match, some are highly relevant, some are marginally relevant, and relevance itself is a matter of degree. IR systems therefore need two abilities that plain database systems don't: a way to decide whether a document matches (retrieval) and a way to decide how well it matches, so results can be ordered (ranking). We build both abilities in this chapter, starting with the simpler one.

Why You Can't Just Scan Everything

Suppose your corpus has N documents, each of average length L words. To check whether a single query word appears in one document, you need to read through that document — roughly O(L) work. To check all N documents for one query word, that's O(N·L) work, repeated for every word in the query, for every search, by every user. For a student's personal notes folder this is fine. For a web-scale engine indexing tens of billions of pages, O(N·L) per query is not just slow — it is physically impossible to do in the time a user is willing to wait. The entire discipline of IR exists because of this one constraint: we must precompute something once, so that each individual query becomes cheap.

The Inverted Index

The precomputed structure that solves this is called an inverted index. The name makes sense once you see the "forward" version first: a forward index maps each document to the list of words it contains — which is exactly how the documents already exist, so it's not useful for searching. An inverted index flips this: it maps each word to the list of documents that contain it. That list is called a postings list.

Take this four-document corpus, drawn from CBSE Class 9–10 Physics and Biology so the words are ones you already know:

D1: Newton laws motion explain force
D2: Newton second law relates force mass acceleration
D3: Photosynthesis converts light energy chemical energy
D4: Force causes acceleration according Newton

To build the inverted index, tokenize each document into individual words, then for every distinct word, record every document ID it appears in. Doing this for the four documents above gives (showing a few terms):

newton       → D1, D2, D4
force        → D1, D2, D4
acceleration → D2, D4
law          → D2
energy       → D3
photosynthesis → D3

The diagram below shows this construction end to end — four raw documents on the left, tokenized and indexed into postings lists on the right.

Now a Boolean query like "newton AND force" is answered not by rescanning any document text, but by merging two postings lists: {D1, D2, D4} ∩ {D1, D2, D4} = {D1, D2, D4}. Since postings lists are stored in sorted order by document ID, this intersection is computed with a single pass down both lists simultaneously (advance whichever pointer is smaller; when they match, output it) — an O(x + y) merge where x and y are the two lists' lengths, completely independent of how many other documents exist in the corpus or how long they are. A query "newton AND NOT law" is a set difference: {D1, D2, D4} − {D2} = {D1, D4}. This is the entire mechanical trick behind fast search: replace "read every document" with "merge short lists," and precompute the lists once instead of per query.

Misconception: "Boolean Retrieval Ranks Results"

A very common misunderstanding is that the Boolean model above already gives you a ranked list, the way a real search engine does. It does not. Boolean retrieval only answers yes/no — a document either satisfies "newton AND force" or it doesn't; there is no notion of one matching document being more relevant than another. Early library catalogue systems worked exactly this way, and it is a real limitation: if a query matches 40,000 documents, Boolean retrieval gives you all 40,000 with no way to tell which ten actually matter. Getting from "matches or doesn't" to "how well does it match, and in what order" requires assigning each document a numeric relevance score — which is exactly the problem the next two sections solve.

Beyond Yes/No: Term Frequency–Inverse Document Frequency

The first useful scoring idea sounds almost too simple: a word that appears more often in a document is probably more central to what that document is about. Define term frequency for a term t in document d as the fraction of d's words that are t:

TF(t, d) = (number of times t occurs in d) / (total number of words in d)

Dividing by document length matters: a 5-word document where a term appears once is proportionally more "about" that term than a 500-word document where it also appears once. Without this normalization, longer documents would win every ranking purely by having more words, not more relevance.

But term frequency alone has a flaw. Words like "the," "is," or in our corpus, common connector words, appear in almost every document and have high TF everywhere — yet they carry almost no information about what makes one document different from another. We need to penalize terms that are common across the whole corpus, and reward terms that are rare and therefore distinguishing. Define document frequency df(t) as the number of documents (out of N total) that contain t at least once, and inverse document frequency as:

IDF(t) = log( N / df(t) )

A term appearing in every document (df = N) gets IDF = log(1) = 0 — it contributes nothing to distinguishing documents, exactly as it should. A term appearing in only one document out of many gets a large IDF, since it is highly discriminating. The base of the logarithm doesn't actually matter for ranking: changing base only rescales every IDF value by the same constant factor (by the change-of-base identity), so the relative order of documents is unchanged. We'll use base 10 throughout. The combined score is:

TF-IDF(t, d) = TF(t, d) × IDF(t)

Let's compute this for real on our four-document corpus (N = 4). Document lengths: D1 has 5 words, D2 has 7, D3 has 6 (with "energy" appearing twice), D4 has 5.

Term "force":   df = 3 (in D1, D2, D4)   IDF = log10(4/3) = 0.1249
Term "acceleration": df = 2 (in D2, D4)  IDF = log10(4/2) = 0.3010
Term "energy":  df = 1 (only D3)         IDF = log10(4/1) = 0.6021

TF-IDF(force, D1) = (1/5) × 0.1249 = 0.0250
TF-IDF(force, D2) = (1/7) × 0.1249 = 0.0178
TF-IDF(acceleration, D4) = (1/5) × 0.3010 = 0.0602
TF-IDF(energy, D3) = (2/6) × 0.6021 = 0.2007

Notice what happened: "energy," appearing in only one document, gets a TF-IDF score nearly ten times higher than "force," which is spread across three documents — even though "force" also gets repeated attention in its documents. This is exactly the intended behaviour: TF-IDF rewards words that are both frequent within a document and rare across the corpus, which together are a good proxy for "this word tells you what this specific document is about."

Documents as Vectors: The Vector Space Model

TF-IDF gives every (term, document) pair a number. Collect all of a document's TF-IDF scores, one per distinct term in the corpus, and you get a point in a high-dimensional space — one dimension per vocabulary word. This is the vector space model: every document is a vector, and a query is a vector too (built the same way from its own words). Ranking documents for a query becomes a geometry problem: which document vectors point in a direction closest to the query vector?

"Closest direction" is measured by the angle between vectors, using the cosine similarity:

cos(q, d) = (q · d) / (|q| × |d|)

where q · d is the dot product (multiply corresponding components and sum) and |v| is a vector's magnitude, √(v₁² + v₂² + ... + vₙ²). Cosine similarity ranges from 0 (perpendicular, no shared direction — completely unrelated) to 1 (pointing in exactly the same direction). Crucially, it does not depend on vector length, only direction — which is the key design choice, as the worked example below proves.

Restrict attention to three terms — newton, force, acceleration — and let a = IDF(newton) = IDF(force) = 0.1249 and b = IDF(acceleration) = 0.3010 (each term occurs exactly once in every document that contains it, so TF is just 1/length in each case). The three document vectors, in (newton, force, acceleration) order, are:

D1 = (1/5)(a, a, 0)     [no "acceleration" in D1]
D2 = (1/7)(a, a, b)
D4 = (1/5)(a, a, b)

Take the query "force acceleration," giving query vector q = (0, 1, 1) (newton not requested). Now compute cosine similarity for D1 algebraically, letting the scalar 1/5 cancel out of both numerator and denominator (cosine ignores overall scale, so we can drop it):

cos(q, D1) = (0·a + 1·a + 1·0) / (√2 × √(a² + a² + 0))
           = a / (√2 × a√2)
           = a / (2a) = 1/2 = 0.500

Notice the actual value of a cancelled out completely — the answer is exactly 0.5 regardless of the IDF weights, because D1 shares only one of the two query dimensions and shares it in exactly the "expected" proportion. Now compare D2 and D4. Their un-scaled direction vectors are both (a, a, b) — D2 is simply (1/7) of that direction and D4 is (1/5) of that same direction, i.e. D2 and D4 are exact positive scalar multiples of each other. Since cosine similarity depends only on direction, this proves — not approximately, but exactly —

cos(q, D2) = cos(q, D4) = (a+b) / (√2 × √(2a² + b²)) ≈ 0.863

D2 has 7 words and D4 has only 5, yet cosine similarity ranks them identically relevant to the query. This is the entire point of dividing by |q||d|: two documents that discuss "force" and "acceleration" in the same proportion, connected as Newton's second law (F = ma) actually connects them, are recognised as equally relevant regardless of how much unrelated padding text surrounds those words. A raw (un-normalised) dot product would have scored D4 lower than D2 purely because D2's numbers happen to look different before normalisation — length would leak into the relevance score, which is exactly the flaw cosine similarity is designed to remove. Final ranking for this query: D2 and D4 tie for most relevant (0.863), D1 is markedly less relevant (0.500), and D3 — sharing no query terms at all — scores a flat 0.

Evaluating a Search System: Precision, Recall, F1

Once a system returns a ranked list, how do we measure whether it's actually good? Suppose, for the query "Newton's laws," the true relevant set (decided by a human judge) is {D1, D2, D4}, but the system actually retrieves {D1, D2, D3} — correctly finding D1 and D2, wrongly including D3, and missing D4. Define:

• True positives (TP): retrieved and actually relevant = {D1, D2} = 2
• False positives (FP): retrieved but not relevant = {D3} = 1
• False negatives (FN): relevant but not retrieved = {D4} = 1

Precision = TP / (TP + FP) = 2/3 ≈ 0.667   (of what we returned, how much was right?)
Recall    = TP / (TP + FN) = 2/3 ≈ 0.667   (of what was right, how much did we return?)
F1 = 2·P·R / (P + R) = 2/3 ≈ 0.667

Precision and recall trade off against each other: a system that returns every document in the corpus gets recall = 1 (it never misses anything relevant) but terrible precision (mostly junk). A system that returns only its single most confident result might get high precision but very low recall. F1, the harmonic mean of the two, penalises systems that sacrifice one for the other — and note the identity used above: when precision exactly equals recall, the harmonic mean of two equal numbers is just that number again, so F1 = P = R, as it does here. This trio — precision, recall, F1 — is not specific to search; it is the standard way to evaluate any system that has to decide, item by item, "relevant or not" — including spam filters and medical-test classifiers, which is why the same three formulas reappear whenever a classifier's output is judged.

Ranking the Web: Link Analysis and PageRank

TF-IDF and cosine similarity score a document using only its own words. But web pages have another rich signal unavailable to a library card catalogue: hyperlinks. A page linked to by many other important pages is probably itself important. This intuition, formalised by Larry Page and Sergey Brin in 1998, is called PageRank, and it is one of the reasons early Google outranked earlier search engines that relied on text matching alone.

Model a "random surfer" who is currently on some page. With probability d (the damping factor, typically 0.85), they click a uniformly random outgoing link on the current page. With probability (1 − d), they get bored and jump to a completely random page in the whole corpus instead (this prevents the surfer getting trapped forever in a small loop of pages that only link to each other). PageRank PR(p) is defined as the long-run fraction of time this random surfer spends on page p. Writing L(q) for the number of outgoing links on page q, and summing over every page q that links to p:

PR(p) = (1 - d)/N + d × Σ [ PR(q) / L(q) ]   for every q that links to p

This is a system of equations where each page's rank depends on other pages' ranks, which themselves depend on it — solved not algebraically but by iteration: start every page at PR = 1/N, repeatedly apply the formula to every page using the previous round's values, and the values converge to a stable fixed point. (For readers continuing into linear algebra: this iteration is exactly the power-iteration method for finding the dominant eigenvector, with eigenvalue 1, of the "Google matrix" built from the link structure — the same numerical technique used throughout applied linear algebra to find a matrix's principal eigenvector without computing eigenvalues directly.)

Work one full iteration by hand on a 4-page graph, with d = 0.85 and N = 4, so the base term (1 − d)/N = 0.15/4 = 0.0375 for every page. Link structure: A links to {B, C}; B links to {C}; C links to {A}; D links to {A}; and no page links to D (D has zero inlinks). Starting every page at PR = 0.25:

PR(A) = 0.0375 + 0.85 × ( PR(C)/1 + PR(D)/1 )
      = 0.0375 + 0.85 × (0.25 + 0.25) = 0.0375 + 0.4250 = 0.4625

PR(B) = 0.0375 + 0.85 × ( PR(A)/2 )
      = 0.0375 + 0.85 × 0.125 = 0.0375 + 0.10625 = 0.14375

PR(C) = 0.0375 + 0.85 × ( PR(A)/2 + PR(B)/1 )
      = 0.0375 + 0.85 × (0.125 + 0.25) = 0.0375 + 0.31875 = 0.35625

PR(D) = 0.0375 + 0.85 × 0        (nobody links to D)
      = 0.0375

Check: 0.4625 + 0.14375 + 0.35625 + 0.0375 = 1.0000  ✓ (ranks always sum to 1)

Page A comes out highest after just one iteration, because two pages — C and D — link to it. Notice, though, that D itself is unimportant (nothing links to D), yet in round one it still hands A a "vote" worth its full starting value of 0.25. This is exactly why a single iteration isn't enough: in the next round, A's score will be recomputed using C and D's updated ranks, so D's now-tiny influence (0.0375) properly shrinks A's contribution from D. Repeating the update for many rounds lets this correction propagate through the whole graph until the ranks stop changing — that stable point is the true PageRank.

Misconception: PageRank is often described as measuring how much traffic or how many clicks a page gets. It measures neither. PageRank is computed purely from the hyperlink graph's structure — who links to whom — and can be calculated without a single real visitor ever loading the page. Actual click and traffic data are separate signals that modern search engines also use, but they are not what PageRank itself computes.

Where Modern Search Goes Further

Real search engines no longer rank purely on TF-IDF or the original PageRank formula; both were 1990s-era foundations that later work extended. Most production text-search systems (including the open-source engines Elasticsearch and Apache Lucene) now use BM25, a refinement of TF-IDF that caps the benefit of repeating a term too many times and tunes the length-normalisation more carefully. Google has publicly confirmed that since 2019 it also uses a transformer-based language model (BERT) to better interpret what a query actually means — for instance distinguishing "flights to Chennai from Delhi" from "flights to Delhi from Chennai," which pure keyword and TF-IDF matching cannot tell apart, since both queries contain exactly the same words. That kind of meaning-based matching, using dense vector embeddings instead of sparse word-count vectors, is the subject of modern semantic-search techniques — the vector space model you derived above is the direct mathematical ancestor of that approach, just with hand-built TF-IDF coordinates replaced by coordinates learned by a neural network.

CBSE and Competitive-Exam Connections

CBSE's Artificial Intelligence curriculum (Data Science strand) explicitly teaches precision, recall, and F1-score as classifier-evaluation metrics using the confusion-matrix framing used above — the identical formulas, just applied to a spam/not-spam or disease/no-disease classifier instead of a document search result. For JEE and BITSAT, information retrieval is not a named topic, but the underlying computation absolutely is: manipulating logarithms (as in IDF, using change-of-base and log(a/b) = log a − log b) and computing vector dot products and magnitudes (as in cosine similarity) are staple problems in their mathematics sections, and this chapter is genuine practice for both. GATE's Computer Science syllabus has no separate "Information Retrieval" section, but its building blocks are examined throughout: hashing and set operations underlie the inverted index and its merge algorithm (Algorithms), and logarithms and probability underlie IDF and the random-surfer model (Engineering Mathematics); GATE's newer Data Science & AI paper also tests precision, recall, and F1 directly as classifier-evaluation tools. If the algorithmic side of this chapter appealed to you — implementing an efficient postings-list merge, or coding the PageRank iteration — that is exactly the kind of programming-and-algorithms problem tested in India's informatics-olympiad pathway run by IARCS, which feeds into the International Olympiad in Informatics.

Check Your Understanding

Work through each question on paper before reading the answers in the next section.

1. A corpus has 1,000 documents. The word "the" appears in all 1,000; the word "photosynthesis" appears in only 4. Without calculating exact numbers, which word will get the higher IDF score, and why?
2. Using the postings lists newton → {D1, D2, D4} and energy → {D3}, what document set does the Boolean query "newton AND energy" return? What does this tell you about queries combining terms that never co-occur?
3. Two documents, X and Y, are related by X = 3Y as vectors (X's coordinates are exactly triple Y's). What is cos(X, Y), and why?
4. A page has zero inbound links from any other page in the corpus. Under the PageRank formula given in this chapter, can its PageRank ever be exactly zero? Why or why not?

Answers

1. "Photosynthesis" gets the higher IDF. IDF = log(N/df), and a smaller document frequency (4 out of 1,000, versus 1,000 out of 1,000) makes N/df larger, so its logarithm is larger. This matches intuition: "the" appears everywhere and distinguishes nothing; "photosynthesis" appears rarely and strongly signals what those 4 documents are about.
2. The intersection of {D1, D2, D4} and {D3} is the empty set — no document contains both words, so nothing is returned, even though each word individually has matches. This shows Boolean AND is strict: partial overlap or "close" matches don't count, which is a real limitation compared to a ranked model where a document with just one of the two terms can still score above zero.
3. cos(X, Y) = 1. Cosine similarity depends only on direction, not magnitude, and scaling a vector by any positive constant (here, 3) does not change the direction it points in. X and Y point in exactly the same direction, so the angle between them is 0° and its cosine is 1.
4. No — its PageRank cannot be zero. Even with zero inbound links, the formula's first term, (1 − d)/N, is added unconditionally to every page regardless of its link structure. This term represents the random surfer's chance of jumping to that page directly, and it guarantees every page in the corpus gets a strictly positive minimum PageRank.

Summary

Search at scale is impossible by brute-force scanning, so IR systems precompute an inverted index mapping each term to a postings list of the documents containing it, turning per-query work into a fast list-merge rather than a full-corpus scan. Boolean queries (AND/OR/NOT) answer match-or-not but cannot rank; ranking requires scoring, and TF-IDF provides that score by rewarding terms frequent in a document but rare across the corpus. Treating documents and queries as vectors of these scores lets cosine similarity rank by directional closeness rather than raw magnitude — a choice you proved, not just asserted, makes document length irrelevant to the score. Precision, recall, and F1 quantify how good a retrieval (or any classification) system actually is, trading off "results returned are correct" against "correct results were found." Finally, PageRank adds a structural signal independent of document text entirely, computed by iterating a random-surfer equation until it converges to a stable ranking of page importance. Together — index, TF-IDF, vector space ranking, evaluation metrics, and link analysis — these five ideas are still, in refined form (BM25, embeddings, learned ranking), the working core of every search engine in use today.

Think About It

Think about this: How would you explain information retrieval and search systems 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.