IR Models: Boolean, Vector, and Probabilistic Retrieval

2.1 How IR Models Arise: Index Terms, Premises, and Term Weights

2.1.1 Index terms and the premises behind ranking

Traditional information retrieval starts from index terms, which are the cleaned vocabulary units that survive preprocessing. An index term (a word or word-like token kept for indexing, written $K_i$ for the $i$-th vocabulary term) becomes the bridge between a document and a query. Two preprocessing steps produce these terms. Stemming (crude suffix chopping, such as mapping running to run) strips endings with rules. Lemmatization (full morphological analysis that maps each word to its dictionary base form, its lemma) uses vocabulary knowledge to return the true base form. The session names stemming plus a second step sounding like limitization; the reference text confirms the pair is stemming and lemmatization, where the lemmatizer does full morphological analysis to identify the lemma for each word while the stemmer applies language-specific suffix rules with less knowledge.

These index terms label each document, and retrieval then ranks documents against a user query. The ranking always rests on a fundamental premise, and each distinct premise gives rise to a distinct IR model. Three premises shape the three classical models. The first premise says documents can share a common set of index terms, with presence or absence deciding membership. That premise leads to the Boolean model. The second premise says documents can share weighted terms, where each term carries a weight that records how telling it is. That premise leads to the vector space model. The third premise says documents can carry a likelihood of relevance, a probability that the document serves the query. That premise leads to the probabilistic model.

A quick recap anchors the session. Earlier ground covered preprocessing and stemming, retrospective versus prospective retrieval, how IR differs from data retrieval, the logical view of documents, and the IR process flow diagram. Retrieval, unlike browsing, always includes ranking. Within retrieval, the retrospective style, also called ad hoc retrieval, returns a ranked list of relevant documents for a one-off query. The prospective style, also called filtering, keeps responding as data and user queries change over time. A person who searches once for Chandrayaan-3 photos uses retrospective retrieval. A person who sets an alert for every new paper on Chandrayaan-3 uses prospective filtering.

Picture a spice shelf as an everyday analogy. Each jar label is an index term. The Boolean cook asks only whether the jar is on the shelf or not. The vector cook weighs how much of each spice each dish needs. The probabilistic cook asks how likely each dish is to please the guest. The mapping is direct: jar presence maps to the Boolean bit, spoonful size maps to the term weight, and chance of pleasing maps to the relevance probability. The analogy breaks where cooking stops: spices blend in fixed dishes, while index terms interact with queries that change every time.

2.1.2 From noun-only indexing to full-text indexing

The earliest traditional systems indexed only nouns. The reason given was that nouns carry independent meaning, so a noun-only index looked like a compact record of what each document is about. A document about the Moon mission would then be filed under Moon and mission, while verbs such as launched and small words such as on were dropped.

That choice misses real signal, because the rest of the words also carry weight. Verbs separate launch from landing. Adjectives separate crewed from robotic. Names such as Chandrayaan-3 separate one mission from all others. Modern practice moved on to full-text representation, where every surviving word becomes an index term rather than a hand-picked set of important words. Stop-word removal still drops the least telling tokens, and stemming plus lemmatization still merge variants, but no word class is barred at the door.

Classical models in this session (Boolean, vector, probabilistic) sit on top of that full-text idea: they consider all index terms, and then they go one step further by asking whether every term deserves the same say. The Boolean model keeps the full text but gives each term one vote. The vector model keeps the full text and weights each vote. The probabilistic model keeps the full text and asks how each vote shifts the odds of relevance.

2.1.3 Rare terms deserve extra weight

Not all index terms matter equally. Take the sentence "India launched Chandrayaan-3 on the Moon." Its index terms include India, launched, Chandrayaan-3, on, and Moon. The term India appears in thousands of documents, so it says little about which document is wanted. The term Chandrayaan-3 is rare and highly informative, so it should count for more when documents are ranked.

This single idea, nouns first, then all terms, then weighted terms, motivates the whole move from early practice into the three classical models. The session states the weight verbally as the weight associated with the term $K_i$ in the document $D_j$, and the display above records that phrasing in symbols.

Imagine a plot with term rarity on the horizontal axis and weight on the vertical axis. Common words such as on sit near the left with near-zero height. Mid words such as launched rise modestly. Rare names such as Chandrayaan-3 spike high on the right. The curve climbs steeply then flattens on a log scale. The takeaway in one line: rarity buys height, and the log keeps one freak term from buying the whole chart.

2.1.4 Student Questions and Answers

