Information Retrieval

Vector Space Model and TF-IDF Ranking

Published: 2026-09-14

Level: postgraduate

Audience: Postgraduate students in Information Retrieval

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Term-document incidence matrix and Boolean evaluation — covered in Lecture 2 (The Term-Document Incidence Matrix and Boolean Evaluation)
Vector space model and angle-based ranking foundations — covered in Lecture 2 (The Vector Space Model: Weights, Angles, and Ranking)
Wildcard queries and permuterm index — covered in Lecture 4 and Lecture 5 (Wildcard Queries and Permuterm Index)
Biword and positional indexes for phrase search — covered in Lecture 4 and Lecture 5 (Biword and Positional Indexes for Phrase Search)
Phonetic matching with Soundex — covered in Lecture 5 (Phonetic Matching with Soundex)
Variable byte coding and gap compression — covered in Lecture 7 (Postings Compression with Gaps and Variable Byte Codes)
Jaccard coefficient and ranked retrieval foundations — covered in Lecture 7 (Ranked Retrieval and the Jaccard Coefficient)
Count matrix and term frequency dampening — covered in Lecture 7 (From Incidence Matrix to Count Matrix and Term Frequency)

# Vector Space Model and TF-IDF Ranking

8.1 From Boolean Retrieval to Ranked Retrieval and Jaccard Overlap

8.1.1 Why presence or absence stops being enough

Imagine you ask a library desk for books about cars and the clerk wheels out every book that mentions the word car even once, dumped in no order, a 400-page manual next to a passing joke in a novel. That pile is what the old setup gives you, and the question of this section is how to turn that pile into a ranked list where the best answer sits on top.

A Boolean model (a retrieval setup where each term is marked only as present with 1 or absent with 0 in each document) returns a set of matching documents with no order among them. A ranked retrieval setup (a list where documents appear sorted from most to least likely to satisfy the need behind the query) needs graded evidence, not just a yes-or-no match.

Think of Boolean matching like a light switch: on or off. Ranked retrieval is more like a dimmer dial: how strongly is this document about the query? When a word can occur once, twice, or a hundred times in one document, marking it only as 1 hides how strongly that document talks about the word. Just knowing that a word occurs is not enough to decide which document deserves to come first. Counting how often it occurs starts to matter. The Boolean approach is not a bad approach. It was a useful start, and it still powers exact needs such as a legal clause search. The move away from it happens because ranking needs graded evidence.

The table behind both setups tells the story. An incidence matrix (a table with terms as rows and documents as columns that records presence or absence) was the first form of this table. In that binary form each cell holds 1 when the row term occurs in the column document and 0 when it does not. The new step keeps the same rows and columns but replaces each 1 with a count:

	Doc 1	Doc 2
car	1	0
insurance	1	1

becomes, once repeats are counted:

	Doc 1	Doc 2
car	27	4
insurance	0	33

That count table is still a bag of words table (a table that keeps counts but drops word order), which means the order of words in the document is not kept. The classic example from the textbooks makes this concrete: under a bag of words view, the document "Mary is quicker than John" and the document "John is quicker than Mary" look identical, because both hold the same multiset of words. That loss of order is a drawback that stays with us through the classic weighting that follows, and it is also why phrase handling later needs extra machinery such as positional indexes.

Scope: the count table fixes the "how much" gap but keeps the "in what order" gap. Any need where order changes meaning, such as phrase queries or "A quicker than B" style facts, cannot be answered from counts alone. The vector model built in this lecture inherits that limit.

Picture the shift as a chart: on the horizontal axis put the number of times car occurs in a document (0, 1, 10, 50), on the vertical axis put the evidence that the document is about cars. A Boolean curve is flat after 1: it jumps from 0 to full at the first occurrence and never rises again. A ranked curve keeps climbing after 1, steeply at first and then more gently. The one-sentence takeaway is that ranking treats repeats as extra, fading evidence rather than no evidence. That fading shape is exactly what the log scaling in the next section will formalize.

In live search this is the difference between an unordered Boolean hit set of ten thousand pages and a top-10 page where the most focused pages surface first. Web engines never show the raw set; they always rank it.

8.1.2 Jaccard overlap and where it breaks

If Boolean is too coarse, what is the smallest step toward grading? The lecture tries overlap first: how much of the vocabulary do the query and the document share?

A Jaccard coefficient (a number that measures overlap between two sets) is the size of the shared part divided by the size of everything seen. Where $A$ is the set of terms in one text and $B$ is the set of terms in the other text, with $∣ A \cap B ∣$ as the size of shared terms and $∣ A \cup B ∣$ as the size of all distinct terms across both, the coefficient is: $J (A, B) = \frac{∣ A \cap B ∣}{∣ A \cup B ∣}$ The spoken form kept from the lecture is that overlap comes from A intersection B and the two sets come from their universe, that is A union B. Every symbol here is a set size: $∣ A \cap B ∣$ counts terms found in both texts, $∣ A \cup B ∣$ counts distinct terms found in either text, and the ratio always lands in $[0, 1]$ .

Worked mechanics with tiny sets. Let $A = {c a r, in s u r an ce}$ and $B = {c a r, a u t o}$ . Shared terms: car only, so $∣ A \cap B ∣ = 1$ . Distinct terms across both: car, insurance, auto, so $∣ A \cup B ∣ = 3$ . Then $J (A, B) = \frac{1}{3}$ , about 0.33. Sense-check: one shared word out of three distinct words feels like weak overlap, and 0.33 says exactly that. Two edge cases pin the scale: identical sets give $J = 1$ (full overlap), while sets with nothing in common give $J = 0$ (no overlap).

A second quick check sharpens the feel. Let $A = {c a r, in s u r an ce, b es t}$ and $B = {c a r, in s u r an ce, a u t o}$ . Then $∣ A \cap B ∣ = 2$ and $∣ A \cup B ∣ = 4$ , so $J = \frac{2}{4} = 0.5$ . Doubling the shared words from one to two while the universe grows only slightly lifts the score from 0.33 to 0.5, which matches the plain reading that these two texts agree more.

The drawback is direct and it is the whole reason the lecture moves on. Jaccard works on sets, so repeats do not count. When a term is seen twice in a document, that second occurrence adds nothing to the score. Take a query ${c a r}$ and two documents whose term sets are both ${c a r, in s u r an ce}$ . Document X mentions car once; document Y mentions car fifty times. Both give the same sets, the same intersection size 1, the same union size 2, and the same Jaccard $\frac{1}{2}$ . A document that mentions a query word fifty times gets the same overlap as one that mentions it once. That misses the frequency signal that ranking needs.

Assumption: Jaccard assumes each distinct term contributes exactly one vote no matter how often it repeats. That assumption breaks for text, where the second, fifth, and fiftieth mention still carry extra (though fading) evidence. It also treats every term as equally telling, so a shared the counts as much as a shared insurance.

Exam note: expect a short theory ask on why Jaccard is not enough for scoring. The answer in one line is that it ignores term frequency inside documents: it is a set measure, so repeats add nothing and rare telling words count the same as common filler words.

The bridge from here is forced: to rank, we must open up the sets into multisets with counts. That count is the term frequency of the next section, and the "not all words are equal" gap becomes the rarity weight of the section after that.

8.1.3 Student Questions and Answers

Q: We just started the vector space model, right? What did we cover about Jaccard?

A: Yes. We moved from Boolean presence or absence toward a model that can rank. We tried Jaccard overlap of query and document sets, $J (A, B) = ∣ A \cap B ∣ / ∣ A \cup B ∣$ , with the tiny run $A = {c a r, in s u r an ce}$ , $B = {c a r, a u t o}$ giving $\frac{1}{3}$ . We saw that repeats do not change Jaccard, so a term seen twice counts the same as a term seen once. That gap pushed us toward term frequency. Several students circled this same point, so treat the set-versus-count contrast as the one line to keep from this section.

8.2 Term Frequency and Log Frequency Weighting

8.2.1 What term frequency means

How do we turn "this document mentions the word a lot" into a number? The lecture's answer starts with the simplest count possible, then immediately warns that the count overstates its case.

A term frequency (the count of times a term $t$ occurs in a single document $d$ ), written $t f_{t, d}$ , is that raw count: $t$ is the term string such as car, $d$ is one document from the group, and $t f_{t, d}$ is how many times $t$ appears in $d$ . The spoken form kept from the lecture is the number of times that particular term T occurs in that document D. This is a per-document count. It never looks across the whole group.

Concrete values fix the meaning: when $t f_{t, d} = 0$ the term does not occur in that document at all; when $t f_{t, d} = 1$ it occurs once; when $t f_{t, d} = 27$ it occurs twenty seven times. The count matrix from the prior section is exactly this idea laid out as a table: each cell holds $t f_{t, d}$ for its row term and column document.

The central caution follows at once, and the professor leans on it hard. Relevance does not grow in direct proportion to this count. A term that occurs a hundred times is not a hundred times more on-topic than a single occurrence. The hundredth repeat adds less new evidence than the first few repeats.

Think of it as tasting soup, the professor's own picture: the first spoon tells you a lot about the flavor, the second spoon confirms it, and by the tenth spoon you are learning almost nothing new. Map it point by point: the first spoon is the first occurrence establishing the topic, later spoons are repeats adding fading confirmation, and the point where tasting stops teaching is the point where raw counts should stop climbing linearly. Where the analogy breaks: soup tasting saturates because your tongue tires, while text saturates because the topic is already established, but the fading shape is the same. That flattening idea is why a raw count is later scaled down.

A second everyday picture helps for exams: counting applause. The difference between zero claps and ten claps tells you a show started; the difference between one thousand claps and one thousand ten claps tells you almost nothing new. Same added count, very different added information.

8.2.2 Log scaled term weight

If raw counts over-claim, how do we keep the signal but tame the scale? The lecture reaches for the logarithm, the standard tool for turning multiplicative jumps into small additive steps.

A log frequency weight (a scaled form of the count that grows slowly when the count grows fast), written $w_{t, d}$ , is defined with $lo g_{10}$ as log base 10 and $t f_{t, d}$ as above: $w_{t, d} = 1 + lo g_{10} (t f_{t, d}) when t f_{t, d} > 0$ $w_{t, d} = 0 when t f_{t, d} = 0$ The spoken form kept from the lecture is 1 plus log tf when tf is at least 1, else 0. This matches the textbook sublinear scaling $w = 1 + lo g t f$ for $t f > 0$ , which exists precisely because twenty occurrences do not carry twenty times the weight of one.