Real-world: paid placement and premium membership boosts on shopping sites sit above the IR match layer instead of replacing it. The same split appears in web search, where sponsored links sit apart from organic ranked results.

2.2 The Boolean Model: Exact Match With Logic Operators

2.2.1 Mathematical Formulation

The Boolean model treats retrieval as logic plus set theory. Documents and queries meet through three operators: AND, OR, and NOT. The session states them as truth tables over presence bits, where 1 means a term is present and 0 means it is absent. AND returns 1 only when both bits are 1:

$$A\wedge B=1\text{ only when }A=1\text{ and }B=1$$

OR returns 0 only when both bits are 0, and 1 in every other case:

$$A\vee B=0\text{ only when }A=0\text{ and }B=0$$

NOT negates its input:

$$\neg A=1\text{ when }A=0,\neg A=0\text{ when }A=1$$

Here $A$ and $B$ are presence bits for two index terms in one document. The symbol $\wedge$ (logical AND) means intersection of document sets. The symbol $\vee$ (logical OR) means union of document sets. The symbol $\neg$ (logical NOT) means the complement within the collection, the disjoint remainder left after removing the term set.

In set language, AND is intersection of document sets, OR is union, and NOT is the complement. A query such as India AND Moon is the set of documents holding both terms. India OR Moon is the set holding either term. India AND NOT Moon is the set holding India minus the set holding Moon. The model views each document as just a set of words, and each query as a Boolean expression of terms.

Think of airport security trays as an analogy. Each tray is a document. Each required item, laptop out and liquids out, is a term. AND means every required item must be present. OR means at least one suffices. NOT means the banned item must be absent. The mapping is exact: tray contents map to presence bits, and the gate decision maps to retrieval. The analogy breaks where travel stops: trays hold a handful of items, while documents hold thousands of terms whose absence is the norm rather than a red flag.

2.2.2 Worked Examples

Now change the query to "India OR Moon." The model widens the net to every document holding either word. A document with only India scores $1\vee 0=1$. A document with only Moon scores $0\vee 1=1$. A document with neither scores $0\vee 0=0$ and is dropped. The result set grows, and the burden of discarding the wrong ones moves to whoever consumes the retrieval output.

A bare two-word query such as "AI healthcare," with no operator at all, needs a decision: read it as one phrase, as an AND, or as an OR. A Boolean engine needs an explicit operator, so the bare form is ambiguous. Lenient engines widen toward union-like behavior and return more, leaving the user to keep or discard results. Imprecise queries return more, and the user does the filtering.

Picture a Venn diagram with India as the left circle and Moon as the right circle. The overlap lens is the AND set. The full inked area of both circles is the OR set. Everything outside Moon is the NOT Moon set. Landmarks are the lens center (both terms, kept by AND), the lone crescents (one term, kept only by OR), and the outside white field (neither term, dropped by both). The takeaway in one line: logic draws hard borders, and nothing ranks the survivors inside each border.

2.2.3 Why exact match hurts

The strengths are real: the model is simple, easy to build, easy to read, and intuitive. A query means exactly what its logic says. That is why it stayed dominant in demanding database setups, including legal search, for more than 30 years. When a lawyer must find every document with a given clause and no near-miss is acceptable, exact sets are the right contract.

But four drawbacks follow from presence-or-absence thinking.

First, synonyms are invisible. A query for "salt" never meets a document that writes only "NaCl" or "sodium chloride," because the index term "salt" never occurs there. The salt synonym gap is structural: matching is literal, so no semantic link joins the variants.

Second, frequency is invisible. A document that explains salt making and repeats the word about 500 times ranks no higher than a recipe document that mentions salt 5 times. Both carry the bit 1. The 500 frequency mentions versus 5 frequency mentions change nothing in the model.

Third, the model overshoots. A query like "salt AND sugar" can pull hundreds of documents with no way to order them. Every document with both bits on is equally retrieved.

Fourth, the model undershoots. A rare query such as "Chandrayaan-3" alone, or "Chandrayaan-3 AND Pragyan" (the rover), may return very few documents. When the bits are off, no partial credit saves the near miss.

2.2.4 Student Questions and Answers

Real-world: legal databases and patent search still run Boolean cores because every returned item must provably satisfy the stated logic.

2.3 The Vector Space Model: Weights, Angles, and Ranking

2.3.1 Mathematical Formulation

The vector space model turns documents and the query into vectors over the same vocabulary, then measures how close each document vector sits to the query vector. Closeness is read as relevance, and sorting by closeness gives the ranking that the Boolean model lacks. The session builds the idea from a toy collection and names cosine similarity as the textbook measure. Its verbal definition is the ratio of dot product to the magnitude product, built here step by step. Let the document vector be $D$ and the query vector be $Q$. Let $n$ be the vocabulary size. Then cosine similarity as dot product over magnitudes reads:

$$\text{sim}(Q,D)=\cos \theta =\frac{Q\cdot D}{\Vert Q\Vert \Vert D\Vert }$$

Here $\theta$ (theta) is the angle between the query and document arrows. $Q\cdot D$ (the dot product) measures alignment. $\Vert Q\Vert$ and $\Vert D\Vert$ (the Euclidean lengths) normalize for size.

The dot product in the numerator is:

$$Q\cdot D=\sum _{i=1}^n{q}_i{d}_i$$

where $q_i$ is the $i$-th entry of the query vector, $d_i$ is the $i$-th entry of the document vector, and $n$ is the vocabulary size. Each magnitude in the denominator is:

$$\Vert Q\Vert =\sqrt{\sum _{i=1}^n{q}_i^2},\Vert D\Vert =\sqrt{\sum _{i=1}^n{d}_i^2}$$

The numerator measures how the two vectors line up, and the denominator normalizes them so that a long document cannot outscore a short one on length alone. Length normalization converts each raw vector into a unit arrow, so only direction counts.

The session states the output range as zero to one. For count-based vectors with no negative entries that range holds: identical vectors give $\cos 0=1$, orthogonal vectors at 90 degrees give $\cos 90=0$, and anything between marks partial similarity such as 0.9 (near duplicate direction), 0.8, 0.6, or 0.3 (weak overlap). A smaller angle means a larger cosine and a more similar document. The range claim needs its qualifier: with general weights that allow negatives, cosine spans minus one to one, but term counts and TF-IDF weights are never negative, so the zero-to-one reading is safe here.

Think of two shopping lists as an analogy. Each list is a vector over the store inventory. The dot product counts how much the two lists agree item by item. Dividing by list lengths stops the family-size list from always beating the single-person list. The mapping is direct: items map to terms, quantities map to weights, and list direction maps to topic. The analogy breaks where pantries stop: shopping lists never hold 50,000 mostly-zero entries, while document vectors do.

2.3.2 Worked Examples

2.3.3 Term weights and TF-IDF

Raw counts already improve on bits: if "india" occurred twice in document one, its entry would read 2 rather than 1, and frequency would shape the score. Term weights push this further. Each term gets an importance weight, rare terms get larger weights than common ones, and the vectors compared by cosine similarity become weighted vectors. The session names TF-IDF as the weighting of choice and notes that most listeners already know it: TF-IDF builds the weighted vector, and cosine similarity reads the angle between weighted vectors.

Newer practice refines the weights with sublinear term frequency and smoothed inverse document frequency. Sublinear term frequency with smoothed inverse document frequency dampens runaway counts and avoids edge cases. The sublinear form replaces the raw count by its log:

$$w_{t,d}^{tf}=1+\log t{f}_{t,d}\text{if }t{f}_{t,d}>0,\text{ else }0$$

The reference text confirms this exact form: twenty occurrences should not carry twenty times the weight of one, so the log compresses the scale. The smoothed inverse document frequency adds one inside the log:

$$id{f}_t^{smooth}=\log \left(1+\frac{N}{d{f}_t}\right)$$

The base form in the reference is $\log (N/d{f}_t)$. The smoothed form keeps the same spirit while avoiding a zero weight when a term appears in every document ($d{f}_t=N$ gives $\log 1=0$ in the base form, but $\log 2$ after smoothing) and softening divisions by small counts. The session named sublinear tf scaling and smooth idf without stating exact forms; the displays above give the standard forms consistent with the reference, with base-10 or natural logs both acceptable since the base does not change the ranking order.

Contextual embeddings from BERT-style models then carry the idea further by weighting and placing terms with context. The session audio garbles the name as bird models; the intended reference is BERT, the transformer encoder whose token vectors shift with surrounding words. Where TF-IDF gives one fixed weight per term per document, BERT gives a context-sensitive placement, so bank near river and bank near money land in different spots.

Other closeness measures are allowed. Euclidean, Manhattan, Mahalanobis-distance, and correlation measures can all compare two vectors; the textbook path simply uses cosine. The guidance given is practical: any proximity measure that fits the data and surfaces similar vectors is acceptable. Distance reads how far apart the endpoints sit, while cosine reads the angle regardless of length.