Why add 1? Because $lo g_{10} (1) = 0$ . Without the added 1, a term that occurs once would get weight 0, the same as a term that never occurs. That would erase a real occurrence. Adding 1 keeps a single occurrence visible with weight 1. Why use log at all? Because raw counts can blow up. Common words can reach huge counts while topic words stay small. Log pulls huge counts down and keeps the scale workable. Without scaling, a word that occurs a hundred thousand times would swamp every sum. With log scaling, its lead shrinks to a few points.

Tiny numeric tour with base 10, each step shown. When $t f_{t, d} = 1$ , $w_{t, d} = 1 + lo g_{10} (1) = 1 + 0 = 1$ . When $t f_{t, d} = 2$ , $w_{t, d} = 1 + lo g_{10} (2) = 1 + 0.30 = 1.30$ . When $t f_{t, d} = 10$ , $w_{t, d} = 1 + 1 = 2$ . When $t f_{t, d} = 100$ , $w_{t, d} = 1 + 2 = 3$ . When $t f_{t, d} = 1000$ , $w_{t, d} = 1 + 3 = 4$ . Each tenfold jump in count adds only 1 to the weight. That is the normalizing effect in action: counts multiply by ten, weights crawl up by one. Sense-check: a document with 1000 repeats scores only 4 times a single-occurrence document, not 1000 times, which matches the soup intuition that later repeats matter less.

Picture this as a chart with count on a stretched horizontal axis and weight on the vertical axis. The raw-count line is a steep straight ramp climbing to the sky. The log-weight curve rises fast from 0 to 1 on the first occurrence, then bends hard and crawls almost flat: 10 gives 2, 100 gives 3, 1000 gives 4. Landmarks: the intercept at $t f = 1, w = 1$ (single occurrence preserved), the tenfold-adds-one staircase, and the flat tail where huge counts barely move the needle. The takeaway in one line is that log scaling compresses count explosions into a workable few-point range.

Scope: log scaling assumes repeats carry fading but positive evidence. It applies to ordinary content words. It breaks for spam-style stuffing where repeats are injected to game ranking rather than to add content, which needs separate spam handling, and it does not fix the separate problem that long documents naturally accumulate larger counts, which needs length normalization later.

Common traps cluster here. First, taking $lo g (0)$ : the formula never evaluates log at zero because the $t f = 0$ case is defined separately as weight 0. Second, dropping the +1 and wiping out single occurrences. Third, mixing raw and log weights in one sum, which compares numbers from two different scales. Fourth, switching log bases mid-answer (base 10 versus base 2 changes the numbers but not the ranking order, so pick the base the ask names and stay with it).

Web-scale text keeps this scaling because raw counts for words such as the and and would otherwise dominate every sum. Modern stacks such as BM25 keep the same fading idea with a capped saturation curve instead of a pure log, but the motive is identical.

Exam note: the classic form to write in an answer is $w = 1 + lo g_{10} (t f)$ for $t f > 0$ , else 0. Name the base. If an ask says raw values, skip the log and use $t f$ directly. If it says weighted or log form, use the log version. Markers reward the $t f = 0$ branch written out, not assumed.

8.2.3 Student Questions and Answers

Q: I saw another form where term frequency was count divided by total words in the document. How is that different from 1 plus log tf?

A: The plain count $t f_{t, d}$ is the base fact: how many times term $t$ occurs in document $d$ . The form $1 + lo g_{10} (t f_{t, d})$ is one weighted variant of that fact: it damps huge counts onto a log scale. The form of count divided by document length is another variant: it adjusts for document size rather than damping bursts. The classic model here uses the log variant so that both the term part and the rarity part below live on log scales and can be multiplied cleanly. Other variants are allowed, including length-ratio and augmented forms, but the log form tones down huge counts while the plain ratio form does not tone them down in the same way. Use whichever the ask names; never mix two variants in one table.

Q: Why is log extra load for a machine yet we still use it?

A: Log costs more arithmetic steps than plain addition or multiplication. We still pay that cost because counts grow in a skewed way, a few words explode while most stay small, and log brings them to a shared, workable range where one runaway word cannot swamp the sum. The gain in ranking quality is worth the extra arithmetic. In practice the cost is paid once at index time and reused for every query, so it is cheap where it counts.

8.3 Document Frequency, Collection Frequency and Inverse Document Frequency

8.3.1 Document frequency and collection frequency side by side

Term frequency looks inward at one document. The next two counts step back and look at the whole collection, and the lecture's key move is choosing the right one.

A document frequency (the count of documents in the whole group that hold term $t$ at least once), written $d f_{t}$ , counts how many of the $N$ total documents hold $t$ at least once, where $N$ is the total number of documents in the group. The spoken form kept from the lecture is count of documents in the whole collection in which that particular T occurs. A collection frequency (the total number of occurrences of term $t$ across the whole group), written $c f_{t}$ , adds up every occurrence everywhere. Its spoken form is total occurrences of the term in the entire collection. A corpus (the whole set of documents we search over) is the scope for both $df$ and $c f$ .

The two differ in what they count, and a tiny table makes the split unmissable. Take a small group with three documents where the word insurance occurs 5 times in document 1, 4 times in document 2, and 1 time in document 3. Then $c f = 5 + 4 + 1 = 10$ , because collection frequency sums occurrences. But $df = 3$ , because three documents hold it at least once. Counts per document feed $c f$ ; presence per document feeds $df$ .

Second contrast to lock the pattern. Word X occurs 10 times but all 10 sit inside a single document: then $c f = 10$ yet $df = 1$ . Word Y occurs 10 times spread as one occurrence in each of 10 documents: then $c f = 10$ yet $df = 10$ . Same $c f$ , wildly different $df$ . Sense-check: Y is spread across the collection while X is a local burst, and only $df$ sees that spread. That spread is exactly what ranking needs to know.

8.3.2 Why rarity matters and why document frequency wins

Why should spread matter at all? Because rare terms are better clues than common ones.

A rare term carries more signal than a common term. The word the occurs almost everywhere, so seeing it tells us little about which document fits a need. A focused word such as insurance occurs in far fewer documents, so seeing it is a stronger clue. Think of it as footprints, the professor's own picture: pigeon prints on a street tell you little because pigeons are everywhere, while tiger prints tell you a lot because they are rare. Map it directly: street is the collection, footprint type is the term, and rarity of the print is the $df$ signal. Where it breaks: a rare misspelling is also a rare footprint but a useless clue, so rarity must later combine with the in-document count rather than stand alone.

The textbook's Reuters numbers turn this intuition into evidence. Collection frequency values for try and insurance sit close together, about 10422 versus 10440, which would suggest they matter equally. But their document frequencies split apart: insurance in about 3997 documents, try in about 8760 documents. Same total count, very different spread. The word try is spread thin across many documents. The word insurance is packed into fewer documents and marks those documents more sharply. So $c f$ suggests a tie while $df$ shows that insurance is more focused and more telling.

More cases drive the same lesson home. Take spider versus a very rare spider-study word such as arachnocentric. A document with the rare word gives a stronger signal than one with only the common word spider. Take a two-word need such as capricious person. The word capricious is rare and should count more. The word person is common and should count less. The rarity gap is the whole reason for the next weight.

Scope: prefer $df$ over $c f$ because one repeat-heavy document can skew $c f$ and $c f$ hides spread. The textbook states the design reason directly: in trying to discriminate between documents for scoring it is better to use a document-level statistic than a collection-wide sum. $c f$ still matters elsewhere, for instance in language modeling, but for separating documents $df$ is the right lens.

8.3.3 Inverse document frequency formula

How do we convert "rare means telling" into a number that is big for rare terms and small for common ones? By inverting the frequency and taming the ratio with a log.

An inverse document frequency (a rarity number that is large for rare terms and small for common terms), written $i d f_{t}$ , is defined with $N$ as total number of documents in the group, $d f_{t}$ as document frequency of term $t$ , and $lo g_{10}$ as log base 10: $i d f_{t} = lo g_{10} (\frac{N}{d f _{t}})$ The spoken form kept from the lecture is log of N by DF for normalization. Log appears again for the same scaling reason as before: without log the ratio $N$ over $d f_{t}$ can swing across six orders of magnitude, while with log the swing stays within a few points.

A one-line derivation shows where the bounds come from. Since $1 \leq d f_{t} \leq N$ , the ratio satisfies $1 \leq N / d f_{t} \leq N$ , so $lo g_{10}$ of it satisfies $0 \leq i d f_{t} \leq lo g_{10} (N)$ . A term in every document gets 0; a term in exactly one document gets $lo g_{10} (N)$ , the maximum. The formula can never go negative and never needs an infinity guard, because $d f_{t} \geq 1$ for any indexed term.

Worked ladder with $N = 1 0^{6}$ , every step shown. When $d f_{t} = 1$ , $i d f_{t} = lo g_{10} (1 0^{6} /1) = lo g_{10} (1 0^{6}) = 6$ . When $d f_{t} = 100 = 1 0^{2}$ , $i d f_{t} = lo g_{10} (1 0^{6} /1 0^{2}) = lo g_{10} (1 0^{4}) = 4$ . When $d f_{t} = 1000 = 1 0^{3}$ , $i d f_{t} = 3$ . When $d f_{t} = 1 0^{4}$ , $i d f_{t} = 2$ . When $d f_{t} = 1 0^{5}$ , $i d f_{t} = 1$ . When $d f_{t} = 1 0^{6}$ , $i d f_{t} = lo g_{10} (1) = 0$ . So a one-in-a-million term scores 6 while a term in every document scores 0. A rare surname gets the top score; the word the gets the lowest score. Sense-check: each extra zero in $df$ shaves exactly 1 off the score, so rarity maps to a tidy staircase. When $i df$ is near 0 for a term in every document, that term adds almost nothing to a ranking sum. That is the math saying what intuition already says: a word everywhere helps nowhere.