Picture unit arrows fanning from one origin. The query arrow points northeast. Document one lies almost on top of it with a sliver of a gap, near 35 degrees, cosine near 0.82. Documents two and three splay out at 60 degrees each, cosine 0.50. The horizontal axis is the india direction, the vertical axis is the moon direction, and landmarks are the 0-degree ray (score 1) and the 90-degree ray (score 0). The takeaway in one line: tighter fan means higher score.

2.3.4 Student Questions and Answers

2.3.5 Where the model breaks

Four drawbacks survive. First, terms are treated as mutually independent axes, so "dog bites man" and "man bites dog" share the same tokens (dog, bites, man) and look identical. Word order and who-did-what-to-whom vanish. Second, matching stays literal. A query for "car repair" never meets a document about "automobile servicing," even for a shop ten feet away, because the tokens differ and no semantic link joins them. Third, representation turns poor at scale. Real documents hold hundreds or thousands of words, collections hold lakhs of documents, and the matrix fills with zeros. The zeros are non-informative cells that still get stored, so the signal sits buried in a vast sparse grid. Fourth, TF-IDF weights are intuitive counts rather than quantities derived from a strict theoretical model. These gaps motivate probabilistic models, and beyond them semantic, neural, bigram and trigram, relationship-based, and graph approaches that model meaning, context, and word relationships.

Real-world: retrieval-augmented generation and knowledge agents over office document stores reuse this vector machinery as their retrieval core. Web search, shop search, and help-desk search all rank weighted vectors before any language model writes a word.

2.4 The Probabilistic Model: Ranking by Likelihood of Relevance

2.4.1 The relevance-feedback loop

The probabilistic model, also called binary independence retrieval (BIR), asks a different question: what is the probability that this document is relevant to this query. Its symbol is $P(\text{relevant}\mid D,Q)$, the probability of relevance given document $D$ and query $Q$, with a matching $P(\text{non-relevant}\mid D,Q)$ for the other side. Documents are then ranked by their likelihood of being relevant, which lines up directly with what the user wants.

Think of a detective updating a hunch as clues arrive. Each relevance mark is a clue. The prior guess about a document shifts with every yes or no from the user. The mapping is direct: hunches map to probabilities, clues map to feedback marks, and the case board maps to the re-ranked list. The analogy breaks where cases stop: detectives weigh dependent clues together, while binary independence treats terms as if they arrive alone.

The model does not stand alone. It is built on top of a Boolean or vector run. The procedure has numbered steps: first, retrieve an initial document set with the base model; second, have the user mark each returned document as relevant or non-relevant; third, feed those marks back so the system updates its picture of relevance; fourth, re-rank and return the improved list. Each round of marks sharpens the next ranking. Feedback here means the relevance feedback loop that turns user judgments into new term odds, and re-rank means sorting again by the updated likelihood.

Picture odds bars for three documents. Round one shows short, tied bars from the base run. The user marks one relevant and one non-relevant. Round two stretches the bar for terms from the relevant document and shrinks the bar for terms tied to the rejected one. The horizontal axis is estimated relevance probability, landmarks are the marked relevant and non-relevant anchors, and the takeaway in one line is that each mark bends the next ranking toward the user's yes pile.

2.4.2 Strengths and weaknesses

Ranking by likelihood is the main strength. Scores now mean something the user cares about, namely the chance of relevance, and the feedback loop lets the system learn from direct judgments instead of guessing. The reference names this the Binary Independence Model, where binary means documents and queries are incidence vectors of presence bits and independence means terms are modeled as occurring on their own. That sparseness keeps estimation practical.

The weaknesses mirror the design. The first round depends on the base model, so a weak Boolean or vector start caps everything above it. Relevance marks are binary, which squeezes graded usefulness into yes-or-no boxes: a document that is partly helpful must still be filed as fully in or fully out. And learning from the non-relevant set adds only marginally useful signal, since knowing what is wrong helps less than knowing what is right. In short, the model improves relevance but inherits the limits of whatever sits underneath.

2.4.3 Method family and road map

Several known methods belong to this family. The binary independence model is the base form. BM25, short for Best Matching 25, is the best-known probabilistic ranker named in the session. BM25 keeps the probabilistic outlook but adds term counts, document-length handling, and saturation so that the twentieth occurrence adds less than the first. Language models with maximum-likelihood estimation and belief (Bayesian network) models extend the same probabilistic outlook: language models score by the chance the document would generate the query, while Bayesian networks propagate beliefs across linked terms and documents.

Think of these as one shelf in a longer journey: the course starts with the Boolean model, moves to the vector model, then the probabilistic model, and later reaches web retrieval, graph-based retrieval, neural retrieval, and multimodal retrieval. The current and next sessions stay with the Boolean model, which gets a full dedicated treatment. The road map matters because each later shelf keeps the earlier machinery: neural rankers still filter with inverted lists, and web engines still seed probabilistic scores from vector runs.

2.4.4 Student Questions and Answers

Real-world: spam filters, news recommenders, and search engines all run this loop in production: seed with a fast ranker, collect clicks or marks as soft relevance votes, and re-rank by updated likelihood.

2.5 The Term-Document Incidence Matrix and Boolean Evaluation

2.5.1 Why manual search and grep do not scale

Pose a concrete task: find every Shakespeare play containing "Brutus" and "Caesar" but not "Calpurnia." By hand, the method is to open each play, check for the two wanted words, and confirm the third is absent. With Unix tools the same idea becomes grep-style queries such as "list files matching Brutus," combined with matches for Caesar and non-matches for Calpurnia. Both paths work on a handful of files. Neither scales to billions of documents, because every query would re-scan the whole collection. The fix is to prepare the data once, in advance, and then answer each query from that prepared structure. That preparation is indexing, and its simplest form is the term-document incidence matrix (also just called the incidence matrix).

An incidence matrix (a table with a 1 where a term occurs in a document and 0 elsewhere) pays an upfront build cost once so that every later query becomes cheap bit work. Grep scans text each time. The matrix scans bits each time, over a far smaller structure.

2.5.2 Mathematical Formulation

The incidence matrix is the same document-term idea seen through Boolean eyes. Terms run down the rows, documents run across the columns (six Shakespeare plays in the worked session), and each cell holds 1 when the row term occurs in the column document and 0 otherwise. Counts, positions, and weights are all ignored. The six columns in order are Antony and Cleopatra, Julius Caesar, The Tempest, Hamlet, Othello, and Macbeth. Each term is then a binary vector across documents. Reconciled against the reference table, the three term vectors are:

$$V_{\text{brutus}}=[1,1,0,1,0,0]$$

$$V_{\text{caesar}}=[1,1,0,1,1,1]$$

$$V_{\text{calpurnia}}=[0,1,0,0,0,0]$$

The dictated digits in the session run longer than six entries and mix two examples, so the six-wide forms above follow the reference figure: Brutus appears in Antony and Cleopatra, Julius Caesar, and Hamlet; Caesar appears in those three plus Othello and Macbeth; Calpurnia appears only in Julius Caesar. NOT flips every bit of the Calpurnia vector:

$$\neg V_{\text{calpurnia}}=[1,0,1,1,1,1]$$

AND takes the bitwise minimum across the three vectors:

$$V_{\text{answer}}=V_{\text{brutus}}\wedge V_{\text{caesar}}\wedge \neg V_{\text{calpurnia}}=[1,0,0,1,0,0]$$

In compact bit-string form this is the textbook identity $110100\wedge 110111\wedge 101111=100100$. The verbal rule used throughout is "AND means keep a 1 only where every input has 1; NOT turns each 1 to 0 and each 0 to 1." Reading the 1-entries of the answer vector gives the matching documents.

2.5.3 Worked Examples

Compared with hand search and grep, the matrix version is fast and routine. Once built, each query is just bit operations over short vectors rather than a fresh scan of a million words of Shakespeare text. The same pattern restates as "NOT Calpurnia, then AND the three together," yielding those two plays.

Picture the matrix as a grid with terms as rows and plays as columns. Ones cluster in the Brutus and Caesar rows; the Calpurnia row is almost all white with a single dark cell under Julius Caesar. The answer row lights only under columns one and four. The horizontal axis is the play order, the vertical axis is the term order, landmarks are the lone Calpurnia cell that kills column two and the empty Tempest column, and the takeaway in one line is that zeros dominate and answers are the rare columns where every required light stays on.

2.5.4 Limits of the matrix view

Two limits already bite with only six plays. First, zeros outnumber ones, so most stored cells carry no information; at web scale that sparsity becomes the dominant fact about the structure. Shakespeare uses about 32,000 distinct terms, so a full matrix would hold roughly 32,000 times 37 cells with ones scattered thinly. Second, answers stop at document level. The matrix says Hamlet matches, but not which act or scene holds the matching lines. For instance, a result such as "Antony and Cleopatra, Act 3, Scene 2" is beyond what was asked for and beyond what the structure records. Newer retrieval layers built above this one can supply passage-level answers.

2.5.5 Student Questions and Answers

2.6 The Inverted Index: From Words to Documents