The textbook's Reuters snapshot grounds this in real numbers with $N = 806791$ : car with $df = 18165$ gives $i df = 1.65$ , auto with $df = 6723$ gives $i df = 2.08$ , insurance with $df = 19241$ gives $i df = 1.62$ , best with $df = 25235$ gives $i df = 1.5$ . Notice auto outranks car on rarity even though both are car-industry words, because auto is the rarer spelling in that collection. Also note the exam-friendly question the book poses: the $i df$ of a term in every document is $lo g (1) = 0$ , which is exactly how the math implements a stop list without maintaining one.

Picture the shape: horizontal axis $df$ on a log scale from 1 to $N$ , vertical axis $i df$ falling in a straight descending line from $lo g (N)$ to 0. Landmark the two ends (sole-document term at top, ubiquitous term at floor) and the midpoint where $df = N$ gives half the max. The takeaway: rarity converts to a small additive bonus, not a wild multiplier.

Exam note: write $i d f_{t} = lo g_{10} (N / d f_{t})$ , state what $N$ and $d f_{t}$ are, and add the two boundary readings: $d f_{t} = N$ gives 0 (no separating power), $d f_{t} = 1$ gives the max. An ask on why we do not use collection frequency expects the try-versus-insurance split: one repeat-heavy document can skew $c f$ , and $c f$ cannot show spread.

8.3.4 Student Questions and Answers

Q: If document frequency of term 1 is 100000 and term 2 is 100, which matters more?

A: Term 2 matters more. Smaller document frequency means rarer, and rarer means more telling: with the same $N$ , term 2 gets $i df = lo g (N /100)$ while term 1 gets only $lo g (N /100000)$ , a full 3 points lower on a base-10 scale. Common terms such as the and and occur almost everywhere, so their power to pick out one document is weak. The rule to carry is inverse: less it appears, more it matters.

Q: In the table where N is 10 to the power 6 and the term also has DF 10 to the power 6, IDF is 0. Does that mean all terms are in all documents?

A: No. It means that one particular term occurs in all $1 0^{6}$ documents. The ratio is $1 0^{6} /1 0^{6} = 1$ and $lo g_{10} (1) = 0$ . That term gets zero weight because it cannot separate one document from another, exactly like a stop word. Other terms in the same table keep their own $df$ values and nonzero scores.

8.4 TF-IDF Weighting and Query Document Scoring

8.4.1 How the two weights join

We now have two pulls: repeats inside one document say "this document dwells on the term," rarity across the collection says "this term is a sharp clue." The lecture joins them by multiplication so that a term must earn both to score big.

A TF-IDF weight (the product of the term part and the rarity part), written $w_{t, d}^{t f i df}$ , uses $t f_{t, d}$ as term frequency in document $d$ and $i d f_{t}$ as above: $w_{t, d}^{t f i df} = (1 + lo g_{10} (t f_{t, d})) \times i d f_{t} when t f_{t, d} > 0$ $w_{t, d}^{t f i df} = 0 when t f_{t, d} = 0$ The spoken form kept from the lecture is TF multiplied with IDF, also heard as TF dot IDF or TF times IDF, and at longer length as take the term frequency weightage between term to document and multiply that with inverse document frequency. In the textbook's compact notation this is $t f - i d f_{t, d} = t f_{t, d} \times i d f_{t}$ , with the log variant $w f - i d f_{t, d} = w_{t, d} \times i d f_{t}$ when sublinear scaling is on.

This product balances two pulls. The first factor rewards repeats inside one document but in a toned-down log way. The second factor rewards rarity across the group. A word that repeats a lot in this document and is rare elsewhere gets a large product. A word that is common elsewhere gets pulled down even when it repeats here. The textbook ranks the three regimes from highest to lowest weight: many mentions inside a few documents at the top, fewer mentions or many hosting documents in the middle, and terms in virtually all documents at the floor near zero.

Think of hiring: term frequency is how loudly a candidate claims a skill, rarity is how few candidates hold that skill. Loud claims about a common skill impress little; even quiet evidence of a rare skill stands out. The product is the interview score combining both.

A query-document score (the sum of TF-IDF products over shared terms only), written $S cor e (q, d)$ , uses $q$ as query and $d$ as document: $S cor e (q, d) = t \in q \cap d \sum w_{t, d}^{t f i df}$ The spoken form is summation of TF IDF for terms that belong to both query and document, with the sum over terms T that are in both Q and D, for all terms matching with the query in that document D, and the score is 0 when no term matches. Term frequency pushes the sum up, but the log inside keeps the rise gentle. In the textbook this first appears as the overlap-style sum refined from raw counts to TF-IDF weights, before cosine normalization sharpens it further.

Two properties matter for exams. First, only shared terms contribute: query words absent from the document add nothing, and document words absent from the query are ignored. Second, the sum rewards coverage of the whole need: two medium matches beat one giant match plus one miss, as the numeric run below shows.

This same product idea travels. In biology it appears as gene frequency times inverse cell frequency, written GF times ICF, where rare genes get higher weight and common genes get lower weight. In ranking history the method BM25, short for Best Matching 25, builds on TF-IDF as its base and adds capped term saturation plus explicit length handling on top. So TF-IDF is both a working scorer and the foundation later methods extend.

Scope: this score assumes terms contribute independently and additively, with no phrase, synonym, or position effects. It also leaves document length uncorrected: a long document that repeats query words many times can outscore a short focused one purely on volume. Both limits are patched later, by positional machinery and by cosine normalization.

8.4.2 Full numeric run with car and insurance

The tables used here give document frequencies and term frequencies for a small set, with $i df$ already worked out. For the term car, $i df = 1.65$ across all three documents because $i df$ depends on the whole collection, not on one document. Term frequencies are 27 in document 1, 4 in document 2, and 24 in document 3. Recall from the Reuters snapshot that $i df = 1.65$ corresponds to $df = 18165$ in $N = 806791$ , since $lo g_{10} (806791/18165) = 1.65$ .

Single-term run for car, each line shown. For document 1 the spoken form was one plus log 27 times 1.65: $w_{c a r, 1} = (1 + lo g_{10} (27)) \times 1.65 = (1 + 1.43) \times 1.65 = 2.43 \times 1.65 = 4.01$ For document 2 the spoken form was one plus log 4 times 1.65: $w_{c a r, 2} = (1 + lo g_{10} (4)) \times 1.65 = (1 + 0.60) \times 1.65 = 1.60 \times 1.65 = 2.64$ For document 3 the spoken form was one plus log 24 times 1.65: $w_{c a r, 3} = (1 + lo g_{10} (24)) \times 1.65 = (1 + 1.38) \times 1.65 = 2.38 \times 1.65 = 3.93$ So for the single term car the order is document 1 at 4.01, then document 3 at 3.93, then document 2 at 2.64. In compact form: document 1 is greater than document 3 is greater than document 2. Sense-check: 27 versus 24 repeats give nearly tied weights (4.01 vs 3.93) because the log flattens the gap, while 4 repeats fall a full 1.3 points behind at 2.64.

Now widen to the two-word query car insurance. The $i df$ for insurance is shared across documents the same way (textbook value 1.62 at $df = 19241$ , lecture run uses the matching column). The worked TF-IDF values for insurance used here are 0 in document 1, 4.08 in document 2, and 3.99 in document 3, where the 0 reflects $t f = 0$ for insurance in document 1. The score for each document adds its car part and its insurance part:

For document 1: $S cor e = 4.01 + 0 =$ 4.01. For document 2: $S cor e = 2.64 + 4.08 =$ 6.72. For document 3: $S cor e = 3.93 + 3.99 =$ 7.92.

So the final order for query car insurance is document 3 at 7.92, then document 2 at 6.72, then document 1 at 4.01. The lesson often surprises at first glance. Document 2 holds the single largest cell among all six values for insurance (4.08), which can make it look like the winner on its own. But document 3 is solid on both words, near 4 on each, and the sum lifts it past document 2. Ranking by sum rewards coverage of the whole need, not one spike. The overall TF-IDF mass for car alone across the three, $4.01 + 2.64 + 3.93$ , is a side total, but ranking for a query always uses the per-document sum shown above.

A note on bases: the run here uses $lo g_{10}$ . The textbook poses this as an exercise and the answer is worth memorizing: changing the log base multiplies every $i df$ (and every log term weight) by a shared constant, so all document scores scale together and their relative order does not change. Still, stick to the base named in the ask for exact numbers.

Exam note: read the ask first. When it says raw term values, use $t f \times i df$ with no log; when it says weighted or log form, use $(1 + lo g (t f)) \times i df$ . Show the per-term products and the per-document sums separately, because method marks split across those two stages. If insurance is absent ( $t f = 0$ ), write the 0 branch explicitly.

8.4.3 Student Questions and Answers

Q: Between TF dot IDF, is the dot multiplication or addition? And what does the summation over query terms do?

A: The dot joins TF and IDF for one term by multiplication: for one term in one document compute $(1 + lo g_{10} (t f_{t, d})) \times i d f_{t}$ . The summation, written with sigma as $\sum_{t \in q \cap d}$ , then adds those per-term products across the words in the need. For query car insurance and document 1 we add the car product 4.01 and the insurance product 0 to get 4.01. We repeat that addition per document (6.72 and 7.92 for documents 2 and 3) and rank by the totals. So dot is per-term multiply, sigma is across-term add.

Q: What is the score equation really asking us to find for query against three documents?

A: It asks for one number per document: the sum of TF-IDF products for words that occur in both that query and that document. With three documents we get three totals (here 4.01, 6.72, 7.92). Those totals set the order 3, 2, 1. That order is the ranked answer we return instead of the whole group. When no term matches, the sum is empty and the score is 0.

8.5 Document Vectors, Sparsity and High Dimensions

8.5.1 From count table to weighted table to vectors

Three forms of the same table appear in order, and the lecture walks them as one morphing object. First a binary table with 0 and 1 (the incidence matrix). Then a count table with $t f_{t, d}$ in each cell. Then a weighted table with TF-IDF values in each cell. Same rows, same columns, richer numbers at each pass.

A document vector (an ordered list of real numbers, one per term, that stands for that document as a point in term space) is one row of that weighted table read sideways. Terms are the axes of that space: one axis per distinct term, one coordinate per axis holding that term's weight in this document. A query vector (the same kind of ordered list built for the query string) is built by the identical recipe so that query and document live on a shared scale. In the textbook's language the collection becomes a term-document matrix with $M$ term rows and $N$ document columns, and a query is treated as a very short document dropped into the same space.

Why must the query follow the same recipe? Because comparison needs a shared currency. If documents carry log-scaled TF-IDF weights while the query carries raw 0-or-1 flags, the dot products mix two scales and the ranking drifts. Without that shared scale the numbers are not comparable. In practice the same recipe on both sides is the norm unless there is a pressing reason to split them, and the one standard split (log plus rarity on the query, log only on documents) is documented in the SMART section with its reasons.

A concrete miniature makes the geometry click. With vocabulary [car, insurance, best] a document scoring [4.01, 0, 2.1] is a single arrow in 3-axis space pointing far along the car axis, nowhere along insurance, and partway along best. A second document [2.64, 4.08, 0] points elsewhere. Closeness of arrows will soon mean closeness of topics.

8.5.2 Sparsity and scale

Two facts about these arrows dominate every engineering choice that follows: they are almost all zeros, and they live in an enormous space.

A sparse vector (a long list where most entries are 0) is what we get at every stage: binary, count, or weighted. The tempest example in the session shows this well: most entries are 0 and only two hold weights. Nothing in TF-IDF removes that sparsity, because weighting rescales nonzero entries without creating new ones. We live with it in classic models and handle it later with other tools such as inverted indexes that skip zeros entirely.

The width is the other strain. Each distinct term is one axis, so a toy demo has 4 or 6 axes while a web engine reaches millions or even billions of axes, one per vocabulary term. Each vector is that wide, yet any single document touches only its own few hundred distinct words, so almost all entries are 0. That mix of huge width and mostly zeros shapes every choice about storage and scoring that follows: store only nonzero postings, score only query-term axes, and never materialize the full dense arrow.

Picture a football stadium with a seat per term and only a handful of occupied seats per document. The task of scoring is checking just the seats named by the query rather than walking the whole stadium. The one-sentence takeaway is that sparsity is not a defect to fix inside TF-IDF; it is the property the index exploits to stay fast.

Scope: the vector view assumes word order carries no signal (bag of words) and terms act as independent axes (no synonym or phrase geometry). Those assumptions break for phrases, negation, and synonyms, which is why later machinery adds positions, expansion, and embeddings. Sparsity plus independence is what makes the classic model fast and also what bounds its understanding.

Keep this bridge line: once every document and the query are arrows in one shared weighted space, ranking becomes geometry. The next section asks which geometric notion, gap or angle, actually matches topical closeness.

8.5.3 Student Questions and Answers

Q: Once I have the weighted table, what is a document now?

A: It is a vector of real TF-IDF weights, one weight per term: pick the document's row and read its weighted cells left to right as coordinates. The count table turned into a weighted table, and each document row of that table is the vector we score with. The query gets the same treatment on its own row so both arrows share axes and scale.

8.6 Why Euclidean Distance Fails and Cosine Takes Over

8.6.1 The length trap in Euclidean scoring

Once documents are arrows, the obvious question is how to measure closeness between arrows. The lecture starts with the familiar tool from school geometry, then breaks it on purpose.

Why reach for gap first? Because in everyday space the straight-line gap tracks closeness well: nearby points are similar places. The hope was that nearby arrows would mean similar topics. The trap is that text arrows encode length as verbosity while topics live in direction, so gap confuses a long document with a distant one.

A Euclidean distance (the straight-line gap between two points), with $q_{i}$ as query weight on term $i$ and $d_{i}$ as document weight on term $i$ , is: $d i s t (q, d) = i \sum (q_{i} - d_{i})^{2}$ The spoken form kept from the lecture is square root of squared sums of differences. Every symbol: $i$ runs over all term axes, $q_{i} - d_{i}$ is the per-axis gap, squaring removes sign, summing pools all axes, and the root returns to the original units.

Concrete clash from the lecture. Documents hold four words rich, poor, gap, gross. The query holds two words rich, poor. Both query words occur in document 2, so by word overlap we expect high closeness: a small angle, near-identical direction. But Euclidean math punishes the size gap. The four-word vector carries extra nonzero coordinates where the two-word query holds zeros, so per-axis gaps like $d_{g a p} - 0$ and $d_{g r oss} - 0$ pile squared mass into the sum and the distance comes out large. Distribution of shared words says near, length says far. Length wins in the formula and gives the wrong signal for text. So distance can measure gap, but here gap is the wrong notion of fit. The textbook states the same warning: two documents with near-identical term distributions can show a large vector difference purely because one is much longer. Sense-check: duplicating a document word for word (same topic, double length) doubles its Euclidean distance from the query while its topic never moved, which proves gap tracks verbosity, not aboutness.

Scope: Euclidean gap assumes all axes share comparable scales and that vector length is content. Both fail for text: axes have wildly different rarity scales, and length mostly reflects verbosity or multi-topic coverage. Gap tools also let a single high-count axis dominate the squared sum. The professor's flag to keep is that Euclidean length dominates and hides term overlap.

Exam note: an ask on why Euclidean is a poor fit expects this line in full: vector length dominates and hides term overlap, because extra axes and larger counts inflate squared gaps even when shared-word direction agrees. Name the rich-poor-gap-gross clash as evidence.

8.6.2 Angle, cosine and length normalization

If gap tracks the wrong thing, what tracks the right thing? Direction: do the query and document point the same way through term space, regardless of how long each arrow is?

An angle view fixes the focus. Smaller angle means closer direction. Larger angle means apart. Cosine tracks that wish directly: $cos (0^{\circ}) = 1$ for same direction, $cos (9 0^{\circ}) = 0$ for fully apart directions with no shared terms. Since cosine falls steadily from 0 degrees to 90 degrees for the nonnegative vectors of text (no negative weights, so angles stay in the first quadrant), it reads as a similarity that slides from 1 down to 0.

A cosine similarity (the cosine of the angle between two vectors) has the spoken form ratio of dot product to the lengths of the vectors. With $q \cdot d$ as dot product and $∥ q ∥_{2}$ and $∥ d ∥_{2}$ as lengths: $cos (q, d) = \frac{q \cdot d}{∥ q ∥ _{2} \times ∥ d ∥ _{2}}$ Here dot product means point to point multiplication summed up, written $q \cdot d = \sum_{i} q_{i} \times d_{i}$ , over all term axes $i$ . Length means L2 norm, written $∥ x ∥_{2} = \sum_{i} x_{i}^{2}$ . The spoken forms kept from the lecture are dot product is point to point multiplication of two vectors and length is L2 norm, square root of squared sums. Dimensional check: dot and length-product share squared-weight units, so their ratio is unit-free in $[0, 1]$ for nonnegative text vectors.

The denominator is the fix. It divides out the length effect that hurt Euclidean scoring. Both vectors are brought to a shared size before the comparison.

A length normalized vector (a vector divided by its own length) is built by dividing each entry by its L2 norm. With $x_{i}$ as entry $i$ and $∥ x ∥_{2}$ as its length: $x^_{i} = \frac{x _{i}}{∥ x ∥ _{2}}$ The spoken form is dividing each of the components by its length. After this step each vector is a unit vector (a vector whose length is 1), so $∥ x^∥_{2} = 1$ . On normalized vectors the denominator is $1 \times 1 = 1$ and cosine collapses to a plain dot product: $cos (q^, d^) = q^\cdot d^= i \sum q^_{i} \times d^_{i}$ That short form holds only on length normalized vectors. It does not hold on raw vectors.

Think currency conversion, the canonical picture for normalization: comparing prices in mixed currencies misleads until every price is converted to one currency. Length normalization converts every document to the one currency of unit length, so only direction (relative word mix) decides. Where it breaks: pure direction ignores that a longer document may genuinely cover more topics, a subtlety later patched by pivoted length handling.

Picture all normalized arrows living on the surface of a sphere of radius 1 centered at the start. Long and short originals now end at the same distance from the start; only the angle between them varies. Documents sharing the query's word mix cluster in one patch of the sphere surface; documents with nothing shared sit a quarter-turn away at cosine 0. The takeaway: length no longer steers the order, direction alone decides.

Comparison in one glance:

	Euclidean distance	Cosine similarity
Asks	How far apart are the endpoints?	How aligned are the directions?
Long duplicate document	Scores far (wrong)	Scores identical (right)
Extra non-query words	Inflates gap	Factored out by denominator
Range on text vectors	0 upward, smaller is nearer	0 to 1, larger is nearer
When to pick	Short equal-length numeric spaces	Text vectors of mixed lengths

The one-line picker: for mixed-length text arrows always reach for cosine; keep Euclidean for low-dimensional physical gaps.

Beginner traps: reading cosine as a distance (it is a similarity, larger means nearer); applying the dot-only shortcut to raw unnormalized vectors; forgetting the sum runs over all axes so absent terms contribute $0 \times w = 0$ ; and expecting negative cosines in TF-IDF space, which cannot happen because weights are never negative.

8.6.3 Student Questions and Answers

Q: What is the best closeness tool: Euclidean, Manhattan, or something else for text?

A: Euclidean and Manhattan are the first tools that come to mind for gaps, and both sum per-axis differences (straight-line versus city-block). For text vectors of very different lengths, both gap tools let length dominate: extra words and bigger counts inflate the gap even when the topic direction matches. Angle tools fit better because they compare direction. That is why cosine, with its length division, is the pick here. Several students asked this in different words; the canonical answer is direction over gap for text.

Q: After normalization, why is similarity just a dot product?

A: Because each normalized length is 1. Start from dot over lengths, $cos = (q \cdot d) / (∥ q ∥ \times ∥ d ∥)$ . Replace each length with 1 after normalization. The denominator vanishes to $1 \times 1 = 1$ , leaving only the dot sum $\sum_{i} q^_{i} \times d^_{i}$ . That shortcut is valid only after both sides are normalized; on raw vectors keep the full denominator.

8.7 Length Normalization and Cosine Worked in Full

8.7.1 Log weights then L2 then unit vector

The previous section gave the geometry; this one runs the full arithmetic chain on real novel counts so you can repeat it blind in an exam. Three documents, Sense and Sensibility short SAS, Pride and Prejudice short PAP, and Wuthering Heights short WH, with four terms affection, jealous, gossip, and wuthering, carry raw term frequencies in the table. The run here uses log weights only, no rarity factor, to isolate the normalization lesson. A full production run would fold $i df$ back in before normalizing; the steps after that stay identical.