2.6.1 Flipping the mapping

The incidence matrix maps documents to words and pays for it in stored zeros. The inverted index flips the direction: it maps each word to the documents holding it, storing only what is present. The session reaches for a textbook analogy: the textbook index entry science report with pages 12, 15, 45 points from a word to its locations, and the analogy holds because an inverted index does the same for a collection, mapping each term to document locations rather than mapping each document to terms.

For the word Brutus the index stores only the identifiers of documents containing Brutus. The same goes for Caesar and Calpurnia. Nothing is stored for documents a word never touches, so the sparse grid collapses into short lists. The repository of 174 documents named in the session belongs to the larger collection figure where Brutus postings run to identifiers 173 and 174; the six-play matrix is a separate small toy over six columns. The two numbers live in different examples: six plays for the bit-matrix drill, 174 documents for the postings illustration.

Think of a library card catalog as an analogy. Each card names one book title and lists the shelves holding it, instead of listing every shelf for every book with mostly-empty rows. The mapping is direct: cards map to dictionary terms, shelf numbers map to postings, and pulling a card maps to a dictionary lookup. The analogy breaks where cards stop: catalog cards are read by people, while postings are walked by merge code that demands sorted order.

2.6.2 Building one: dictionary, postings, and frequencies

Vocabulary terms on the left are the dictionary; each term's document list on the right is its postings list, held in a plain manageable structure such as a linked list or array. A posting (one document identifier inside a term list, optionally with frequency or position data) is the unit entry. A document frequency (the count of documents holding a term, written $df$) is stored beside each term and later doubles as the list length and the ranking statistic.

Construction follows numbered steps: first, collect the documents to index; second, tokenize the text into pieces; third, normalize each token (lowercasing, stemming, lemmatization, stop-word removal); fourth, emit term-plus-document-identifier pairs; fifth, drop duplicates such as a doubled "I" or a doubled "killed"; sixth, sort the postings of each term by document identifier; seventh, record each term's document frequency alongside.

The session stresses that the demo exists only to build intuition for indexing, sorting, and frequency counting; there is nothing else to memorize in it. Real-world: web engines hold billions of such postings, which is the physical reason ordinary queries answer in milliseconds. The dictionary commonly stays in memory while postings live on disk, so both sizes matter and later chapters compress each.

Picture the build as three columns. The left column is the raw pair stream in document order. The middle column is the same pairs sorted alphabetically by term. The right column splits into dictionary terms with pointers plus postings lists. Landmarks are the doubled pairs that merge, the sorted runs that group, and the frequency counts beside each list. The takeaway in one line: sort plus group turns a jumble of pairs into a query-ready map.

2.6.3 Why sort the postings

Sorting by document identifier looks like bookkeeping, yet the session plants it as a pointed question: why should order matter when the same identifiers are stored either way. A participant suggests faster navigation and search, which is confirmed and then proved in the next section: the merge procedure that intersects postings only works in one pass because both lists arrive sorted. Keep that answer attached to this section: sort once at build time so that every later AND can walk forward without ever stepping back.

Without sorting, intersecting two lists of lengths $M$ and $N$ would need up to $M\times N$ checks in the worst case. With sorting, the merge walks both lists once. The dictionary also stores document frequency, which later lets the engine pick the smallest list first before touching disk. That pairing, sort at build plus frequency at query time, is the whole efficiency story in one line.

2.7 The Merge Algorithm: Answering AND With One Forward Pass

2.7.1 Mathematical Formulation

Boolean AND over postings is set intersection, OR is set union, and NOT is the complement within the collection. The session states this three-way mapping directly ("AND implies intersection, OR implies union") and then turns AND into a procedure called the merge algorithm. A merge (a joint walk over sorted lists with interleaved pointer advances) answers AND by moving fingers forward through postings.

Steps. Given the two sorted inputs:

1. Start with an empty answer list.
2. While neither list is exhausted, compare the two current document identifiers.
3. If they are equal, append the identifier to the answer and advance both pointers.
4. Otherwise advance only the pointer on the smaller identifier.
5. Stop when either list runs out, since no further match is possible.

Because each step moves at least one pointer forward and never moves any pointer back, the merge forward pass never steps back and pointers stay sorted throughout. The total work is:

$$T(M,N)=O(M+N)$$

where $M$ is the length of the first postings list and $N$ is the length of the second. The verbal form given is "the complexity is simply order of M plus N, where M and N are the lengths of the lists." The merge complexity linear in postings lengths holds because every comparison consumes at least one posting forever.

Sorted order is the load-bearing assumption: without it, no pointer could safely skip ahead, and every combination would need checking. Using a numeric sort by document identifier is the standard way to supply that single global order. The intersection operation is asymmetric in production: the intermediate result stays in memory while the next list streams from disk, and the intermediate list stays no longer than the other side.

Picture two combs sliding past each other. The upper comb carries $P_1$, the lower carries $P_2$. At each tick the smaller tooth jumps forward; matching teeth click and drop a copy into the answer tray. The horizontal axis is document identifier order, landmarks are equal-tooth clicks versus smaller-tooth jumps, and the takeaway in one line is that forward-only motion guarantees each tooth is touched once at most.

Complexity and cost. Time grows with the sum of list lengths, not the product, so doubling both lists roughly doubles work rather than quadrupling it. Space is the answer list plus two pointers. When to use and alternatives: use the linear walk as the default for AND; when one list dwarfs the other, binary-search each short item in the long list or hash the long list for constant-time membership tests, at the cost of extra structures that compress poorly.

2.7.2 Worked Examples

Third, plain logical-expression queries. "AI AND healthcare" keeps only documents holding both terms (intersection). "AI OR healthcare" keeps documents holding either (union). The model never grades partial relevance: a document matches or it does not.

2.7.3 Student Questions and Answers

2.8 Query Optimization and Why Boolean Refuses to Retire

2.8.1 Smallest set first