The three-pass recipe in order: log-scale every count, measure the arrow length, divide every entry by that length. Each pass has one formula and one job: tame bursts, size the arrow, convert to unit currency.

Step one is log weights with the spoken form weight is one plus log tf. For SAS the raw counts 115, 10, 2, 0 turn into weights 3.06, 2, 1.3, 0. The first entry shows the arithmetic in full with the spoken form log 115 is 2.06, so 1 plus 2.06 gives 3.06: $w_{1} = 1 + lo g_{10} (115) = 1 + 2.06 = 3.06$ The same $1 + lo g_{10} (t f)$ step gives $1 + lo g_{10} (10) = 1 + 1 = 2$ for the second entry and $1 + lo g_{10} (2) = 1 + 0.30 = 1.30$ for the third, with 0 staying 0 by the zero branch. So the SAS vector before normalization is $[3.06, 2, 1.3, 0]$ , where each slot lines up with affection, jealous, gossip, wuthering in that order. Check the compression: raw counts span 115 down to 2 (a 57-fold range) while weights span only 3.06 to 1.3 (barely 2-fold), which is the log doing its job before geometry even starts.

Step two is length with the spoken form square root of squared sums. In symbols:

$∥ S A S ∥_{2} = 3.0 6^{2} + 2^{2} + 1. 3^{2} + 0^{2} = 9.36 + 4 + 1.69 + 0 = 15.05 = 3.78$ Every symbol: each weight is squared to drop sign and punish large axes, the squares sum to 15.05 pooling all axes, and the root returns to weight units giving length 3.78. Numerical spot-check: $3.0 6^{2} = 9.36$ , $2^{2} = 4$ , $1. 3^{2} = 1.69$ ; the total 15.05 roots to 3.78, matching the lecture number.

Step three divides each entry by 3.78:

$S A S^= [\frac{3.06}{3.78}, \frac{2}{3.78}, \frac{1.3}{3.78}, \frac{0}{3.78}] = [0.789, 0.515, 0.335, 0]$ The spoken form kept from the lecture is 3.06 divided by 3.78 gives 0.789, 2 divided by 3.78 gives 0.515, 1.3 divided by 3.78 gives 0.335. Unit-length check: $0.78 9^{2} + 0.51 5^{2} + 0.33 5^{2} + 0 = 0.623 + 0.265 + 0.112 = 1.00$ within rounding, so the L2 norm of this new vector is 1 and it is a unit vector. The same divide-by-length pass turns PAP and WH into unit vectors as well, giving a length normalized matrix ready for cosine math. Sense-check: the biggest raw count 115 now contributes only 0.789 of direction, so verbosity has been converted out.

8.7.2 Cosine as dot product on the normalized table

Cosine on this normalized table is dot product only, with the spoken form point to point multiplication. For SAS and PAP the shape is:

$cos (S A S, P A P) = 0.789 \times 0.82 + 0.515 \times 0.555 + 0.335 \times 0.0 + 0 \times \dots = 0.647 + 0.286 + 0 + 0 = 0.94$ The numbers 0.82 and 0.555 are the matching normalized slots from PAP for affection and jealous. Zeros line up where a term is absent (gossip missing from PAP, wuthering missing from both Austen novels). Step detail: $0.789 \times 0.82 = 0.647$ carries most of the total because both novels dwell on affection; $0.515 \times 0.555 = 0.286$ adds the jealous agreement; the rest add nothing. The total 0.94 is near 1, so SAS and PAP read as highly similar. Sense-check against the textbook's three-term raw-frequency variant, which reports 0.999 on the same pair: both versions agree the Austen pair is near-identical, with the small gap tracing to the lecture's four-term log-weighted setup versus the book's three-term raw setup.

The same dot pass gives SAS with WH and PAP with WH at lower values separated by about 0.05 (textbook run: about 0.888 for SAS-WH on its variant). WH shares three words with SAS, which can make a same-count guess point to WH as closer. Yet SAS with PAP still scores higher because affection and jealous carry heavy weights in those two vectors while WH spreads weight toward gossip and wuthering. That is the intended takeaway: weights steer the order, not just shared-word counts. This run left out the rarity factor on purpose to show normalization alone. A full run would fold $i df$ back in before normalizing, which would further lift distinctive terms such as gossip and wuthering.

Scope: this demo normalizes log-tf weights with rarity off on both sides (shorthand LNC on each side). It isolates geometry cleanly but understates rare-term separation. In production the same three passes run on TF-IDF weights, and query-versus-document dots replace document-versus-document dots. The arithmetic pattern never changes: weights, squares, root, divisions, dot sum.

Exam note: show every intermediate in order: log weights, squares, root, divisions, then dot sum. The method marks reward the steps more than the final 0.94. Line up term slots in one fixed order (affection, jealous, gossip, wuthering) through all three passes so the checker can trace each number to its slot.

8.7.3 Student Questions and Answers

Q: Is the C in the model the cosine value for a term or for a document?

A: C stands for the length normalization pass and the cosine comparison that follows it: normalize each vector to unit length, then take dot products between vectors. It applies to whole vectors, document to document or query to document, not to one term alone. The scalar out of that dot, such as 0.94 for SAS-PAP, is the similarity. So C names the process on full arrows; the number it yields compares full arrows.

8.8 Weighting Variants and SMART Notation

8.8.1 The DDD QQQ code

With term scaling, rarity, and normalization each offering switches, the field needed a compact label for "which recipe did you run?" The answer is a six-letter code.

A SMART notation (a short code for which weighting recipe was used) writes three letters for documents and three for queries. The shape is DDD for term, rarity, normalization on documents and QQQ for the same three slots on queries. Slot 1 is the term-frequency component, slot 2 the document-frequency component, slot 3 the normalization. The letters seen here map as L for log scaled term frequency $1 + lo g (t f)$ , N for no change in that slot, T for rarity with log inverse document frequency, B for binary 0 or 1, A for an augmented scaled term form used in methods such as BM25, and C for cosine length normalization. The textbook's full table adds variants such as natural, pivoted-unique, byte-size, and log-average rows, but these six letters cover every classroom ask.

Decode the greatest hits. LTC means log term part, rarity part on, cosine normalization on. LNC means log term part, no rarity part, cosine normalization on. LTN means log term part, rarity part on, no normalization. LNN means log only with the other two slots off. The point is compact: the code tells a reader exactly which of the three switches were flipped without reprinting the pipeline.

The standing rule is to use the same recipe on both sides so query and document share a scale. The textbook's standard example is lnc.ltc: documents carry log tf with no idf plus cosine normalization, queries carry log tf with idf plus cosine normalization, a deliberate near-match that spares document-side idf work. Classroom tasks sometimes split them harder to show two recipes at once. That split is a teaching device. Live setups keep them matched unless a strong reason forces a split, a warning the lecture phrases as matched recipes share scale.

8.8.2 Two classroom splits decoded

The lecture runs two splits on one tiny table so the code letters become muscle memory.

First split: documents use LNC while queries use LTN. For documents that means log term weights, no rarity weights, with cosine normalization. For queries that means log term weights, rarity weights on, with no normalization. Term tables, rarity column, and length divisions line up with that split. Document length comes from squares such as $1^{2} + 0 + 1^{2} + 1. 3^{2}$ style sums, then each entry is divided by that root to form a unit vector. The final similarity is a product of the two sides (document unit entries times query log-idf entries, summed). Because only one side is normalized, the result can cross above 1. The spoken point kept is that on a fully normalized pair the dot must sit between 0 and 1, but here it does not because the query side skipped normalization. That overshoot is not a bug in arithmetic; it is the signature of a half-normalized split.

Second split: the same tiny task redone as LTC on both sides. The only change is that documents now fold in the rarity column too, so each document entry becomes log-tf times idf before the same square-root-divide pass. Walking that version after the session locks in the difference between LNC and LTC: the letter in the middle flips from N to T when the rarity factor joins.

Textbook ask pattern: a paragraph describes the pipeline and wants the DDD QQQ code. Decode slot by slot. Are logs used for terms in documents and queries? Yes on both, so L opens both codes. Is rarity used in documents? No, so N sits in the middle of DDD. Is rarity used in queries? Yes, so T sits in the middle of QQQ. Is normalization used in documents? Yes, so C closes DDD. Is it used in queries? No, so N closes QQQ. That spells DDD as LNC and QQQ as LTN. The punchline for study: spotting LTC is simple once you check the three slots in order, term log, rarity, normalization, for each side. A companion exam drill from the old paper uses LNC on both sides when rarity is off everywhere with cosine on everywhere.

Scope: the code describes computation, not quality. LTC on both sides is the balanced default, lnc.ltc is the textbook efficiency standard, and exotic splits are diagnostic tools. Picking letters never fixes deeper modeling gaps such as synonyms or phrases; it only names the weighting consistently so results can be reproduced.

8.8.3 Student Questions and Answers

Q: If there is no logarithm, what sits in place of L? And when term frequency is 0, does log break?

A: When raw counts are used as is with no log, the term slot is N for no change (natural $t f$ ), or B when the table is binary 0 or 1. The weight equation itself stays $1 + lo g_{10} (t f)$ whenever log is on. When $t f = 0$ we do not take $lo g (0)$ , which is undefined. We set the weight to 0 directly by the zero branch. The added 1 handles the $t f = 1$ case since $lo g_{10} (1) = 0$ , leaving weight 1 so a single occurrence is not wiped out.

Q: What are A and the capital L variants in the table?

A: A marks an augmented term form that scales counts in a capped way, of the kind used inside BM25: $0.5 + 0.5 \times t f / max t f$ in the lecture's telling, which guards against one outlier term dominating. B marks the binary 0 or 1 choice from the Boolean table. L marks the $1 + lo g (t f)$ choice. Other rows in the full table mix these with rarity switches (including probabilistic idf) and normalization switches (including pivoted and byte-size forms) to name many combined recipes. For this course only A, B, L, N, T, C appear in asks.

Q: Is the DDD QQQ split with different recipes on each side important on its own, or would plain LTC do?

A: Plain matched LTC is the working default you would ship. The split matters as a reading skill: an ask may hand you a table where documents skip rarity and queries keep it, or where only one side is normalized, and then demand the code plus the matching arithmetic. You need to name that split as LNC with LTN and run each side by its own letters. Once named, the arithmetic is the same log, multiply, normalize steps you already know. So learn LTC as the tool and LNC-with-LTN as the label you must read fast.

8.9 Practice Set: Wildcards, Binary Cosine, Soundex, Phrase Indexes and Byte Codes

8.9.1 Suffix wildcard by reversal

A query with a star in an awkward spot cannot run as a plain prefix walk. The lecture's fix is to spin the problem until the star sits where the index wants it.

A wildcard query (a search string with a star standing for any tail, possibly empty) needs a special path when the star is not at the end. A suffix need such as star plus ology asks for words ending in ology. The trick is to flip both sides so the star lands at the end, turning a suffix hunt into a prefix hunt. The professor's fixed crux is that the star must end up at the end.

Steps in order. Reverse the query string: star ology becomes ygol star after reversal, where the star now sits at the end. Reverse every dictionary term the same way (cardiology becomes ygolo idrac in full reversal, and similarly for the rest). Then match as a plain prefix hunt for ygol star. Matches include cardiology, neurology, biology, and radiology, since each reversed form starts with ygol. Those four are the retrieved terms. When the star already sits at the end, as in a plain prefix need such as card star, no reversal is needed and the plain trie or B-tree walk runs as is.

Why does flipping preserve correctness? Reversal is a mirror: word $w$ ends with suffix $s$ exactly when reversed word $r e v (w)$ starts with $r e v (s)$ . So the set of words ending in ology equals the set whose reversals start with ygol. The star-at-end machinery (tries, sorted term lists, B-trees) then applies unchanged.

Tree and order notes: the same reversal must be applied to keys inside any tree or hash structure used for lookup, whether a binary search tree, a balanced tree, or a B-tree. Lexicographic order among reversed keys is kept so branch walks still work: sort the reversed forms and rebuild branches in that order. When the ask hands you a tree, you also build its reversed form step by step. When no tree is asked, showing the reversed query plus the reversed dictionary scan with matched terms is enough.

Mini drill to self-test. Dictionary: organ, organic, organism, allergy. Need: star ganic (suffix ganic). Reversed need: cinag star. Reversed terms: nagro, cinagro, msinagro, ygrella. Prefix cinag star matches cinagro (organic) and msinagro (organism) but not nagro or ygrella. Retrieved: organic, organism. Sense-check: both end in ganic, neither is a prefix hit, so reversal did work a plain walk could not.

Exam note: write every step in order: original need, reversed need, reversed dictionary forms, prefix walk, final list. Skipping the reversed-dictionary line is the most common mark loss even when the final list is right.

Q: If the need had been a prefix, would we still reverse?

A: No. A prefix need such as card star already has the star at the end, so plain wildcard matching runs as is on the original dictionary and tree. Reversal is only for needs where the star sits elsewhere (leading star for suffix, inner star for infix, possibly via rotation structures). The goal is always to make the hunt a prefix hunt with minimum machinery.

Q: Do we need to build a reversed tree from scratch in the answer?

A: Only when the ask explicitly wants a tree. Then start from the given base tree, since fair asks give the base tree or at least the dictionary terms to shape branches. Reverse each key, keep lexicographic order, and show the reversed branches with the ygol star walk marked. Otherwise a clear term-level reversal plus match list earns the marks without redrawing any tree.

8.9.2 Binary vectors and cosine ranking

Not every cosine task needs TF-IDF weights. This drill strips weighting away and tests whether the geometry runs clean on zeros and ones.

A binary vector task hands you 0 or 1 vectors for a query and for each of faculty 1, faculty 2, and faculty 3. Length effects stay small here because entries are only 0 or 1, but they do not vanish: a faculty vector with more ones still has a longer L2 norm ( $count of ones$ ), so normalization still matters.

Method template to run per pair. For query $q$ and faculty $f$ : dot $q \cdot f = \sum_{i} q_{i} \times f_{i}$ counts shared ones; lengths $∥ q ∥_{2} = \sum q_{i}^{2}$ and $∥ f ∥_{2} = \sum f_{i}^{2}$ are square roots of one-counts; cosine $cos = (q \cdot f) / (∥ q ∥ \times ∥ f ∥)$ . Work each of the three pairs fully: dot, both lengths, division. The highest cosine picks the best match. Tiny illustration: query $[1, 1, 0]$ against F1 $[1, 1, 1]$ gives dot 2, lengths $2 \times 3$ , cosine $2/ 6 = 0.816$ ; against F2 $[1, 0, 0]$ gives dot 1, lengths $2 \times 1$ , cosine $1/ 2 = 0.707$ ; so F1 outranks F2 despite its extra non-shared one, because two shared ones outweigh the length penalty. Sense-check every line: dots are whole counts, lengths are roots of counts, cosines sit in $[0, 1]$ . The ask tests clean arithmetic, dot, lengths, divisions, more than new ideas.

Traps: skipping normalization because "binary is simple" and ranking by raw dot counts instead; misaligning term slots between query and faculty rows; and forgetting that absent-absent zeros contribute nothing (only shared ones score). Line up slots in one fixed term order through all pairs.

8.9.3 Soundex phonetic codes

Spoken queries misspell by sound, not by letter. Soundex groups names that sound alike so a spoken surname still finds its stored cousins.

A Soundex code (a letter plus three digits that groups names by sound) lets spoken forms match stored forms despite spelling shifts. Rules used here: keep the first letter as is; map remaining letters by the given table; ignore vowels A E I O U and the letters H W Y (they contribute no digit); collapse side-by-side repeats that map to the same digit into one digit; pad with zeros to reach three digits. The mapping table printed in the ask is the authority; follow it digit by digit. Standard mappings behind this session: BFPV to 1, CGJKQSXZ to 2, DT to 3, L to 4, MN to 5, R to 6.

Spoken surname Shankar runs letter by letter. Keep S. Skip H (ignored). Skip A (vowel). N maps to 5. K maps to 2. Skip A (vowel). R maps to 6. Digits in order: 5, 2, 6, already three, no padding needed. Code: S526. Repeat the same per-letter pass for each stored form: Shankar with E, Shankar without H, Shukla, and Shaker, showing each keep, skip, map, and collapse line. Forms that land on the same code are the likely phonetic matches for the spoken query. Sense-check: S526 starts with the kept S and carries three consonant-class digits, the required shape. Exam note: show the per-letter walk, not just the final code, because the walk carries the marks.

Adjacent-repeat handling deserves its own line because it decides close calls. Adjacent same-sound letters count once, so NN keeps one N digit (one 5, not two). The rule applies to coded equivalence, not raw letters: two different letters mapping to the same digit side by side also collapse. Vowels and H W Y between same-digit consonants are conventionally treated as separators in many textbook variants, but follow the ask's printed rule when it specifies one.

Picture the code space as pigeonholes labeled A000 to Z999: thousands of spellings funnel into each hole, and retrieval pulls the whole hole for a spoken probe. The takeaway: Soundex trades precision for tolerance, which suits name lookup and hurts exact-term ranking.

Q: What when a word would map to more than three digits? And do double letters count twice?

A: Adjacent same-sound letters count once, so NN keeps one N digit and similar runs collapse before the length check. Vowels plus H W Y dropping trims further length, so overlong codes are rare in practice. When a query still yields a longer code, that longer code (or its truncated-to-spec form per the ask) is the form to compare against stored codes computed the same way. The mapping table in the ask is the authority: follow it digit by digit and state any truncation explicitly.

8.9.4 Biword versus positional phrase handling

A phrase need cares about order, not just co-occurrence. Two index designs answer it at different price points, and this drill runs both on one example so their gap is visible.

A phrase query such as secure payment gateway needs the three words adjacent and in order, not just co-occurring somewhere. A biword index (an index over adjacent word pairs) handles it by indexing secure payment and payment gateway as units. A positional index (an index that also stores word positions in each document) handles it by storing for secure, payment, and gateway their document plus position postings such as secure in D1 at 1.

Biword pass: secure payment occurs in D1, D2, D3. Payment gateway occurs in D1, D3, D4. The overlap of those two sets is D1 and D3. Positional pass: build postings such as secure in D1 at 1, D2 at 1, D3 at 2, D4 at 3; payment in D1 at 2, D2 at 2, D3 at 3, D4 at 1; gateway in D1 at 3, D2 at 4, D3 at 4, D4 at 2. Then enforce the order rule: secure at $P$ , payment at $P + 1$ , gateway at $P + 2$ in the same document. D1 with 1, 2, 3 passes. D3 with 2, 3, 4 passes. D2 fails because gateway sits at 4 rather than 3. D4 fails on order. True answer: D1 and D3. Sense-check: both routes agree here, but agreement is not guaranteed in general.

Here both routes land on D1 and D3, but that tie does not always hold. Biword matching is cheaper yet can return false hits when pairs occur but the full order breaks. A false-positive shape to memorize: a document holding artificial intelligence in one spot and intelligence applications in another, without the full three-word run artificial intelligence applications in order, passes both biword postings and their overlap yet lacks the phrase. Positional postings cost more labor and storage yet give exact order checks through the $P$ , $P + 1$ , $P + 2$ test.

Comparison in one glance:

	Biword index	Positional index
Stores	Adjacent pairs	Term plus per-occurrence positions
Phrase test	Overlap of pair sets	$P, P + 1, P + 2$ adjacency in one doc
Cost	Smaller, faster	Larger postings, exact
Failure mode	False positives on split pairs	None on order, but heavier
When to pick	Cheap pre-filter, short phrases	Exact phrase needs, exams asking "better"

The one-line picker: when asked which route is better for exact phrase needs, pick positional and show the $P$ , $P + 1$ , $P + 2$ check.

In production these ideas power quoted-phrase search: biword-style pairs prune candidates fast while positional verification confirms order before ranking.

8.9.5 Variable byte gaps, permuterm rotation and skip pointers

Three compression and speed tricks close the practice set. Each is a short deterministic procedure, and each is marked on visible steps rather than final numbers.

A variable byte task starts from a posting list, forms gaps between successive doc ids, then counts bits and bytes per gap and sums them for the total. Steps: list ids in order (for example 50, 53, 60); write each gap as current minus prior with the first gap as is (50, 3, 7); map each gap to its byte length under variable byte coding (small gaps fit one byte, larger gaps need a continuation byte each); add them for the total compressed size. That sum is the answer for that list. Show the gap subtraction line so the checker can trace each byte back to its gap, then a per-gap byte table, then the sum.