Posting lengths decide the bill. In the running example the Brutus list holds about seven identifiers, the Caesar list about eight, and the Calpurnia list two. The session states the counts once as six, eight, two and once as seven, eight, two; the relative order is stable with Calpurnia shortest, and the optimization lesson is unchanged either way. (The full-collection figure elsewhere lists eight Brutus postings and four Calpurnia postings; the lecture's running counts are its own smaller illustration of the same principle.) An AND between Brutus and Caesar would grind through roughly a dozen comparisons, while starting with Calpurnia needs only about two probes: check each of its two identifiers against the longer list.

Concretely, intersecting Calpurnia with Brutus first yields a single survivor, document 16; the remaining AND against the Caesar list is then one membership test, is 16 present, with early exit the moment the short side is exhausted. The smallest set Calpurnia Brutus survivor optimization leaves that single survivor for one membership test. Because postings are sorted, a match at 16 also proves nothing later in the other list can match the consumed prefix, so the tail (thousands of identifiers in real lists) is never touched. The rule is: for AND, run the smallest list first and stop as soon as any side runs dry. The reference states the same heuristic as sorting terms by increasing frequency and seeding the in-memory result with the least frequent term's list.

OR queries need the mirror image. A union only grows, so estimate each OR's result size from document frequencies first, run the smaller union first, and let the later AND meet the compact set. The session sketches winds: if "wind" occurs in 100 documents and "fire" in 200, their union holds at most 300; if "thunder" occurs in 50 and "lightning" in 30, their union holds at most 80. Process the 80-side first, then combine with the 300-side, and the comparison count stays low. The stated maximum is a worst case, not a promise: overlaps shrink real unions below the sum, so the sum is a conservative size estimate.

Picture three bars for list lengths: Calpurnia shortest at two, Brutus mid at seven, Caesar tallest at eight. Intersecting the two tall bars first builds a wide intermediate slab. Starting from the short bar keeps every intermediate slab no wider than two. The horizontal axis is processing order, landmarks are the survivor document 16 and the early-exit point, and the takeaway in one line is that small-first bounds every later step.

2.8.2 Skipping ahead with skip pointers

A second speedup jumps over hopeless stretches. Suppose $P_1=[1,2,5,8,12]$ and $P_2=[3,5,7,8,\dots ]$ with a skip length of 2. These lists reconstruct the dictated fragments as a clean illustration; the pointer logic is what matters, not the exact tail digits. Instead of stepping one by one, compare 1 with 5, find no match, and skip two ahead; compare 5 with 5, record the match, and skip the block between, since sorted order proves no match hides inside it. Later, 8 against 7 mismatches and the window jumps again.

Trace in words. Both pointers start at their heads. When the lagging side owns a skip whose landing identifier is still no larger than the other side's current identifier, follow the skip; otherwise step once. Skips exist only on the original stored lists, never on intermediate results, and they help AND queries rather than OR queries. The idea matches the merge theme: sorted identifiers let the procedure prove that whole stretches can go unchecked.

2.8.3 Industry Applications

Real-world: Westlaw, the large legal search system, still runs Boolean-style retrieval after decades, because legal work leaves no room for maybe-answers. The retrieved set must be exactly the matching set, trustworthy at face value. The Westlaw legal exact sentence tailored retrieval earns trust in that setting: every hit provably satisfies the stated operators.

Its queries show how far exact matching stretches. A query may combine a wildcard such as "limit!" (matching limit, limits, limitation, where SQL-style systems would write a star), a proximity bound such as "/3" (within three words), a sentence bound such as "/S" (within the same sentence), and offsets such as "/2" (within two words). One worked query chains "limit!" within three words of "statute action," in the same sentence as "federal," within two words of "tort," within three words of "claim," and pulls the sentence "The statute of limitations governing this action under the Federal Tort Claims Act applies." The Westlaw wildcard proximity sentence statute federal retrieval drill is the canonical specimen: read each operator into plain words, then check the sentence word by word. A second query asks for "trade secret" in a sentence with "disclose" plus "prevent" plus "employ," retrieving the sentence about preventing disclosure of trade secrets by employees. This is sentence-tailored exact retrieval, not keyword guessing.

Real-world: modern pipelines (retrieval-augmented generation, neural rankers, knowledge graphs, Elasticsearch-style engines) do not retire Boolean logic; they embed it as a fast first-pass filter and rank what survives. Elasticsearch and related stacks run Boolean pre-filters over inverted lists before any learned scorer sees a document.

Real-world: contact and address lookup, brand-exact shopping search (a named toothpaste brand should return that brand, not synonyms), library catalog lookup by author name, and biomedical search over PubMed and NCBI all favor exact Boolean behavior where synonyms would corrupt the answer. PubMed search for one gene symbol must not drift to a look-alike symbol.

2.8.4 Student Questions and Answers

2.9 From Notebook to Assignment: Boolean Retrieval in Code

2.9.1 The pipeline in miniature

A Python notebook replays the whole Boolean path on four short documents about schizophrenia, drugs, treatment, and breakthrough (each line treated as one document). The steps mirror the session: preprocess text with the NLTK library (tokenize, lowercase, reduce to base forms), build the inverted index as a dictionary of sorted terms plus postings, then run Boolean retrieval with AND, OR, and NOT over a typed query. The index output shows alphabetically sorted terms beside the documents holding each one. NLTK supplies the tokenizer and stemmer, so the notebook focuses on index logic rather than string plumbing.

Picture the notebook as three panels. The left panel shows raw lines. The middle panel shows tokens per line. The right panel shows the inverted index plus the answer set for the typed query. The uploader demo repeats the same three stages, upload a text file, view tokens, view the inverted index, type a Boolean query, with each uploaded line acting as one document. The takeaway in one line: the same code path serves the toy lines and the uploaded file, only the input changes.

2.9.2 Worked queries and the take-home brief

The take-home brief converts the demo into real practice. Build an application that loads multiple genuine documents (not one line per document), then carries out preprocessing, inverted-index construction, and Boolean querying over them. The companion interactive demo repeats the three stages with an uploader, and the follow-on assignment follows similar lines. Exploration beyond the brief is encouraged: try vector-side ideas on the same uploader, test with current coding tools, and bring findings back for discussion. The habit matters more than the harness: a good exploration question beats a long program. The session notes that its own demo code was drafted with AI assistance and then verified by hand, modeling exactly that workflow.

Exam Guidance Summary

No mark distribution, question pattern, or exempted topic was stated in this session. The signals below are importance cues worth converting into study tasks.

Key Industry Applications

Real-world: Westlaw-style legal search keeps Boolean exactness (wildcards, proximity, sentence bounds) where near-misses are unacceptable, with queries such as limit-plus-proximity chains checked sentence by sentence.

Real-world: retrieval-augmented generation, neural rankers, knowledge graphs, and Elasticsearch-style stacks reuse Boolean matching as a fast filter beneath ranking, so inverted lists prune billions of documents before any learned scorer runs.

Real-world: sponsored placement on shopping and search products layers payments above relevance ranking instead of changing the match core, keeping organic relevance separate from promotion.

Real-world: knowledge agents over office document stores index content into vectors and retrieve before composing answers, repeating the notebook chain of preprocess, index, match, and compose at production scale.

Real-world: contact and address lookup, brand-exact shopping search, library author catalogs, and PubMed plus NCBI biomedical search all prefer exact matching, since one drifted synonym can corrupt a name, brand, or gene symbol.

Real-world: web engines pre-build billion-scale inverted indexes with document frequencies, which is why plain queries return in milliseconds over ever-changing collections that are rebuilt continuously.