A permuterm rotation (a trick that spins each term with a sentinel so any star form becomes a prefix hunt) follows the same star-at-end drive as reversal but handles stars anywhere, not just leading stars. Spin the need so the star lands last. The spoken form in the session was S star NG with sentinel becoming NG sentinel S star after the spin, where the sentinel (spoken here as dollar, written as an end mark in textbooks) anchors the rotation. Apply the same spin to dictionary terms, index all rotations in a rotated vocabulary, then prefix-match the spun need. Reversal is the light special case for pure suffix needs; permuterm is the general wildcard engine.

A skip pointer count (extra jumps that speed up list intersection) uses square root of list length as the guide. For a list of size $n$ , plant about $n$ skips spread evenly across the list (for $n = 64$ that is about 8 skips roughly every 8 entries). Each skip stores the next jump target so AND-walks leap over dead stretches instead of stepping doc by doc. Other revision points in this stretch: edit distance with insert, delete, copy or replace plus backtrack of costs through the table; front coding with shared prefixes inside sorted blocks; block size trade-offs in dictionary compression (bigger blocks save more prefix bytes but force longer sequential scans plus heavier lookup overhead).

Q: For variable byte codes, what exactly do we hand in?

A: Three lines in order: gaps first (each subtraction shown), then per-gap bit and byte counts, then the total sum. Show the gap subtraction line so the checker can trace each byte back to its gap. A bare total with no gap line earns little even when the number is right.

8.10 Old Paper Walkthrough and Course Revision

8.10.1 Term frequency, Boolean needs and edit distance

The paper opens with short direct asks that reward clean definitions plus one worked trace. No deep critical essay hides here; each ask names its method and the marks follow the visible steps.

First ask: what is term frequency and does a Boolean setup need it. Term frequency $t f_{t, d}$ is the count of term $t$ in document $d$ , a per-document number. Document frequency $d f_{t}$ is the count of documents holding $t$ , a corpus-level number. Boolean matching needs only presence (1 or 0) for its yes-or-no choice, so term frequency is not needed for its decision. The split to memorize: term frequency looks at one document, document frequency looks at the corpus. A one-line addendum earns completeness: ranked setups do need $t f$ (plus $i df$ ), which is exactly the Boolean-to-ranked arc of this lecture.

Second ask: edit distance by Levenshtein steps with backtrack. The procedure: build the table with one string along the top and the other down the side, fill each cell with the minimum over insert, delete, and copy-or-replace costs from its three neighbors, then trace back from the bottom-right corner to the top-left naming the operation used at each step. Show the table, fill costs cell by cell, then draw the path and label every move. Marks reward the visible path and per-cell costs, not just the final number. A frequent slip is reporting the distance without the backtrack; the backtrack is half the answer.

Third ask: stemming versus lemmatization for a question-answering setup over a document group. Pick lemmatization. Stemming (crude suffix chopping such as Porter rules) cuts fast but can merge forms that should stay apart (for instance organization versus organ collapsing toward a shared chop). Lemmatization (mapping to the base dictionary form, the lemma, using vocabulary and grammar) keeps the true base meaning, for example better mapping toward good or meeting as noun staying distinct from meet. That care suits answer text where exact base meaning matters and a wrong merge surfaces a wrong answer. For a broad web engine stemming can still be the pragmatic pick on speed and recall, but for this answer-focused need the base-form route fits better. Give one word example where crude chopping hurts and the lemma keeps meaning, and state the choice in the first line so the checker sees the verdict immediately.

8.10.2 Biword false hits, Soundex, Heaps law and front coding

This block is four one-paragraph drills. Each is a two-minute task when the template is memorized.

Biword false-positive ask: give a document that a biword overlap returns for artificial intelligence applications yet should not return. Use a document holding artificial intelligence in one spot and intelligence applications in another, without the full three-word run in order, for example "The lab studies artificial intelligence. Separately, the team builds intelligence applications for finance." Both biwords hit, the overlap hits, but the phrase is absent. That gap is exactly why positional checks exist, and the answer should close with that line plus the $P, P + 1, P + 2$ remedy.

Soundex ask: write codes for two given terms with the mapping table printed in the paper. Follow the same keep-first, map rest, drop vowels and H W Y, collapse repeats, pad to three digits used in the practice set. With the table in hand this is a one-minute task. Show per-letter work: keep, skip, digit, collapse, pad. Never free-recall the table when it is printed; copy it and cite each digit to its row.

Theory ask: what is Heaps law and how does it help inverted index compression. Heaps law (vocabulary size grows sublinearly with collection size, roughly $V = K n^{b}$ with $b$ well below 1) says doubling the collection adds far fewer than double the new words. State the law in words first, then link it: a smaller-than-linear vocabulary estimate bounds dictionary size, which guides how much dictionary compression (front coding, blocking) and memory planning can save and how the dictionary scales to web size. Keep it to the two-mark depth the paper gives it: law in one line, compression link in one line.

Front coding ask: compress a small dictionary snapshot with shared prefix runs. Steps: sort terms into correct order first (the sample order with L Y after L is already sorted, else sort it, since front coding only works on sorted runs); then write the first term whole and each later term as shared-prefix length plus suffix tail (for example BAT T style runs storing shared counts). Block size ask with it: the session demo used 4 and then 8 or 16. Bigger blocks save more prefix bytes but force longer sequential scans inside a block plus heavier lookup-table overhead. When the wanted key sits last in a 64-word block, the scan walks 63 wasted entries and the saving evaporates. That is why block size cannot grow without bound: it trades bytes saved against time spent scanning plus pointer overhead.

8.10.3 Jaccard, MapReduce, cosine ranking and paper tactics

Jaccard issue ask: the scoring gap is that Jaccard ignores term frequency inside documents. Write that line and tie it to the set-versus-count point from the opening section: $J (A, B) = ∣ A \cap B ∣ / ∣ A \cup B ∣$ sees distinct terms only, so repeats add nothing and rarity counts nothing. One line plus the formula closes this ask.

MapReduce ask with static group size $N$ plus small $n$ , $R$ , $Z$ and minimum parses: note that this depth was not built up in the taught path. Do not burn early minutes there. The tactic is explicit: mark it, finish every core sum first (Soundex, gaps, Jaccard line, biword false hit, front coding, TF-IDF and cosine tables), and return only when the core sums are done. Partial definitions earn more per minute on familiar ground than a long stall on unfamiliar symbols.

Cosine ranking ask for query data mining, data warehousing over three documents with term frequencies for data, analysis, algorithm, mining, technique, warehousing: build the term-document table (six columns in fixed order), apply log term weighting $1 + lo g (t f)$ on both query and document with no rarity on either side and cosine normalization on both sides (shorthand LNC on documents with LNC on queries when rarity is off on both, decoded slot by slot in the answer), then dots between normalized query and each normalized document. Concretely per document: log-scale each of the six counts, square and sum and root for the length, divide to unit entries, dot with the normalized query, compare the three scalars. Six-wide vectors make this the longest task on the paper. Tactic: solve short direct tasks first (Soundex, gaps, Jaccard line, biword false hit, front coding), then spend the remaining block on this table plus the edit-distance table. No coding or pseudo-code tasks are set. Mapping tables and step hints are printed in the paper, so practice reading the code letters DDD QQQ straight from the wording: log versus raw in slot one, rarity on versus off in slot two, normalization on versus off in slot three.

In production these pieces sit together: BM25 as the TF-IDF successor in ranking stacks, gene-cell weighting as the biology mirror of the same product idea, and permuterm plus skip structures as the index-speed toolkit around the scorer.

Exam note: attempt order is part of the answer strategy. Short deterministic drills first, six-term cosine table and edit-distance table last with the remaining time. Every table answer shows slots, weights, lengths, divisions, and dots; never a bare ranking.

8.10.4 Student Questions and Answers

Q: Will the paper test deep critical thinking or direct how-to steps?

A: The style is direct. Each ask names the method: do Soundex coding, do variable byte coding, rank with cosine, show edit backtrack. The load is in doing the steps without slips rather than inventing arguments. Knowing ideas plus one clean practice run per method is enough. The cosine table is the only long one, so leave it for a later slot in the answer order and give it an unbroken time block.

Q: For text-method asks, will mappings and hints be printed?

A: Yes. Mapping tables (Soundex classes) and step cues (which weighting, which normalization) come with the paper. Read the DDD QQQ wording line by line, pick log versus raw, rarity on versus off, normalization on versus off, then run the numbers in that recipe. Copy the printed table rather than recalling it, and keep term slots in the printed order.

Exam Guidance Summary

Ranked retrieval needs counts, not just presence. Jaccard overlap $J (A, B) = ∣ A \cap B ∣ / ∣ A \cup B ∣$ misses repeats because it is a set measure: a term seen fifty times scores the same as one seen once, and rarity counts nothing. A top short-theory point: write the formula plus the set-versus-count line.
Classic term weight is $w_{t, d} = 1 + lo g_{10} (t f_{t, d})$ for $t f_{t, d} > 0$ , else 0. Raw $t f$ times $i df$ is only when the ask says raw. Adding 1 saves the $t f = 1$ case from collapsing to 0, since $lo g_{10} (1) = 0$ . Tenfold count adds exactly 1 to the weight.
Rarity weight is $i d f_{t} = lo g_{10} (N / d f_{t})$ . Rare means large (up to $lo g (N)$ at $df = 1$ ); in-every-document means 0. $df$ looks across the corpus while $t f$ looks inside one document. Boundary readings $df = N \to 0$ and $df = 1 \to max$ earn method marks.
Prefer $df$ over $c f$ because one repeat-heavy document can skew $c f$ and $c f$ hides spread. Insurance in 4000 versus try in 9000 with tied $c f$ near 10400 is the model example: $c f$ calls a tie, $df$ shows insurance is the sharper clue.
Query score is $S cor e (q, d) = \sum_{t \in q \cap d} w_{t, d}^{t f i df}$ with $w_{t, d}^{t f i df} = (1 + lo g_{10} (t f_{t, d})) \times i d f_{t}$ . Car insurance totals 4.01, 6.72, 7.92 for documents 1, 2, 3 give order 3, 2, 1. Show per-term products then per-document sums; coverage of both query words beats one spiky term.
Euclidean $d i s t (q, d) = \sum_{i} (q_{i} - d_{i})^{2}$ lets length dominate: extra axes and bigger counts inflate squared gaps even when direction agrees (rich-poor-gap-gross clash). Cosine $cos (q, d) = (q \cdot d) / (∥ q ∥_{2} \times ∥ d ∥_{2})$ with $∥ x ∥_{2} = \sum_{i} x_{i}^{2}$ fixes it by dividing out length so direction decides.
Normalization is $x^_{i} = x_{i} / ∥ x ∥_{2}$ giving $∥ x^∥_{2} = 1$ and $cos (q^, d^) = q^\cdot d^$ . SAS length 3.78 from $[3.06, 2, 1.3, 0]$ to $[0.789, 0.515, 0.335, 0]$ and SAS-PAP dot 0.94 are the reference numbers. Show weights, squares, root, divisions, dot sum in slot order.
SMART code is DDD for documents plus QQQ for queries over term, rarity, normalization slots. L is log $1 + lo g (t f)$ , T is rarity with log idf, C is cosine normalization, N is none, B is binary, A is augmented. LNC with LTN (half-normalized, scores can exceed 1) versus LTC on both sides is the split to decode fast, slot by slot from the wording.
Practice drills to redo once each: reversal for suffix star ology to ygol star with cardiology, neurology, biology, radiology (show reversed dictionary); binary cosine across faculty vectors (dot, lengths, divisions per pair); Soundex S526 for Shankar (per-letter walk); biword overlap versus $P$ , $P + 1$ , $P + 2$ positional check for secure payment gateway with answer D1, D3; gaps then bytes then sum for variable byte lists; permuterm spin for inner stars; $n$ skips for intersections.
Old-paper tactics: Boolean needs no $t f$ ; Levenshtein needs table plus backtrack with insert, delete, copy or replace; lemmatization beats stemming for answer-focused needs (stemming merges, lemma keeps base form); biword false hit shape is artificial intelligence plus intelligence applications without the full phrase; Heaps law bounds vocabulary sublinearly for dictionary planning; front coding needs sorted order then prefix lengths; bigger blocks trade prefix saving against sequential scan plus lookup overhead; six-term LNC cosine table is longest, attempt it after short tasks. No coding tasks are set; mapping tables and step hints are printed.

Key Industry Applications

Ranked search over million-document groups uses TF-IDF sums with cosine normalization to order results instead of returning an unordered Boolean set; the same pipeline ranks product catalogs, help centers, and site search.
BM25 ranking stacks keep TF-IDF as the base and layer capped term saturation plus explicit document-length handling on top; it is the default scorer in most open-source search engines.
Biology mirrors the same product as gene frequency times inverse cell frequency for rare-gene weighting in single-cell analysis, where rare marker genes pick out cell types the way rare terms pick out documents.
Wildcard and permuterm structures with reversal or rotation power suffix and infix hunts in dictionaries, file search, and autocomplete indexes where users type fragments rather than full terms.
Phonetic codes group spoken surnames such as Shankar variants with Shukla and Shaker for tolerant name lookup in customer records, voice search, and census cleaning.
Positional postings power exact phrase needs such as secure payment gateway in legal and e-commerce search, while biword pairs serve as a cheaper but less exact pre-filter for candidate pruning.
Variable byte gap codes, front coding with block scans, skip pointers near $n$ , and Heaps-law vocabulary estimates keep large inverted indexes small and fast enough to serve web-scale query loads from memory-mapped structures.

IR Lecture 8 notes · Vector Space Model and TF-IDF Ranking

Information Retrieval· postgraduate· 2026-09-14

Sections Breakdown

1From Boolean Retrieval to Ranked Retrieval and Jaccard Overlap

Boolean retrieval returns unordered sets; Jaccard adds graded set overlap but ignores repeats, motivating term-frequency counts

2Term Frequency and Log Frequency Weighting

Term frequency counts repeats per document; log scaling 1+log(tf) tames bursts so relevance grows sublinearly

3Document Frequency, Collection Frequency and Inverse Document Frequency

Document frequency measures spread across the corpus; idf=log(N/df) turns rarity into weight, beating collection frequency

4TF-IDF Weighting and Query Document Scoring

TF-IDF multiplies log damped tf by idf; query score sums shared-term products, rewarding coverage of the whole query

5Document Vectors, Sparsity and High Dimensions

Weighted table rows become document and query vectors in one shared space; they are sparse and very high dimensional

6Why Euclidean Distance Fails and Cosine Takes Over

Euclidean distance fails on mixed-length text; cosine with L2 normalization compares direction and fixes ranking

7Length Normalization and Cosine Worked in Full

Full SAS normalization chain log weights to length 3.78 to unit vector, then dot product cosine 0.94 with PAP

8Weighting Variants and SMART Notation

SMART notation DDD.QQQ labels term, rarity, normalization choices; classroom splits LNC.LTN versus LTC decoded

9Practice Set: Wildcards, Binary Cosine, Soundex, Phrase Indexes and Byte Codes

Practice drills: suffix reversal, binary cosine, Soundex S526, biword versus positional phrase checks, byte gaps and skips

10Old Paper Walkthrough and Course Revision

Old paper revision: direct method asks with step tables; short drills first, six-term cosine and edit tables last

Postgraduate students in Information Retrieval

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

From Boolean Retrieval to Ranked Retrieval and Jaccard Overlap

Must-know: Boolean gives unordered sets; Jaccard grades by set overlap but ignores term frequency, so ranking needs counts

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

Top pitfall: Answering a Jaccard scoring question with a ranked argument that forgets Jaccard ignores repeats and treats all terms equally

Self-check: Compute Jaccard for A={car,insurance}, B={car,auto} and explain why a 50x repeat of car changes nothing

Connects to: 8.2, 8.4

Term Frequency and Log Frequency Weighting

Must-know: tf counts repeats in one document; log weight 1+log(tf) damps bursts so tenfold count adds 1

$w_{t, d} = 1 + lo g_{10} (t f_{t, d}) for t f > 0, 0 otherwise$

Top pitfall: Evaluating log(0), dropping the +1 so tf=1 collapses to 0, or mixing raw and log weights in one sum

Self-check: Compute w for tf=1, 10, 100 and explain why the +1 exists

Connects to: 8.1, 8.3, 8.4

Document Frequency, Collection Frequency and Inverse Document Frequency

Must-know: df counts documents holding t; idf=log(N/df) rewards rarity; prefer df over cf because cf hides spread

$i d f_{t} = lo g_{10} (N / d f_{t})$

Top pitfall: Using cf where df belongs, or reading idf=0 as all terms everywhere instead of one ubiquitous term

Self-check: With N=1e6 compute idf for df=1, 1000, 1e6 and explain try vs insurance

Connects to: 8.2, 8.4

TF-IDF Weighting and Query Document Scoring

Must-know: TF-IDF multiplies damped tf by rarity; query score sums shared-term products giving order 3, 2, 1 on car-insurance run

$S cor e (q, d) = t \in q \cap d \sum (1 + lo g_{10} (t f_{t, d})) \times i d f_{t}$

Top pitfall: Using raw tf when ask wants log form (or reverse), or ranking by one spiky term instead of per-document sums

Self-check: Recompute car weights from tf 27,4,24 with idf 1.65 and rank the two-word query

Connects to: 8.2, 8.3, 8.6

Document Vectors, Sparsity and High Dimensions

Must-know: Weighted table rows are document vectors in shared term space; vectors are sparse and ultra-wide

Top pitfall: Forgetting the query must use the same weighting recipe or comparing vectors from different scales

Self-check: Explain why TF-IDF keeps sparsity and why queries need the same recipe

Connects to: 8.4, 8.6

Why Euclidean Distance Fails and Cosine Takes Over

Must-know: Euclidean gap lets length dominate; cosine divides out length so direction decides; normalized cosine is a dot product

$cos (q, d) = \frac{q \cdot d}{∥ q ∥ _{2} \times ∥ d ∥ _{2}}$

Top pitfall: Calling cosine a distance, or using dot-only shortcut on raw unnormalized vectors

Self-check: Explain the rich-poor-gap-gross clash and why duplicating a document changes Euclidean but not cosine

Connects to: 8.4, 8.5, 8.7

Length Normalization and Cosine Worked in Full

Must-know: Log weights then L2 length then divide gives unit vectors; cosine is dot sum with SAS-PAP 0.94

$∥ S A S ∥_{2} = 3.78, S A S^= [0.789, 0.515, 0.335, 0], cos (S A S, P A P) = 0.94$

Top pitfall: Skipping square-root-divide steps or misaligning term slots across the three passes

Self-check: Recompute SAS length 3.78 and normalized entries, then the 0.94 dot term by term

Connects to: 8.6, 8.8

Weighting Variants and SMART Notation

Must-know: SMART DDD.QQQ names term, rarity, normalization per side; L=log, T=idf, C=cosine, N=none, B=binary, A=augmented

Top pitfall: Naming LNC/LTC from memory instead of decoding the three slots per side from the wording

Self-check: Decode LNC.LTN versus LTC slot by slot and explain scores above 1 in half-normalized splits

Connects to: 8.6, 8.7, 8.10

Practice Set: Wildcards, Binary Cosine, Soundex, Phrase Indexes and Byte Codes

Must-know: Suffix reversal to ygol*; binary cosine per pair; Soundex S526 walk; biword overlap vs P,P+1,P+2 with D1,D3; gaps-bytes-sum and sqrt skips

Top pitfall: Skipping reversed-dictionary or per-letter or gap lines and handing in bare final lists or codes

Self-check: Reverse *ology need, walk Shankar to S526, and run P,P+1,P+2 on D1-D4

Connects to: 8.1, 8.6, 8.10

Old Paper Walkthrough and Course Revision

Must-know: Paper is direct how-to steps; Boolean needs no tf; lemmatization for QA; six-term LNC cosine table attempted last

Top pitfall: Burning early minutes on unfamiliar MapReduce symbols or handing in bare rankings without step tables

Self-check: State the attempt order and the slot-by-slot DDD QQQ reading for the six-term cosine ask

Connects to: 8.2, 8.8, 8.9

Previous LectureLecture 07 · Index Compression and Ranked Retrieval

Next LectureLecture 09 · Evaluation in Information Retrieval

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.