CS726 — Midterm Summary (Lectures 1–22)

📘 Lecture 1 — Information Retrieval Techniques

📖 Overview: This lecture introduces the foundational concepts of Information Retrieval (IR), covering the transition from structured to unstructured data storage, the digitization of libraries, and the core models used in modern search engines. It lays the groundwork for understanding how systems like Google find and rank relevant documents from vast datasets.

🗂️ Topics Covered

The lecture covers the limitations of traditional library and database search, contrasting them with modern IR systems. It introduces the shift from structured data in tables to semi-structured and unstructured text, the digitization of libraries, and the concept of IR models. Key topics include the use of indexes and inverted indexes in search engines like Google/Bing/Yahoo, the importance of test corpora for evaluation, and an introduction to the probabilistic model for relevance.

📝 Lecture Summary

Introduction

The lecture begins by contextualizing Information Retrieval (IR) techniques within the evolution of information storage. It contrasts traditional Library Management Systems that rely on structured data (like tables) with the need to search and manage vast amounts of semi-structured and unstructured data that does not fit neatly into database rows and columns.

Structured Data Storage / Tables

Traditional systems, like an Employee database, store information in structured tables with rows (records) and columns (fields). For example, a table might have columns for Employee, Department, and Salary. Searching requires queries on these specific fields, which is effective for well-defined data but fails for free-form text or document content.

Semi-Structured and Unstructured

Modern IR deals heavily with semi-structured data (e.g., web pages with HTML tags) and unstructured data (e.g., plain text documents, emails, books). This type of data has no pre-defined schema, making it difficult to search with simple database queries. IR techniques are specifically designed to handle this complexity.

Library Digitization

The digital transformation of physical libraries into digital repositories is a core challenge. This involves converting physical books and documents into searchable digital formats. The goal is to provide access to the content, not just the metadata (title, author). This shift is what makes techniques like full-text search and relevance ranking essential.

Information Retrieval Models

To find relevant documents from a large collection, IR systems use mathematical models. The lecture explicitly introduces:

• Indexes / Inverted Indexes: A fundamental data structure. An inverted index maps words back to the documents they appear in, along with their position. This is how search engines can quickly find all documents containing a specific word without scanning every file.
• Test Corpus: A standard collection of documents (e.g., a specific book or set of books) used to evaluate and compare the effectiveness of different IR models.
• The Probabilistic Model: This model computes a similarity coefficient between a query and each document. It estimates the probability that a document will be relevant to a given query. It is a core statistical approach for ranking results.

🔑 Definition — Probabilistic Model: A model that computes the similarity coefficient between queries and documents as the probability that a document will be relevant to a query.

Search Computing: Books

The lecture uses the example of searching for computing books to illustrate how these models are applied. The process involves taking a user's query, using an inverted index to locate candidate documents (books), and then applying an IR model (like the probabilistic model) to rank these books by their estimated relevance to the user's search terms.

⭐ Key Takeaways

• Information Retrieval is fundamentally about searching semi-structured and unstructured data, which is a different problem from searching structured databases.
• The inverted index is the core data structure enabling fast search in large document collections, acting as a lookup table from words to documents.
• The probabilistic model is a classic approach to ranking, which estimates the likelihood of a document being relevant to a user's query.
• Academic research in IR relies on test corpora to objectively evaluate and compare the performance of different search algorithms.
• The lecture contrasts the limitations of traditional library catalogs (metadata search) with the power of modern search engines (full-text content search).

🧠 Quick Revision Questions

1. What is the fundamental difference between searching a structured database (like a library management system) and searching unstructured text?
2. Explain the purpose of an inverted index in Information Retrieval.
3. How does the probabilistic model determine which documents are more relevant to a query?
4. What is a "test corpus" and why is it important in the context of evaluating IR models?
5. Give an example of "semi-structured data" vs. "unstructured data" as mentioned in the lecture context.

📘 Lecture 2 — Information Retrieval Techniques

📖 Overview: This lecture introduces the fundamental concepts of Information Retrieval (IR) , exploring its definitions, core models, and the foundational Boolean Retrieval Model. It explains how IR systems represent, store, and organize unstructured information to satisfy user information needs, focusing on the Boolean model's mechanics, query processing, and its pros and cons.

🗂️ Topics Covered

The lecture begins by defining Information Retrieval from multiple perspectives and discussing the general concept of IR models, including their components and ranking functions. It then differentiates between Ad Hoc retrieval and Filtering tasks. The core of the lecture is dedicated to the Boolean Retrieval Model, explaining its binary weighting scheme, query evaluation (including posting list intersection and query optimization), and concludes with a discussion of its advantages and significant drawbacks, such as its lack of document ranking.

📝 Lecture Summary

What is Information Retrieval?

Information Retrieval (IR) is the field concerned with the representation, storage, organization of, and access to information items. It aims to find relevant material, typically unstructured text documents, that satisfy an information need from within large collections stored on computers. IR is about finding relevant documents, not just simple pattern matches.

IR Models

Modeling in IR is a complex process aimed at producing a ranking function, which assigns scores to documents with regard to a given query. An IR model is formally defined as a quadruple [D, Q, F, R(qi, dj)]:

1. D: A set of logical views for the documents.
2. Q: A set of logical views for the user queries.
3. F: A framework for modeling documents and queries.
4. R(qi, dj): A ranking function.

There are two main retrieval tasks: Ad Hoc Retrieval, where a user submits a new query to a relatively static collection; and Filtering, where a user has a long-term information need and is notified of new documents matching a profile.

The Boolean Model

The Boolean retrieval model is a simple model based on set theory and Boolean algebra. In this model, the significance of an index term for a document is represented by a binary weight (Wkj ∈ {0,1}), indicating the presence (1) or absence (0) of a term in a document. Queries are expressed as Boolean expressions using the operators AND, OR, and NOT (e.g., "Brutus AND Caesar but NOT Calpurnia").

🔑 Definition — Boolean Model: A retrieval model where documents are represented as binary vectors of index terms, and queries are Boolean expressions. A document is considered relevant if its set of terms satisfies the query's logical conditions.

📐 Formula: The ranking function R(qi, dj) returns a binary similarity score of 0 or 1. The query q = tₐ ∧ t_b retrieves the intersection of the posting lists for tₐ and t_b: R(q, dⱼ) = 1 if the document vector satisfies the Boolean expression, else 0.

📌 Example: Given three documents d₁ = [1,1,1]ᵀ, d₂ = [1,0,0]ᵀ, d₃ = [0,1,0]ᵀ for terms (t₁, t₂, t₃), the postings are R_t₁ = {d₁, d₂}, R_t₂ = {d₁, d₃}, R_t₃ = {d₁}. For the query q = t₁ ∧ t₂, we intersect R_t₁ and R_t₂: {d₁, d₂} ∩ {d₁, d₃} = {d₁}. Only document d₁ is considered relevant. The merge operation on sorted posting lists takes O(x+y) operations, where x and y are the list lengths.

Query Optimization

Query optimization is the process of selecting how to organize the work of answering a query with the goal of minimizing the total amount of work. This often involves evaluating the query in a different order to reduce the size of intermediate results.

📌 Example: Given t₁ = {d₁, d₃, d₅, d₇}, t₂ = {d₂, d₃, d₄, d₅, d₆}, t₃ = {d₄, d₆, d₈}, and query q = t₁ AND t₂ OR t₃:

• Left-first evaluation: (t₁ AND t₂) = {d₃, d₅} → {d₃, d₅} OR t₃ = {d₃, d₅, d₄, d₆, d₈} (5 documents)
• Right-first evaluation: (t₂ OR t₃) = {d₂, d₃, d₄, d₅, d₆, d₈} → {d₂, d₃, d₄, d₅, d₆, d₈} AND t₁ = {d₃, d₅} (2 documents) The standard evaluation priority is: AND, NOT, then OR.

Considerations on the Boolean Model

The Boolean Model is a data retrieval model rather than an information retrieval model because it uses a binary decision criterion (relevant or not) with no notion of a grading scale or partial matching.

Pros:

• Boolean expressions have precise semantics.
• Allows for structured queries.
• Intuitive for expert users.
• Simple and neat formalism.

Drawbacks:

• Retrieval is based on binary decision criteria with no notion of partial matching.
• No ranking of documents is provided (absence of a grading scale).
• Users find it awkward to translate an information need into a Boolean expression.
• User queries are often too simplistic.
• The model frequently returns either too few or too many documents.

⭐ Key Takeaways

This lecture establishes that Information Retrieval is about finding relevant documents from large, unstructured collections. The Boolean Retrieval model is the simplest IR model, using binary term weights and Boolean algebra; this means a document is either retrieved or not with no ranking. While it offers precise semantics, its major failing is the lack of partial matching and ranking, often producing results that are "too few or too many". You must understand how to evaluate Boolean queries using logical operators and intersection of sorted posting lists, and the principle of query optimization to minimize computational work. The Boolean model is more of a data retrieval than an information retrieval model due to its all-or-nothing approach.

🧠 Quick Revision Questions

1. What is the fundamental difference between the goal of Information Retrieval and simple pattern matching?
2. What are the four components of an IR model (the quadruple)?
3. In the Boolean Model, what does a binary weight of '0' and '1' for an index term represent?
4. A search system counts all documents in an inverted list for "cat" and all documents in the list for "dog", then adds the two sets together. Is this most likely the AND or OR operation?
5. Why is the Boolean Model considered more of a "data" retrieval than an "information" retrieval model?

📘 Lecture 3 — Boolean Retrieval Model & Rank Retrieval Model

📖 Overview: This lecture introduces two fundamental information retrieval models: the Boolean Retrieval Model, which uses exact set-based matching with AND/OR/NOT operators, and the Ranked Retrieval Model, which scores and orders documents by relevance. Understanding both models is critical for comparing how professional search systems (like Westlaw) and modern web search engines work.

🗂️ Topics Covered

The lecture covers the Boolean Retrieval Model including its definition, set-based document representation, Boolean queries with AND/OR/NOT operators, and its commercial application in Westlaw. It then examines the problems with Boolean search (feast or famine) and transitions to Ranked Retrieval Models, which use free text queries and scoring to produce ordered result sets without overwhelming users.

📝 Lecture Summary

Boolean Retrieval Model

The Boolean Retrieval Model views each document as a set of terms (unique words), not a bag (which allows duplicates). For example, documents D1 = {This is a pen} and D2 = {It is a pen} produce the set {This, It, is, a, pen}, where order and duplicates are irrelevant. A set is like {a, b, c} = {b, a, c}, while a bag is like {a, a, b, c}.

🔑 Definition — Boolean queries: Queries that use AND, OR, and NOT to join query terms. The model is precise: each document either matches the condition or not.

📐 Model: Set membership → Document either contains the term(s) or does not.

📌 Example: Query "pen AND (this OR it)" would return both D1 and D2 because each contains "pen" and at least one of "this" or "it".

The Boolean model was the primary commercial retrieval tool for 3 decades. Many professional searchers (e.g., lawyers) still prefer Boolean queries because you know exactly what you are getting. Many search systems you use are also Boolean: spotlight, email, intranet, etc.

Information Retrieval Ingredients

The three key ingredients for any information retrieval system are:

1. Documents representation — how documents are modeled (e.g., as sets of terms)
2. Query formulation — how users express their information need
3. Query processing — how the system matches queries to documents

Westlaw

Westlaw is the largest commercial legal search service in terms of the number of paying subscribers, with over half a million subscribers performing millions of searches a day over tens of terabytes of text data. The service started in 1975. In 2005, Boolean search (called "Terms and Connectors" by Westlaw) was still the default, used by a large percentage of users, although ranked retrieval has been available since 1992.

📌 Example queries:

• Information need: Legal theories on preventing disclosure of trade secrets by former employees of a competing company → Query: "trade secret" /s disclos! /s prevent /s employe!
• Information need: Requirements for disabled people to access a workplace → Query: disab! /p access! /s work-site work-place (employment /3 place)
• Information need: Cases about a host's responsibility for drunk guests → Query: host! /p (responsib! liab!) /p (intoxicat! drunk!) /p guest

Problem with Boolean search: feast or famine

Boolean queries have a significant feast or famine problem. They require query writing skills, and often result in either too few (=0) or too many (1000s) results. It takes a lot of skill to come up with a query that produces a manageable number of hits. AND gives too few; OR gives too many.

Ranked retrieval models

In ranked retrieval, rather than a set of documents satisfying a query expression, the system returns an ordering over the (top) documents in the collection for a query. Free text queries use one or more words in a human language, rather than a query language of operators and expressions.

💡 Why this matters: Ranked retrieval solves the feast or famine problem because large result sets are not an issue — we just show the top k (≈10) results and don't overwhelm the user, assuming the ranking algorithm works.

Scoring as the basis of ranked retrieval

We wish to return in order the documents most likely to be useful to the searcher. To rank-order documents, we assign a score — say in [0, 1] — to each document. This score measures how well the document and query "match".

⭐ Key Takeaways

The Boolean Retrieval Model treats documents as term sets and uses exact Boolean logic (AND/OR/NOT), which is precise but suffers from feast or famine — either too few or too many results. Westlaw demonstrates successful commercial Boolean search in legal applications, but it requires significant query writing skill. The Ranked Retrieval Model overcomes this by assigning a relevance score to each document and returning a ranked list of top results, typically with free text queries. This scoring-based approach is the foundation of modern web search engines, eliminating the need for users to construct complex Boolean expressions.

🧠 Quick Revision Questions

1. What is the fundamental difference between a "set" and a "bag" in document representation? Give an example.
2. What does the Boolean query "trade secret" /s disclos! /s prevent /s employe! mean in Westlaw, and what information need does it address?
3. Describe the "feast or famine" problem in Boolean retrieval and explain why ranked retrieval avoids it.
4. How does a ranked retrieval model determine which documents to show to the user? What role does "scoring" play?
5. What were the three key ingredients of an information retrieval system mentioned in the lecture?

📘 Lecture 4 — Vector Space Retrieval Model

📖 Overview: This lecture introduces the Vector Space Retrieval Model, a fundamental approach in information retrieval that represents documents and queries as vectors in a term space. It explains how term weighting schemes, particularly tf-idf, are used to compute document-query similarity scores, enabling ranked retrieval that is more precise than Boolean models.

🗂️ Topics Covered

The lecture covers the Vector Model's core concepts, including binary term-document incidence matrices and term-document count matrices, the bag of words model, term frequency (tf) with log-frequency weighting and normalization techniques, document frequency and its relationship to term informativeness, idf (inverse document frequency), and finally the tf-idf weighting scheme.

📝 Lecture Summary

The Vector Model (Salton, 1968)

The Vector Space Model represents documents and queries as vectors in the term space. Term weights are used to compute the degree of similarity (or score) between each document stored in the system and the user query. By sorting in decreasing order of this degree of similarity, the vector model takes into consideration documents which match the query terms only partially. This ranked document answer set is a lot more precise (in the sense that it better matches the user information need) than the document answer set retrieved by the Boolean model. A measure of the similarity between the two vectors is then computed, and documents whose content (terms in the document) correspond most closely to the content of the query are judged to be the most relevant.

Binary term-document incidence matrix

In this representation, each document is represented by a binary vector ∈ {0,1}^|V|, where 1 indicates the presence of a term and 0 indicates its absence. The lecture presents a table showing binary incidence for terms (Antony, Brutus, Caesar, Calpurnia, Cleopatra, mercy, worser) across documents (Antony and Cleopatra, Julius Caesar, The Tempest, Hamlet, Othello, Macbeth).

Term-document count matrices

Instead of just presence/absence, the count matrix considers the number of occurrences of a term in a document. Each document is a count vector in ℕ^V (a column below). The lecture provides an example table showing actual counts, e.g., "Antony" appears 157 times in "Antony and Cleopatra", 73 times in "Julius Caesar", etc.

Bag of words model

The vector representation doesn't consider the ordering of words in a document. For example, "John is quicker than Mary" and "Mary is quicker than John" have the same vectors. This is called the bag of words model. In a sense, this is a step back: The positional index is required to distinguish these two documents. The course will look at "recovering" positional information later.

Term frequency tf

The term frequency tf_t,d of term t in document d is defined as the number of times that t occurs in d. Raw term frequency is not what we want: a document with 10 occurrences of the term is more relevant than a document with 1 occurrence, but not 10 times more relevant. Relevance does not increase proportionally with term frequency.

🔑 Definition — Term Frequency (tf): The number of times a term occurs in a document.

📐 Formula (Log-frequency weighting): The log frequency weight of term t in d is:

w_t,d = { 1 + log10(tf_t,d), if tf_t,d > 0; 0, otherwise }

→ Plain-English meaning: 0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, etc. This reduces the impact of very high term frequencies.

📌 Example: If a term appears 10 times in a document, its log-frequency weight would be 1 + log10(10) = 1 + 1 = 2. If it appears 1000 times, the weight would be 1 + log10(1000) = 1 + 3 = 4.

Term Frequency Normalization

We can use another normalization method for tf: Find the term frequencies of all terms in a document, find out the maximum tf_max from all those terms, then the tf of term 'i' referred to as tf_i is obtained by dividing the tf_i by tf_max: tf_i = tf_i / tf_max. This brings the term frequencies of each term in a document between 1 and 0, irrespective of the size of a document.

Document frequency

Rare terms are more informative than frequent terms. Consider a term in the query that is rare in the collection (e.g., "arachnocentric") — a document containing this term is very likely to be relevant to the query. We want a high weight for rare terms like "arachnocentric". Conversely, frequent terms are less informative than rare terms — consider a query term that is frequent in the collection (e.g., "high", "increase", "line") — while a document containing such a term is more likely to be relevant than one that doesn't, it's not a sure indicator of relevance. For frequent terms, we want high positive weights but lower than for rare terms.

💡 Why this matters: Document frequency (df) captures how common or rare a term is across the entire collection, helping distinguish informative terms from common ones.

idf example, suppose N = 1 million

The inverse document frequency (idf) formula is:

idf_t = log10(N / df_t)

where N is the total number of documents and df_t is the document frequency of term t.

📐 Formula: idf_t = log10(N / df_t) → Plain-English meaning: Terms that appear in fewer documents get higher idf values.

📌 Example (with N = 1 million):

• "calpurnia": df = 1, idf = 6
• "animal": df = 100, idf = 4
• "sunday": df = 1,000, idf = 3
• "fly": df = 10,000, idf = 2
• "under": df = 100,000, idf = 1
• "the": df = 1,000,000, idf = 0

There is one idf value for each term t in a collection.

tf-idf weighting

The tf-idf weight of a term is the product of its tf weight and its idf weight:

w_t,d = (1 + log10(tf_t,d)) × log10(N / df_t)

🔑 Definition — tf-idf: A term weighting scheme that is the product of term frequency and inverse document frequency.

📐 Formula: w_t,d = (1 + log10(tf_t,d)) × log10(N / df_t) → Plain-English meaning: The weight of a term in a document increases with the number of occurrences within that document and increases with the rarity of the term across the collection.

This is the best known weighting scheme in information retrieval. Note: the "-" in tf-idf is a hyphen, not a minus sign. Alternative names include tf.idf, tf x idf.

⭐ Key Takeaways

The Vector Space Model represents documents and queries as vectors in term space, using the bag of words approach that ignores word order. Term frequency (tf) measures how often a term appears in a document, but raw counts are log-transformed because relevance doesn't increase linearly with frequency. Document frequency (df) captures how common a term is across the collection, with rare terms being more informative (higher idf values). The tf-idf weighting scheme combines both factors — it gives high weight to terms that appear frequently in a document but rarely in the collection. Students must remember the log-frequency weighting formula, the idf calculation, and the final tf-idf product formula, as these are fundamental to ranked retrieval.

🧠 Quick Revision Questions

1. What is the bag of words model, and what information does it deliberately ignore?
2. Why is raw term frequency not a good measure of relevance, and how does log-frequency weighting address this?
3. How is term frequency normalization performed using tf_max?
4. Calculate the idf value for a term with df = 250 in a collection of N = 50,000 documents.
5. Write the complete tf-idf formula and explain what each component represents in plain English.

📘 Lecture 5 — Information Retrieval Techniques

📖 Overview: This lecture dives into the core of modern information retrieval: how to transform text documents and user queries into weighted numerical vectors and compute their similarity. It focuses on the TF-IDF weighting scheme, vector space representation, and key similarity measures like the Jaccard coefficient and inner product, which are fundamental for ranking search results.

🗂️ Topics Covered

The lecture covers computing TF-IDF with a worked example, mapping documents and queries to vectors in a high-dimensional space, understanding term weight coefficients, and comparing two similarity measures: the Jaccard coefficient and the inner product (dot product), including its normalized form.

📝 Lecture Summary

Computing TF-IDF -- An Example

The lecture provides a step-by-step example of calculating TF-IDF weights for terms in a document. Given a document with terms A, B, C and their frequencies, and their document frequencies across a collection of 10,000 documents, we calculate each component. The term frequency (tf) is normalized by the maximum frequency in the document, and the inverse document frequency (idf) is the log of the ratio of total documents to the number of documents containing the term. The final tf-idf weight is the product of these two values, giving high weight to terms that are frequent in a specific document but rare across the collection.

🔑 Definition — Term Frequency (tf): A measure of how frequently a term occurs in a document. It is often normalized (e.g., by dividing by the maximum frequency of any term in the document) to prevent bias towards longer documents. 🔑 Definition — Inverse Document Frequency (idf): A measure of how much information a term provides, i.e., whether it is common or rare across all documents. It is calculated as log(N/df), where N is the total number of documents and df is the number of documents containing the term. 📐 Formula: tf-idf = tf * idf where tf = term frequency in document / max term frequency in document and idf = log₂(N / document frequency of term). → This weights terms by how descriptive they are of a specific document. 📌 Example: For a document with terms A(3), B(2), C(1) in a collection of 10,000 documents where A appears in 50, B in 1300, and C in 250:

• A: tf = 3/3 = 1; idf = log₂(10000/50) ≈ 7.6; tf-idf = 7.6
• B: tf = 2/3 ≈ 0.67; idf = log₂(10000/1300) ≈ 2.9; tf-idf ≈ 2.0
• C: tf = 1/3 ≈ 0.33; idf = log₂(10000/250) ≈ 5.3; tf-idf ≈ 1.8 💡 Why this matters: This example shows how a rare term (A, appearing in only 50 documents) gets a much higher tf-idf weight than a common term (B), making it more influential in identifying the document's topic.

Binary → count → weight matrix

The lecture illustrates the transformation of a document-term matrix from a binary representation (1 if a term is present, 0 if not), to a count matrix (raw term frequencies), and finally to a weight matrix (with tf-idf values). For example, in the binary matrix, 'Antony' has a 1 in 'Antony and Cleopatra' and 'Julius Caesar', but 0 in others. In the count matrix, its frequency is 157 in one and 73 in another. In the final weighted matrix, the tf-idf weight for 'Antony' in 'Antony and Cleopatra' is 5.25, and in 'Julius Caesar' is 3.18. This progression shows how raw data is refined into meaningful importance scores.

🔑 Definition — Document-Term Matrix: A matrix where rows represent terms, columns represent documents, and each cell contains a weight (binary, count, or tf-idf) indicating the term's importance in that document.

Mapping to vectors

The concept of mapping documents and queries to a vector space is introduced. Each unique term in the collection defines an axis in this high-dimensional space, making the vectors for the terms themselves the canonical basis vectors. A document is represented as a vector, which is the sum of the vectors (weighted by their tf-idf scores) of all the terms it contains. A query is treated in the exact same way: it is mapped to a vector in the same space using the same weighting scheme. This allows the system to mathematically compare the query with every document.

🔑 Definition — Vector Space Model: An algebraic model for representing text documents (and queries) as vectors of identifiers, such as index terms. Similarity between documents and a query is assessed by the proximity of their vectors. 💡 Why this matters: This mapping is the core transformation that enables mathematical calculation of similarity, moving from raw text to a numerical representation.

Coefficients

The lecture discusses how the coefficients (the weights or values along each dimension of the vector) represent a term's presence, importance, or "aboutness". The model itself gives no guidance on how to set these weights, so several common choices exist:

• Binary: A simple 1 if the term is present in the document, 0 if not.
• tf (Term Frequency): The raw frequency of the term in the document.
• tf·idf: The product of term frequency and inverse document frequency, which is the most common and effective choice as it accounts for both local and global importance.

Query Vector

The query vector is treated the same as a document vector and is typically tf-idf weighted. An alternative approach is for the user to manually supply weights for the query terms, but the standard approach is to compute them automatically.

Similarity Measure

A similarity measure is a function that computes the degree of similarity between two vectors (e.g., query vector and document vector). It is crucial for ranking: the system can rank retrieved documents in order of presumed relevance based on their similarity score and can also enforce a threshold to control the size of the retrieved set.

🔑 Definition — Similarity Measure: A function that computes a score representing the degree of similarity between two vectors.

Jaccard coefficient

The Jaccard coefficient is a commonly used measure for the overlap of two sets A and B. 📐 Formula: Jaccard(A, B) = |A ∩ B| / |A ∪ B| This score always falls between 0 and 1.

• Jaccard(A, A) = 1 (a set is perfectly similar to itself).
• Jaccard(A, B) = 0 if the sets have no intersection (A ∩ B = 0).
• The sets don't have to be the same size.

Issues with Jaccard for scoring

The lecture points out critical issues with using the Jaccard coefficient for document scoring:

• It does not consider term frequency (tf) — it only checks if a term is present or absent.
• It does not account for the informativeness of rare terms (idf). Jaccard treats all terms equally.
• It lacks a sophisticated method for length normalization. Instead of the Jaccard formula, a more advanced normalization technique is needed, leading to the inner product measure.

Similarity Measure - Inner Product

The inner product (or dot product) is a more sophisticated similarity measure for vectors. 📐 Formula: sim(dⱼ, q) = dⱼ • q = ∑ wᵢⱼ * wᵢq (where wᵢⱼ is the weight of term i in document j, and wᵢq is the weight of term i in the query).

• For binary vectors, the inner product is simply the number of query terms that match in the document (the size of the intersection).
• For weighted term vectors (like tf-idf), it is the sum of the products of the weights of the matched terms.
• The lecture also mentions "Similarity, Normalized", implying the use of the cosine similarity (the normalized version of the inner product) to account for document length, though the formula is not fully detailed in this text.

⭐ Key Takeaways

The most critical concepts from this lecture are the TF-IDF weighting scheme, which balances term frequency with inverse document frequency to give high weights to distinctive terms. You must understand how to map documents and queries into a vector space, where each unique term is a dimension. The inner product (dot product) is the preferred similarity measure over the simpler Jaccard coefficient because it incorporates non-binary weights (like tf-idf), unlike Jaccard which only handles set membership. Finally, remember the progression from binary to count to weight matrices as a fundamental data preparation step for using these mathematical models.

🧠 Quick Revision Questions

1. In the TF-IDF example, why did term A (with 3 occurrences) receive a higher tf-idf weight (7.6) than term B (with 2 occurrences and a weight of 2.0)?
2. What are the three stages of a document-term matrix transformation discussed in the lecture, and what does each stage represent about a term in a document?
3. Explain the fundamental difference between the Jaccard coefficient and the Inner Product when used as a similarity measure for weighted document vectors.
4. Why is the "Jaccard coefficient" considered insufficient for scoring documents in a modern IR system, specifically regarding term frequency and term informativeness?
5. How is a query represented in the "Vector Space Model," and is its weighting scheme typically the same as or different from a document's?

📘 Lecture 6 — Similarity Measures and Cosine Similarity Measure

📖 Overview: This lecture explores how documents and queries are compared in vector space retrieval, focusing on the cosine similarity measure as the primary similarity metric. It also covers the basic indexing pipeline, the challenge of sparse vectors, and how inverted indexes efficiently store and retrieve document-term information in information retrieval systems.

🗂️ Topics Covered

The lecture covers cosine similarity as the most common similarity measure for comparing vectors in vector space retrieval, along with its advantages (partial matching, ranked results) and disadvantages (term independence assumption, lack of model justification). It then discusses the basic indexing pipeline, the nature of sparse vectors with very large vocabularies, and three methods for storing sparse vectors (as lists, trees, or hash tables). Finally, it introduces the inverted index as the practical, efficient implementation for document-term storage.

📝 Lecture Summary

Cosine Similarity Measure

The cosine similarity measure is the most frequently used similarity metric in the standard vector space retrieval model. In this model, each dimension corresponds to a term in the vocabulary, and vector elements are real-valued numbers reflecting term importance. Any vector — whether representing a document, query, or other object — can be compared to any other vector using cosine correlation. This approach provides partial matching (documents need not contain all query terms) and ranked results (documents are ordered by similarity score).

🔑 Definition — Cosine Similarity: A metric that measures the cosine of the angle between two vectors, indicating how similar they are. It equals the dot product of the vectors divided by the product of their magnitudes.

📐 Formula: cos(θ) = (A·B) / (||A|| × ||B||) → This computes the cosine of the angle between vectors A and B, where A·B is the dot product and ||A|| and ||B|| are the Euclidean lengths (magnitudes) of the vectors.

📌 Example: If document vector A = [1, 0, 2] and query vector B = [0, 1, 1], then A·B = (1×0) + (0×1) + (2×1) = 2, ||A|| = √(1² + 0² + 2²) = √5 ≈ 2.236, ||B|| = √(0² + 1² + 1²) = √2 ≈ 1.414, so cos(θ) = 2 / (2.236 × 1.414) = 2 / 3.162 ≈ 0.632.

Vector Space Model: Disadvantages

Despite its widespread use, the vector space model has several significant disadvantages. It assumes independence among terms, meaning it treats each term as unrelated to others — though this is a common assumption in retrieval models. There is a lack of justification for some vector operations, such as the choice of similarity function (e.g., why cosine and not another metric) and the choice of term weights (e.g., why certain weighting schemes are used). The model is barely a retrieval model because it does not explicitly model relevance, a person's information need, or language models. Additionally, it assumes a symmetric treatment of queries and documents, treating them as interchangeable, which may not reflect real retrieval scenarios.

💡 Why this matters: Understanding these limitations helps you recognize when vector space retrieval might fail — for example, when term relationships are important (e.g., synonyms like "car" and "automobile" are treated as independent) or when relevance is not simply about term overlap.

Basic Indexing Pipeline

The basic indexing pipeline is the process by which documents are converted from raw text into a structured, searchable index. This pipeline typically involves steps such as tokenization (breaking text into words), normalization (e.g., lowercasing), and building term-document mappings. The pipeline prepares documents for vector space representation and subsequent similarity calculations.

Sparse Vectors

Sparse vectors arise because the vocabulary (and therefore the dimensionality of vectors) in information retrieval can be very large — approximately 10⁴ or more terms. However, most documents and queries do not contain most words, so vectors are sparse, meaning most entries are 0. Efficient methods are needed for storing and computing with sparse vectors to avoid wasting memory and computation time.

🔑 Definition — Sparse Vector: A vector in which most elements are zero, common in IR because documents typically contain only a small subset of the total vocabulary.

Sparse Vectors as Lists

One method for storing sparse vectors is to use linked lists of non-zero-weight tokens paired with their weights. The space required is proportional to the number of unique tokens (n) in the document. However, this method requires linear search of the list to find or change the weight of a specific token, and in the worst case, it requires quadratic time — O(n²) — to compute a vector for a document, because the sum of 1 to n equals n(n+1)/2, which is O(n²).

🔑 Definition — O(n²) Quadratic Time: The time grows quadratically with the number of tokens; for n=1000 tokens, about 500,000 operations may be needed.

📐 Formula: ∑(i=1 to n) i = n(n+1)/2 = O(n²) → This shows that constructing a vector using a list requires summing from 1 to n, resulting in quadratic time complexity.

Sparse Vectors as Trees

An alternative is to index tokens in a document using a balanced binary tree or trie, with weights stored at the leaves. The space overhead for the tree structure is approximately 2n nodes. This approach provides O(log n) time to find or update the weight of a specific token, and O(n log n) time to construct the entire vector. However, it requires a software package to support such data structures, which may not be readily available.

Sparse Vectors as Hash Tables

A more efficient approach is to store tokens in a hash table, using the token string as the key and the weight as the value. The storage overhead for a hash table is approximately 1.5n. The table must fit in main memory for optimal performance. This method provides constant time (O(1)) to find or update the weight of a specific token (ignoring collisions), and O(n) time to construct the vector (again ignoring collisions).

Implementation Based on Inverted Files

In practice, document vectors are not stored directly; instead, an inverted organization provides much better efficiency. The keyword-to-document index (inverted index) can be implemented as a hash table, a sorted array, or a tree-based data structure (trie, B-tree). The critical issue is achieving logarithmic or constant-time access to token information, which these structures provide.

🔑 Definition — Inverted Index: A data structure that maps each term (keyword) to a list of documents containing that term, along with positions or weights, enabling fast retrieval of documents matching query terms.

Inverted Index

The inverted index is the standard implementation for storing document-term information in information retrieval systems. Instead of storing vectors per document (forward index), the inverted index stores for each term a list of documents in which that term appears. This structure supports efficient query processing by quickly identifying which documents contain query terms, rather than scanning all document vectors.

⭐ Key Takeaways

The most critical concept from this lecture is that cosine similarity is the primary metric for comparing documents and queries in vector space retrieval, providing ranked, partial matching results despite its limitations like term independence and lack of relevance modeling. Sparse vectors are the norm in IR due to large vocabularies, and efficient storage is crucial — hash tables offer O(1) access and O(n) construction, making them faster than lists (O(n²)) or trees (O(n log n)). The inverted index is the practical, real-world implementation that reverses the document-term mapping, allowing logarithmic or constant-time access to term information rather than storing vectors per document. For exams, remember that cosine similarity measures the angle between vectors (not distance), that sparse vectors necessitate efficient data structures, and that the inverted index is the industry standard for large-scale retrieval systems.

🧠 Quick Revision Questions

1. What is the formula for cosine similarity, and what do each of its components represent?
2. List three disadvantages of the vector space model and explain why each is a problem.
3. Compare the time complexities for constructing a vector using lists, trees, and hash tables — which is fastest and why?
4. What is an inverted index, and how does it differ from storing document vectors directly?
5. Why are vectors in information retrieval described as "sparse"? Give an approximate value for vocabulary size.

📘 Lecture 7 — Parsing Documents

📖 Overview: This lecture covers the fundamental techniques for building and using inverted indexes in information retrieval systems. It explains how to efficiently store and compute with sparse document vectors, create inverted indexes, compute cosine similarity, and understand the time complexity of indexing and retrieval operations.

🗂️ Topics Covered

The lecture covers the basic indexing pipeline, sparse vector representations (lists, trees, hashtables), inverted index creation and implementation, computing IDF and document vector lengths, time complexity analysis of indexing, and retrieval with inverted indexes including query efficiency.

📝 Lecture Summary

Basic indexing pipeline

The basic indexing pipeline involves processing documents to create a searchable index. Documents are first parsed to extract tokens, then a sparse vector representation is created where most entries are zero since documents typically contain only a small subset of the total vocabulary. The vocabulary and dimensionality of vectors can be very large (up to 10⁴), so efficient storage methods are needed.

🔑 Definition — Sparse Vector: A vector where most entries are zero, representing document-term weights only for terms that actually appear in the document.

Sparse Vectors as Lists

Linked lists can store vectors as pairs of non-zero-weight tokens paired with their weights. Space is proportional to the number of unique tokens (n) in the document. However, this requires linear search O(n) to find or change the weight of a specific token, and worst-case quadratic time O(n²) to construct the vector.

📐 Formula: O(n²) = n(n+1)/2 ≈ Σᵢ₌₁ⁿ i → The time required grows quadratically with the number of unique tokens.

Sparse Vectors as Trees

Balanced binary trees or tries index tokens with weights stored at the leaves. Space overhead is ~2n nodes (contains data and pointers). This provides O(log n) time to find or update token weights and O(n log n) time to construct the vector, requiring a software package to support such structures.

Sparse Vectors as HashTables

Hash tables store tokens with token string as key and weight as value. Storage overhead is ~1.5n, and the table must fit in main memory. This provides constant time O(1) to find or update token weights (ignoring collisions) and O(n) time to construct the vector.

💡 Why this matters: Hash tables offer the best performance trade-off for in-memory document indexing, but the table must fit entirely in RAM.

Implementation Based on Inverted Files

In practice, document vectors are not stored directly; an inverted organization provides much better efficiency. The keyword-to-document index can be implemented as a hash table, sorted array, or tree-based data structure (trie, B-tree). The critical issue is logarithmic or constant-time access to token information.

Inverted Index

An inverted index maps each token to a list of documents containing that token. Creating one involves:

1. Create empty HashMap H
2. For each document D: create HashMapVector V, then for each token T in V: if T not in H, create TokenInfo for T and insert it; create TokenOccurrence for T in D and add it to T's occurrence list
3. Compute IDF for all tokens
4. Compute vector lengths for all documents

🔑 Definition — TokenOccurrence: A record indicating a token's occurrence in a specific document, containing the term frequency and document reference.

Computing IDF

Let N be the total number of documents. For each token T: determine M (number of documents where T occurs, i.e., length of T's occurrence list). The IDF for T is log(N/M). This requires a second pass through all tokens after all documents have been indexed.

📐 Formula: IDF(T) = log(N/M) → Inverse Document Frequency measures how rare or common a term is across the entire document collection.

Cosine Similarity Measure

The document vector length is the square root of the sum of squares of token weights. The weight of a token is TF × IDF. Document lengths cannot be determined until IDFs are known (after all documents are indexed).

📐 Formula: Document length = √(Σ (I × C)²) where I = IDF of token T and C = count of T in document D.

Computing Document Lengths

1. Initialize all document vector lengths to 0.0
2. For each token T: let I be its IDF; for each TokenOccurrence of T in document D: let C be the count of T in D; increment D's length by (I × C)²
3. After processing all tokens, set each document's length to the square root of its accumulated value

Time Complexity of Indexing

• Creating a vector and indexing a document with n tokens: O(n)
• Indexing m documents: O(m × n)
• Computing token IDFs for vocabulary V: O(|V|)
• Computing vector lengths: O(m × n)
• Since |V| ≤ m × n, complete process is O(m × n) — same complexity as reading in the corpus

Retrieval with an Inverted Index

Tokens not present in both query and document do not affect cosine similarity because their weight product is zero and doesn't contribute to the dot product. Since queries are typically short with extremely sparse vectors, the inverted index is used to find only the limited set of documents containing at least one query word.

💡 Why this matters: The inverted index dramatically reduces computation by only considering documents that contain query terms, avoiding the need to scan all documents.

Inverted Query Retrieval Efficiency

The retrieval process:

1. Prompt user for query Q
2. Compute ranked array of retrievals R for Q
3. Print top N documents in R
4. User can:
   • Show next N retrievals
   • Show the Mth retrieved document
5. Continue until user enters empty query

⭐ Key Takeaways

The most critical concepts from this lecture are the three sparse vector implementations (lists O(n²) construction, trees O(n log n), and hashtables O(n) with O(1) lookup), the two-pass process for creating an inverted index where IDF computation requires a second pass after all documents are indexed, and the cosine similarity formula where document vector length = √(Σ(TF × IDF)²). The time complexity of full indexing is O(m × n), and retrieval efficiency comes from using the inverted index to only examine documents containing query terms. Understanding the trade-offs between list, tree, and hashtable implementations is essential for choosing the right data structure.

🧠 Quick Revision Questions

1. What are the three implementations for sparse vectors and their time complexities for construction?
2. Why must IDF computation be done as a second pass after all documents have been indexed?
3. What is the formula for computing document vector length in cosine similarity?
4. How does an inverted index improve retrieval efficiency compared to scanning all documents?
5. What is the overall time complexity of indexing m documents, each with n tokens?

📘 Lecture 8 — Information Retrieval Techniques

📖 Overview: Lecture 8 delves into the foundational steps of the indexing pipeline, focusing on how raw documents are parsed and tokenized into searchable units. It explains the critical handling of numbers, the rationale behind stop words, and the complexities introduced by different document formats, languages, and character sets. Understanding these processes is essential for building any effective information retrieval system.

🗂️ Topics Covered

The lecture begins by explaining the basic indexing pipeline and the process of parsing a document to determine its format, language, and character set. It then discusses complications arising from multi-language documents and the challenge of defining what constitutes a single "document" for indexing. The core topics of tokenization are introduced, including issues with punctuation like apostrophes and hyphens, followed by specific considerations for indexing numbers. The lecture concludes by examining language-specific tokenization challenges (French, German, Chinese, Japanese, Arabic) and the function and modern usage of stop words.

📝 Lecture Summary

Parsing a Document

The first step in the indexing pipeline is to parse the document. This involves identifying its format (e.g., PDF, Word, Excel, HTML), its language (e.g., English, French), and the character set in use (e.g., CP1252, UTF-8). This initial identification is necessary for the correct extraction of text.

💡 Why this matters: A system cannot index a PDF the same way as a Word document, and it cannot process UTF-8 text as if it were ASCII without causing errors.

Complications: Format/Language

Documents being indexed can include content from many different languages, and a single index may contain terms from many languages. A document or its components can contain multiple languages or formats, such as a French email with a German PDF attachment or a French email quoting clauses from an English-language contract. There are commercial and open-source libraries that can handle much of this complexity.

Complications: What is a Document?

When a query is issued returning "documents," there are often interesting questions of grain size: What is a unit document? Is it a single file? An email (perhaps one of many in a single mbox file)? An email with five attachments? A group of files (e.g., a PPT presentation or LaTeX document split over HTML pages)? These tasks are often done heuristically.

Precision and Recall

Precision and recall are two key measures for evaluating the effectiveness of an information retrieval system. Precision measures the proportion of retrieved documents that are relevant (i.e., how many results are correct). Recall measures the proportion of relevant documents that are retrieved (i.e., how many of the correct results you've found).

Tokenization

The input text (e.g., “Friends, Romans and Countrymen”) is processed to output tokens (e.g., Friends, Romans, Countrymen). A token is an instance of a sequence of characters. Each such token is now a candidate for an index entry, after further processing.

🔑 Definition — Token: An instance of a sequence of characters in a particular document that is grouped together as a useful semantic unit for processing.

Issues in tokenization include handling:

• Apostrophes: Finland's capital could become Finland AND s, Finlands, or Finland's.
• Hyphens: Hewlett-Packard could be one token or two (Hewlett and Packard). state-of-the-art could be broken up. co-education vs lowercase, lower-case, lower case.
• Multi-word terms: San Francisco is one token or two? How is it decided?

Numbers

Numbers present their own tokenization challenges, e.g., 3/20/91, Mar. 12, 1991, 55 B.C., B-52, (800) 234-2333. They often have embedded spaces. Older IR systems may not index numbers, but they are often very useful, for example, looking up error codes or stacktraces on the web. One solution is using n-grams. Metadata (creation date, format, etc.) is often indexed separately.

Tokenization: Language Issues

Different languages present unique tokenization issues:

• French: L'ensemble — should it be one token or two (L and ensemble)? The goal is for l'ensemble to match un ensemble.
• German: Noun compounds are not segmented, e.g., Lebensversicherungsgesellschaftsangestellter ('life insurance company employee'). German retrieval systems benefit greatly from a compound splitter module, which can give a 15% performance boost.
• Chinese and Japanese: These languages have no spaces between words, so tokenization is not always guaranteed and unique. Japanese has the further complication of multiple alphabets intermingled.
• Arabic (or Hebrew): These languages are written right to left, but with certain items like numbers written left to right. Words are separated, but letter forms within a word form complex ligatures.

Stop Words

With a stop list, you add the commonest words (e.g., the, a, and, to, be) to a list and exclude them from the dictionary entirely. The intuition is that they have little semantic content and represent a large volume of postings (~30% of postings for the top 30 words).

🔑 Definition — Stop List: A list of common words that are excluded from the index entirely because they are believed to carry little semantic content.

However, the trend is away from doing this because good compression techniques mean the space for including stop words is very small, and good query optimization techniques mean the cost at query time is low. Stop words are needed for phrase queries (“King of Denmark”), various song titles (“Let it be”, “To be or not to be”), and “relational” queries (“flights to London”).

⭐ Key Takeaways

The indexing pipeline begins with parsing a document to determine its format, language, and character set, which introduces complications when dealing with multi-language content. Tokenization is the process of breaking text into individual tokens, but it is fraught with issues related to punctuation (apostrophes, hyphens), multi-word names, and the specific rules of different human languages (e.g., German compounding, Chinese segmentation). While numbers were often ignored in older systems, they are now considered highly valuable for queries like error code lookups. Finally, the modern approach to stop words is to include them rather than exclude them, as they are essential for phrase and relational queries, and efficient compression and optimization techniques make their inclusion inexpensive.

🧠 Quick Revision Questions

1. What are the three primary characteristics of a document that must be identified during the parsing stage before indexing can begin?
2. Give two examples of complexities that arise when tokenizing text that contains apostrophes or hyphens.
3. Explain the main challenge in tokenizing Chinese text that does not exist in English text.
4. What is the classic argument against using a stop list for words like "the" and "a"?
5. Why are numbers like 3/20/91 or (800) 234-2333 considered challenging to tokenize?

📘 Lecture 9 — Terms Normalization

📖 Overview: This lecture focuses on the crucial step of normalizing tokens into standardized terms for effective information retrieval. It explores various normalization techniques, including case folding, handling diacritics, and using thesauri and soundex, to ensure that queries match relevant documents despite variations in word forms, capitalization, and spelling.

🗂️ Topics Covered

The lecture covers normalization of terms for indexing and querying, including case folding to handle capitalization variations, normalization for different languages (accents, umlauts, date forms, character sets), asymmetric expansion as an alternative to equivalence classes, and the use of thesauri for synonyms and soundex for phonetic spelling corrections.

📝 Lecture Summary

Normalization

We may need to “normalize” words in indexed text as well as query words into the same form. We want to match U.S.A. and USA. Tokens are transformed to terms which are then entered into the index. A term is a (normalized) word type, which is an entry in our IR system dictionary. We most commonly implicitly define equivalence classes of terms by deleting periods to form a term (e.g., U.S.A., USA → USA) or deleting hyphens to form a term (e.g., anti-discriminatory, antidiscriminatory → antidiscriminatory).

1. Normalization: other languages

For accents, such as French résumé vs. resume, a simple remedy is to remove the accent, but this is not good in cases like Resume (with and without accent having different meanings) vs. Cliché and Cliche (same meaning). An important consideration is: Are the users going to use accents while writing queries? For umlauts, e.g., German: Tuebingen vs. Tübingen, these should be equivalent. Often, it is best to normalize to a de-accented term (e.g., Tuebingen, Tübingen, Tubingen → Tubingen).

🔑 Definition — Normalization: The process of transforming tokens into a standard form (terms) so that different surface forms of the same word can be matched.

💡 Why this matters: Even in languages that standardly have accents, users often may not type them, so normalization improves recall.

Normalization also applies to things like date forms: e.g., 7月30日 vs. 7/30 (date or mathematical expression). This leads to diversification where 7/30 = 7/30, July 30, 7-30. In Japanese, there are several different character sets, and normalization needs to take care of this fact, resolving queries entered using any char-set. In German, MIT is a word, so the system must differentiate if it refers to the university or the word "with". Tokenization and normalization may depend on the language and is intertwined with language detection. The same method of normalization should be used while indexing as well as while query processing.

2. Case folding

Case folding means reducing all letters to lower case. An exception is upper case in mid-sentence: e.g., General Motors, Fed vs. fed, SAIL vs. sail. It is often best to lower case everything, since users will use lowercase regardless of ‘correct’ capitalization. A word starting with a capital letter in the middle of a sentence is for nouns, so case folding may be given importance in this case. However, if users are not going to use capital letters, then there is no point in improving the index. A longstanding Google example [fixed in 2011] was the query "C.A.T." which returned "#1 result is for 'cats' not Caterpillar Inc."

🔑 Definition — Case folding: The process of converting all letters in a token to a single case (usually lowercase) to create equivalence classes for indexing and querying.

3. Normalization to terms

An alternative to equivalence classing is to do asymmetric expansion. An example: Enter: window → Search: window, windows; Enter: windows → Search: Windows, windows, window; Enter: Windows → Search: Windows. This is potentially more powerful but less efficient. It increases the size of the postings list but gives more control in query processing.

🔑 Definition — Asymmetric expansion: A normalization technique where a query term is expanded to include related forms (e.g., plurals, capitalizations) in an asymmetric way, rather than merging them all into a single equivalence class.

4. Thesauri and soundex

We need to handle synonyms and homonyms. Synonyms are different words with same meanings (e.g., Automobile / Car). Homonyms are same words with different meanings (e.g., Jaguar, Blackberry). For homonyms, postings for all variants are stored against the same index word (term). For synonyms, we can use hand-constructed equivalence classes (e.g., car = automobile, color = colour). We can rewrite to form equivalence-class terms: when a document contains automobile, index it under car-automobile (and vice-versa). Or we can expand a query: when the query contains automobile, look under car as well.

For spelling mistakes (e.g., Chebichev), one approach is Soundex, which forms equivalence classes of words based on phonetic heuristics. It groups words that sound similar into the same equivalence class.

🔑 Definition — Soundex: A phonetic algorithm that indexes words by their pronunciation, forming equivalence classes of words that sound similar, typically used to handle spelling mistakes and variations.

⭐ Key Takeaways

Normalization is critical for matching different surface forms of words, such as "U.S.A." and "USA." Case folding to lowercase is generally recommended, except in special cases like proper nouns. For multilingual contexts, normalization must handle accents, umlauts, date forms, and different character sets. Asymmetric expansion offers more control than simple equivalence classes but is less efficient. Thesauri handle synonyms by creating equivalence classes, while Soundex handles spelling errors by grouping phonetically similar words.

🧠 Quick Revision Questions

1. What is the difference between a token and a term in the context of information retrieval normalization?
2. Give an example of why simple accent removal might be problematic (i.e., two words with and without accent having different meanings).
3. What is the general recommendation for case folding in IR systems, and what is a potential downside?
4. Explain how asymmetric expansion differs from creating equivalence classes for normalization.
5. What problem does the Soundex algorithm solve, and how does it achieve this?

📘 Lecture 10 — Lemmatization

📖 Overview: This lecture covers two core text normalization techniques in information retrieval: lemmatization and stemming. It explains how these methods reduce words to their base or root forms to improve retrieval, and critically evaluates their effectiveness across different languages and applications.

🗂️ Topics Covered

The lecture introduces Lemmatization as a dictionary-based NLP tool that returns the grammatical base form of a word, and Stemming as a crude affix-chopping process that reduces terms to their roots before indexing. It then details Porter’s algorithm, the most common English stemmer, including its conventions, phases, and typical rules. The lecture also discusses other stemmers like Lovins and Paice/Husk, provides a stemming example, addresses language-specificity of these transformations, and concludes with an analysis of whether stemming/lemmatization actually helps retrieval performance.

📝 Lecture Summary

Lemmatization

Lemmatization is an NLP tool that uses dictionaries and morphological analysis of words in order to return the base or dictionary form of a word. It reduces inflectional or variant forms to their base form. For example, “am, are, is” are all reduced to “be”, while “car, cars, car’s, cars’” all become “car”. The sentence “the boy’s cars are different colors” is lemmatized to “the boy car be different color”. Proper nouns like “Pakistan” remain unchanged. Lemmatization implies doing a “proper” reduction to the dictionary headword form. A key example is the lemmatization of “saw”: it attempts to return either “see” (if the token is a verb) or “saw” (if the token is a noun) depending on the part of speech.

🔑 Definition — Lemmatization: A dictionary-based NLP process that returns the base or dictionary form of a word by considering its morphological analysis and part of speech.

Stemming

Stemming involves reducing terms to their “roots” before indexing. It suggests a crude affix-chopping process and is language-dependent. For example, “automate(s)”, “automatic”, and “automation” are all reduced to “automat”. Similarly, “computation”, “computing”, and “computer” all reduce to “comput”. Unlike lemmatization, stemming does not use a dictionary and may not produce a real word.

🔑 Definition — Stemming: The process of reducing inflected or derived words to their stem, base, or root form, typically by removing affixes.

Porter’s algorithm

Porter’s algorithm is the commonest algorithm for stemming English, and results suggest it is at least as good as other stemming options. It follows conventions and has 5 phases of reductions applied sequentially. Each phase consists of a set of commands. A sample convention is: “Of the rules in a compound command, select the one that applies to the longest suffix.”

Typical rules in Porter include:

• sses → ss: “Processes” becomes “Process”
• ies → i: “Skies” becomes “Ski”; “ponies” becomes “poni”
• ational → ate: “Rotational” becomes “Rotate”
• tional → tion: “national” becomes “nation”
• S → “”: “cats” becomes “cat”
• There are also weight of word sensitive rules, such as: (m>1) EMENT → null (if whatever comes before “ement” has length greater than 1, replace “ement” with null). For example, “replacement” becomes “replac”, but “cement” remains “cement”.

📌 Example: Using Porter’s rule sses → ss, the word “processes” is stemmed to “process”. The rule ies → i stems “ponies” to “poni”. The weight-sensitive rule (m>1) EMENT → null stems “replacement” to “replac” because the stem before “ement” has more than one syllable, but leaves “cement” unchanged.

Other stemmers

Other stemmers that exist include the Lovins stemmer, which is a single-pass, longest suffix removal system with about 250 rules (available at http://www.comp.lancs.ac.uk/computing/research/stemming/general/lovins.htm). There is also the Paice/Husk stemmer and Snowball. Full morphological analysis (lemmatization) is also an option, but it offers at most modest benefits for retrieval.

Language-specificity

The above methods (lemmatization and stemming) embody transformations that are language-specific and often application-specific. These are “plug-in” addenda to the indexing process. Both open source and commercial plug-ins are available for handling these language-specific transformations.

Does stemming/lemmatization help?

For English, the results are very mixed. Stemming helps recall for some queries but harms precision on others. For example, stemming “operative” (dentistry) to “oper”, “operational” (research) to “oper”, and “operating” (systems) to “oper” increases recall but reduces precision. Such normalization is not very useful in English language. However, stemming is definitely useful for Spanish, German, Finnish, and other morphologically rich languages. There are 30% performance gains for Finnish. The reason is that these languages have very clear morphological rules for forming words. Domain-specific normalization may also be helpful, such as normalizing words with respect to their usage in a particular domain.

💡 Why this matters: Understanding when stemming and lemmatization are beneficial versus harmful is critical for designing effective information retrieval systems. The decision to use these techniques depends heavily on the language of the documents and the specific retrieval goals (recall vs. precision).

⭐ Key Takeaways

A student must remember that lemmatization is a dictionary-based NLP process that returns the grammatical base form of a word, requiring part-of-speech knowledge, while stemming is a crude, rule-based affix removal that does not rely on a dictionary. Porter’s algorithm is the most common English stemmer and uses 5 sequential phases of reduction commands with weight-sensitive rules. The effectiveness of these techniques is highly language-specific: they provide limited or mixed benefits for English but significant gains (up to 30%) for morphologically rich languages like Finnish. Finally, these transformations are plug-in components to the indexing process and must be chosen based on the language and application domain.

🧠 Quick Revision Questions

1. What is the key difference between lemmatization and stemming in terms of dictionary usage and part-of-speech awareness?
2. Give two examples of typical rules in Porter’s algorithm and show how they transform specific words.
3. Why does stemming/lemmatization provide a 30% performance gain for Finnish but mixed results for English?
4. In the context of Porter’s weight-sensitive rule (m>1) EMENT → null, why does “replacement” become “replac” but “cement” remains “cement”?
5. What are the three specific other stemmers mentioned in the lecture besides Porter’s algorithm?

📘 Lecture 11 — Compression

📖 Overview: This lecture addresses the critical need for compression in information retrieval systems, specifically focusing on compressing inverted indexes. It covers techniques for efficient dictionary storage, including dictionary-as-a-string and blocking methods, to reduce memory and disk space usage, thereby improving system performance.

🗂️ Topics Covered

The lecture begins by explaining why compression is essential for inverted indexes, focusing on both the dictionary and postings files. It then explores the drawbacks of a fixed-width array for dictionary storage. The primary techniques covered are dictionary-as-a-string storage and blocking, which are methods to compress the term list and pointers, reducing overall memory footprint. The lecture concludes with references for further study.

📝 Lecture Summary

Why compression for inverted indexes?

Compression is crucial for both the dictionary and the postings file to improve efficiency. For the dictionary, compression makes it small enough to fit in main memory and can even free up space to keep some postings lists in main memory as well. For the postings file(s), compression reduces disk space needed and decreases the time required to read postings lists from disk. Large search engines keep a significant part of the postings in memory, and compression allows them to keep more data in memory, which is faster to access.

Dictionary storage - first cut

A naive approach to dictionary storage is using an array of fixed-width entries. For example, storing 500,000 terms with 28 bytes per term would require 14 MB of space. The lecture notes that fixed-width terms are wasteful because term lengths vary.

🔑 Definition — Fixed-width entries: A storage method where each term entry in the dictionary occupies the same, predetermined amount of memory, regardless of the actual length of the term.

Dictionary-as-a-String

To save space, the dictionary is stored as a (long) string of characters. A pointer to the next word shows the end of the current word. This technique can save up to 60% of dictionary space. The total space for a compressed list is calculated as:

• 4 bytes per term for Freq (frequency)
• 4 bytes per term for pointer to Postings
• 3 bytes per term pointer (to the term string)
• Average 8 bytes per term in term string

📐 Formula: Total Space = 500K terms × (4 bytes + 4 bytes + 3 bytes + 8 bytes) = 500K × 19 bytes = 9.5 MB. The average storage is now 11 bytes per term, compared to 20 bytes without compression.

💡 Why this matters: This technique demonstrates a significant reduction from 20 bytes per term to 11 bytes per term, saving nearly half the dictionary space by eliminating fixed-width waste.

📌 Example: Storing 500,000 terms. Without compression, each term used 28 bytes = 14 MB. With dictionary-as-a-string, it uses 19 bytes per term = 9.5 MB, saving 4.5 MB.

Blocking

Blocking is a technique where pointers are stored to every k-th term in the term string, rather than to every term. The example in the lecture uses k=4. This requires storing term lengths (one extra byte per term). The net effect is that where 3 bytes per pointer were used without blocking, for k=4 pointers, the storage changes from 3 × 4 = 12 bytes to 3 + 4 = 7 bytes for 4 pointers, saving ~0.5 MB.

📐 Formula: Storage for k pointers: Without blocking = k × (bytes per pointer). With blocking = (bytes for one pointer) + k (for term lengths).

📌 Example: For k=4, without blocking: 4 pointers × 3 bytes/pointer = 12 bytes. With blocking: 1 pointer (3 bytes) + 4 term lengths (4 × 1 byte = 4 bytes) = 7 bytes total.

💡 Why this matters: Blocking saves space by reducing the number of pointers needed. Larger k values can save more, but too large a k value is not recommended because it makes accessing terms slower.

Why not go with larger k?

While larger k saves more space, it makes searching for a term slower. With a larger block size, you need to scan more terms within a block to find the correct one, increasing the time for dictionary lookup.

⭐ Key Takeaways

Compression is vital for making inverted indexes efficient by reducing memory and disk usage. The dictionary-as-a-string method is a primary technique that saves significant space by storing terms contiguously with pointers instead of in fixed-width arrays. Blocking further compresses the dictionary by storing pointers only to every k-th term and using term lengths for navigation, though too large a block size can reduce search speed. The primary goal is to fit the dictionary and as many postings lists as possible into main memory to accelerate query processing. Students should understand the trade-off between compression ratio (space savings) and access speed (time).

🧠 Quick Revision Questions

1. What are the two main components of an inverted index that benefit from compression, and what are the primary benefits for each?
2. In the dictionary-as-a-string approach, what data is stored for each term, and how does this reduce space compared to a fixed-width array?
3. How does the blocking technique reduce storage, and what is the role of the "k" parameter?
4. What is the drawback of using a very large value for 'k' in blocking?
5. Calculate the total dictionary space using dictionary-as-a-string for 250,000 terms, assuming the same per-term byte costs (4 bytes Freq, 4 bytes Postings pointer, 3 bytes term pointer, 8 bytes in term string). Show your calculation.

📘 Lecture 12 — Compression

📖 Overview: This lecture explores compression techniques for information retrieval systems, focusing on reducing storage requirements for dictionaries and postings lists. It covers blocking, front coding, postings compression, and variable byte codes—essential methods for efficient index storage and retrieval.

🗂️ Topics Covered

The lecture covers four main compression techniques: blocking, which stores pointers to every kth term string; front coding, which exploits common prefixes in sorted words; postings compression, which reduces the size of document ID lists by storing gaps; and variable byte (VB) codes, which encode gap values using a continuation bit mechanism.

📝 Lecture Summary

Blocking

Blocking groups term strings into blocks and stores pointers to every kth term string only. For example, with k=4, pointers are stored for every 4th term. This technique requires storing term lengths (1 extra byte) to allow traversal within blocks.

🔑 Definition — Blocking: A compression technique where pointers are stored to every kth term string, reducing dictionary storage by grouping terms into blocks.

📐 Formula: k = block size → pointer stored for every kth term

📌 Example: With k=4 in a sorted dictionary, pointers are stored for terms at positions 1, 5, 9, etc. Each term's length requires 1 extra byte for navigation.

Front Coding

Front coding exploits common prefixes in sorted words by storing only the differences from the previous term. For the last k-1 terms in a block of k, only the suffix after the common prefix is stored.

🔑 Definition — Front coding: A compression technique that stores only the differences between consecutive sorted words, leveraging their long common prefixes.

📐 Formula: Store [length of common prefix][suffix length][suffix characters]

📌 Example: For the sequence "8automata8automate9automatic10automation":

• "automata" is stored fully (length 8)
• "automate" stores only "e" (8 characters common, length difference stored)
• "automatic" stores only "ic" (9 characters common)
• "automation" stores only "ion" (10 characters common)

Postings Compression

The postings file is much larger than the dictionary (factor of at least 10). The goal is to store each posting (docID) compactly. For Reuters (800,000 documents), 32 bits per docID are used with 4-byte integers, or about 20 bits with log₂ 800,000. The aim is to use much less than 20 bits per docID.

🔑 Definition — Postings compression: Techniques to reduce storage requirements for document ID lists by encoding gaps between consecutive docIDs rather than absolute values.

💡 Why this matters: Different terms have vastly different frequencies—rare terms like "arachnocentric" occur in ~1 in a million docs (want ~20 bits), while common terms like "the" occur in virtually every doc (20 bits/posting is too expensive, prefer bitmap).

Postings: Two Conflicting Forces

• Rare terms (e.g., "arachnocentric"): occur in ~1 in a million docs → want log₂ 1M ≈ 20 bits per posting
• Common terms (e.g., "the"): occur in virtually every doc → 20 bits/posting is too expensive → prefer 0/1 bitmap vector

Postings File Entry

Postings are stored in increasing order of docID (e.g., computer: 33, 47, 154, 159, 202...). This ordering allows storing gaps instead of absolute values: 33, 14, 107, 5, 43... Most gaps can be encoded with far fewer than 20 bits.

🔑 Definition — Gap encoding: Storing the differences between consecutive docIDs rather than absolute values, exploiting the fact that most gaps are small.

📌 Example: For docIDs [33, 47, 154, 159, 202], store gaps [33, 14, 107, 5, 43] instead of absolute values.

Variable Byte (VB) Codes

Variable Byte (VB) codes encode gap values G using close to the fewest bytes needed to hold log₂ G bits. The method uses one byte with a continuation bit (c). If G ≤ 127, binary-encode it in 7 bits with c=1. Otherwise, encode lower-order 7 bits first, then additional bytes for higher-order bits, setting c=1 on the last byte and c=0 on others.

🔑 Definition — Variable Byte (VB) codes: A compression scheme that encodes gap values using a variable number of bytes, with 7 bits per byte for data and 1 continuation bit indicating whether more bytes follow.

📐 Encoding Algorithm:

1. Start with G (gap value)
2. If G ≤ 127: store in 7 bits, set continuation bit to 1
3. Else: store lower 7 bits with continuation bit=0, then continue with remaining bits
4. Final byte always has continuation bit=1

📌 Example: For gap value G=5:

• 5 ≤ 127, so encode as binary 0000101 in 7 bits
• Set continuation bit to 1
• Result: 1 byte = [1][0000101] = 10000101 (binary)

For a larger value (e.g., G=131):

• First byte: lower 7 bits of 131 (131 mod 128 = 3 → 0000011) with c=0 → 00000011
• Second byte: higher bits (131 ÷ 128 = 1 → 0000001) with c=1 → 10000001
• Result: 2 bytes [00000011, 10000001]

⭐ Key Takeaways

The lecture emphasizes that compression is critical for efficient information retrieval, with postings files being at least 10 times larger than dictionaries. Blocking reduces dictionary storage by grouping terms and storing pointers to every kth term. Front coding exploits common prefixes in sorted words to store only differences. The key insight for postings compression is storing gaps between consecutive docIDs instead of absolute values, as most gaps are small. Variable byte codes provide a practical variable-length encoding using a continuation bit, where values ≤127 fit in one byte and larger values spread across multiple bytes with the last byte marked by continuation bit=1.

🧠 Quick Revision Questions

1. How does blocking reduce dictionary storage, and what extra information must be stored for navigation within a block?
2. In front coding, how is the term "automatic" stored if the previous term was "automata" (length 8)?
3. Why is storing postings as gaps more efficient than storing absolute docIDs, and what are the "two conflicting forces" in postings compression?
4. How does variable byte encoding handle a gap value of 200? Show the continuation bits and the resulting byte sequence.
5. For a term occurring in 500,000 out of 1,000,000 documents, explain whether gap encoding or bitmap representation would be more efficient and why.

📘 Lecture 13 — Compression

📖 Overview: This lecture explores techniques for compressing postings lists in information retrieval systems. It covers variable byte codes, unary codes, and gamma codes, explaining how these methods reduce storage space for document gap values while maintaining efficient decoding.

🗂️ Topics Covered

The lecture examines variable byte (VB) codes as a byte-aligned compression method using continuation bits, then introduces unary code as a simple representation where numbers are encoded as ones followed by a zero. Gamma codes are presented as bit-level compression using length-offset pairs, with detailed properties and examples. The lecture concludes with compression statistics from the Reuters RCV1 collection.

📝 Lecture Summary

Variable Byte (VB) codes

For a gap value G, variable byte encoding aims to use close to the fewest bytes needed to hold (\log_2 G) bits. The method begins with one byte to store G and dedicates 1 bit as a continuation bit c. If G ≤ 127, it binary-encodes the value in 7 available bits and sets c = 1. If G > 127, the algorithm encodes G’s lower-order 7 bits and uses additional bytes for higher-order bits, repeating the process. At the end, the continuation bit of the last byte is set to 1 (c = 1), while preceding bytes have c = 0.

🔑 Definition — Continuation bit: A dedicated bit in each byte indicating whether more bytes follow (c = 0) or the byte is the last in the sequence (c = 1).

📐 Formula: G encoded in VB → Use 7 bits per byte for data, 1 bit per byte for continuation flag.

📌 Example: For G = 130 (binary 10000010), the lower-order 7 bits are 0000010, and the higher-order bits are 1. First byte: higher-order 1 with continuation bit 0 → 10000001 (c=0). Second byte: lower-order 0000010 with continuation bit 1 → 10000010. Final VB code: 10000001 10000010.

Other variable unit codes use different alignment units: 32 bits (words), 16 bits, or 4 bits (nibbles). Variable byte alignment wastes space with many small gaps; nibbles perform better in such cases. VB codes are used by many commercial/research systems as a good blend of variable-length coding and sensitivity to computer memory alignment. Recent work also exists on word-aligned codes that pack a variable number of gaps into one word.

Unary code

Unary code represents a number n as n 1s followed by a final 0. This method is extremely simple but produces very long codes for large numbers.

🔑 Definition — Unary code: A representation where the integer n is encoded as n consecutive 1 bits terminated by a single 0 bit.

📐 Formula: unary(n) = (n) ones followed by one zero → total of (n+1) bits.

📌 Example: Unary code for 3 is 1110. Unary code for 40 is 40 ones followed by a zero: 11111111111111111111111111111111111111110. Unary code for 80 requires 81 bits. This approach appears impractical for large gaps but forms the foundation for gamma codes.

Gamma codes

Gamma codes provide better compression using bit-level encoding. The code represents a gap G as a pair: length and offset. The offset is G in binary with the leading bit removed. For example, 13 → binary 1101 → offset 101. The length is the number of bits in the offset. For 13 (offset 101), length = 3. The length is encoded using unary code: 1110. The gamma code of 13 is the concatenation of length and offset: 1110101.

🔑 Definition — Gamma code: A prefix-free bit-level encoding where a gap G is represented as the unary-coded length of its offset (binary representation minus leading 1) concatenated with the offset itself.

📐 Formula: gamma(G) = unary(len(offset)) + offset, where offset = binary(G) with leading 1 removed.

📌 Example: For G = 5, binary is 101, offset is 01 (length 2). Unary(2) = 110. Gamma code = 11001. For G = 40, binary is 101000, offset is 01000 (length 5). Unary(5) = 111110. Gamma code = 11111001000.

Gamma code properties

G is encoded using (2 \lfloor \log_2 G \rfloor + 1) bits. The length of offset is (\lfloor \log_2 G \rfloor) bits. The length of length is (\lfloor \log_2 G \rfloor + 1) bits. All gamma codes have an odd number of bits. This encoding is almost within a factor of 2 of the best possible (\log_2 G) bits. The gamma code is uniquely prefix-decodable, like VB, meaning no code is a prefix of another. It can be used for any distribution and is parameter-free.

🔑 Definition — Prefix-decodable: A code where no valid codeword is a prefix of any other valid codeword, enabling unambiguous decoding without separators.

📐 Formula: Bits used for G = (2 \lfloor \log_2 G \rfloor + 1) bits.

📌 Example: For G = 6 (binary 110), offset = 10 (length 2), unary(2) = 110, gamma = 11010 (5 bits). Calculation: (2 \lfloor \log_2 6 \rfloor + 1 = 2 \times 2 + 1 = 5) bits. This matches.

Reuters RCV1

Despite theoretical efficiency, gamma codes are seldom used in practice because machines have word boundaries (8, 16, 32, 64 bits). Operations that cross word boundaries are slower. Compressing and manipulating at the granularity of bits can be slow. Variable byte encoding is aligned and thus potentially more efficient. Regardless of efficiency, variable byte is conceptually simpler at little additional space cost.

RCV1 compression statistics show that index compression techniques allow creation of an index for highly efficient Boolean retrieval that is very space efficient — only 4% of the total size of the collection, or 10-15% of the total size of the text in the collection. However, positional information has been ignored; space savings are less for indexes used in practice, though techniques remain substantially the same.

💡 Why this matters: Understanding the tradeoff between compression ratio and decoding speed (bit-level vs. byte/word-aligned) is crucial for designing practical search engines that balance storage efficiency with query response time.

⭐ Key Takeaways

Variable byte codes use continuation bits to achieve byte-aligned compression of gap values, making them practical for modern systems despite space inefficiency with small gaps. Gamma codes achieve better compression ratios using bit-level encoding with unary length and trimmed binary offset, but suffer from slower decoding due to cross-word-boundary operations. Gamma codes are parameter-free, prefix-decodable, and work for any distribution, yet are seldom used in practice because byte-aligned codes offer better performance. Compression of postings lists can reduce index size to only 4% of the collection size for Boolean retrieval, though this figure increases when including positional information. The choice between compression methods involves a fundamental tradeoff between space efficiency and decoding speed.

🧠 Quick Revision Questions

1. How does the continuation bit work in Variable Byte encoding, and what values indicate whether more bytes follow?
2. What is the unary code representation for the number 5, and why is this method impractical for large gap values?
3. For a gap value G = 25, show step-by-step how to construct its gamma code, including the offset, length, and final concatenated bits.
4. According to the gamma code property formula, how many bits are required to encode the gap value G = 100?
5. Why are gamma codes seldom used in practice despite their theoretical compression efficiency, and what alternative does the lecture recommend?

📘 Lecture 14 — Index Constructions

📖 Overview: This lecture addresses the critical challenge of scaling index construction for very large document collections. It explores hardware constraints, memory hierarchy, and disk access mechanics, then introduces distributed computing approaches like MapReduce to overcome the limitations of in-memory indexing.

🗂️ Topics Covered

The lecture covers scaling index construction for large collections, the memory hierarchy and Moore’s Law, hard disk tracks, sectors, and blocks, disk access time components, hardware basics including memory vs. disk access speeds and block-based I/O, inverted index structure, and hardware assumptions for distributed computing systems.

📝 Lecture Summary

Scaling index construction

In-memory index construction does not scale for very large collections because you cannot fit the entire collection into memory, sort it, and then write it back. To construct an index for very large collections, we must take into account hardware constraints such as memory, disk, and speed.

🔑 Definition — Scaling index construction: The process of building an inverted index for collections too large to fit entirely in main memory, requiring disk-based and distributed methods.

Memory Hierarchy

The memory hierarchy organizes storage by speed and capacity, from fastest/smallest (registers, cache) to slowest/largest (hard disk, tape). Access times vary dramatically: registers (~1 ns), cache (~2 ns), main memory (~10 ns), and hard disk (~10 ms). This hierarchy dictates that algorithms must minimize slow disk accesses.

🔑 Definition — Memory hierarchy: A structured ordering of storage levels by speed, cost, and capacity, where each level acts as a cache for the next slower level.

Moore’s Law

Moore’s Law observes that the number of transistors on a microchip doubles approximately every two years, leading to exponential growth in processing power and memory capacity. However, disk seek times have not improved at the same rate, creating a growing performance gap between computation and data access.

🔑 Definition — Moore’s Law: The empirical observation that transistor density on integrated circuits doubles roughly every two years, driving exponential growth in computing capability.

Hard Disk Tracks and Sectors

Hard disks store data on platters divided into concentric tracks (rings) and sectors (arcs within tracks). The disk head must move to the correct track (seek) and wait for the correct sector to rotate under it (rotational delay) before data can be read or written.

🔑 Definition — Track: A concentric circular path on a hard disk platter where data is stored. 🔑 Definition — Sector: A subdivision of a track, typically 512 bytes, representing the smallest addressable unit of data on a disk.

Hard Disk Blocks

Operating systems group sectors into larger blocks (typically 8KB to 256KB) for efficient I/O. Reading and writing occur in whole blocks, meaning even if you need only a few bytes, the entire block is transferred. Block-based I/O is fundamental to disk performance optimization.

🔑 Definition — Block: The minimum unit of data transferred between disk and memory during a single I/O operation, consisting of multiple sectors.

Disk Access Time

The total time to read data from disk is: Access time = Seek time + Rotational delay + Transfer time. Seek time is the time to move the disk head to the correct track. Rotational delay is the wait for the right sector to spin under the head. Transfer time is the time to actually read and transfer the data.

📐 Formula: Disk Access Time = Seek Time + Rotational Delay + Transfer Time → Total time from issuing a read request to having data available in memory. 💡 Why this matters: Seek time (typically 5-10 ms) dominates access time, so minimizing seeks is critical for performance.

Hardware basics

Access to data in memory is much faster than access to data on disk. During disk seeks, no data is transferred while the head is being positioned. Therefore, transferring one large chunk of data is faster than many small chunks. Disk I/O is block-based, reading/writing entire blocks (8KB to 256 KB) rather than individual bytes.

🔑 Definition — Block-based I/O: The property that disk controllers read and write data in fixed-size blocks, not arbitrary byte ranges.

Inverted Index

The inverted index is the core data structure for information retrieval, mapping each term to a list of documents (postings list) containing that term. For large collections, the index itself can be many gigabytes, requiring disk-based construction and storage.

🔑 Definition — Inverted index: A data structure associating each term in a collection with the list of documents where that term appears, enabling fast full-text search.

Hardware basics (Continued)

Servers used in IR systems typically have several GB of main memory, sometimes tens of GB. Available disk space is several orders of magnitude larger (2–3 orders). Fault tolerance is very expensive, so it is much cheaper to use many regular machines rather than one fault-tolerant machine.

🔑 Definition — Fault tolerance: The ability of a system to continue operating properly in the event of a failure of some of its components.

Distributed computing

Distributed computing is a field of computer science that studies distributed systems, where components located on networked computers communicate and coordinate their actions by passing messages. For large-scale indexing, distributed systems allow splitting the work across many machines.

🔑 Definition — Distributed computing: A model in which components of a software system run on multiple networked computers, coordinating through message passing to achieve a common goal.

Hardware assumptions

For efficient indexing, reasonable hardware assumptions include: main memory of several GB, disk space of several TB, multiple CPU cores, and network connectivity for distributed processing. Key papers on the topic include the original MapReduce publication (Dean and Ghemawat, 2004) and SPIMI (Heinz and Zobel, 2003).

🔑 Definition — MapReduce: A programming model for processing large datasets in parallel across distributed clusters, using map and reduce operations.

⭐ Key Takeaways

The most critical concepts from this lecture are that in-memory index construction fails for large collections due to memory limitations, and understanding the memory hierarchy is essential since disk access is millions of times slower than memory. Disk access time is dominated by seeks, making block-based I/O and large sequential transfers critical for performance. For very large collections, distributed computing with approaches like MapReduce provides scalability, and it is more cost-effective to use many regular machines than one fault-tolerant supercomputer.

🧠 Quick Revision Questions

1. Why does in-memory index construction fail for very large document collections?
2. What are the three components of disk access time, and which one typically dominates?
3. Why is transferring one large chunk of data from disk faster than many small chunks?
4. What is the advantage of using many regular machines over one fault-tolerant machine in distributed indexing?
5. What does the acronym SPIMI stand for, and what problem does it solve?

📘 Lecture 15 — Merge Sort

📖 Overview: This lecture covers the fundamental sorting algorithm Merge Sort and its application in information retrieval for inverted index construction. It introduces two key indexing strategies—Single-pass in-memory indexing (SPIMI) and its block-based variant—that enable efficient processing of large document collections on a single machine.

🗂️ Topics Covered

The lecture explains the Two-Way Merge Sort algorithm with an example, introduces Single-pass in-memory indexing (SPIMI) as an alternative to traditional sorting-based methods, details the SPIMI-Invert process for generating per-block inverted indexes, and discusses merging these blocks into a single global index. It concludes by comparing SPIMI with Block Sort-Based Indexing (BSBI) and outlining future scalability challenges.

📝 Lecture Summary

Two-Way Merge Sort

A sorting algorithm that repeatedly divides a list into two halves, recursively sorts each half, then merges the two sorted halves into one sorted list. In information retrieval, this is used to sort postings during index construction.

🔑 Definition — Merge Sort: A divide-and-conquer algorithm that splits a list, sorts each half recursively, and merges the sorted halves. 📐 Formula: split list → sort left half → sort right half → merge sorted halves → produces sorted list. 📌 Example: Given list [3, 1, 4, 2], split into [3, 1] and [4, 2]; sort each to [1, 3] and [2, 4]; merge to [1, 2, 3, 4].

Single-pass in-memory indexing (SPIMI)

A memory-efficient indexing technique that processes document blocks one at a time without requiring a global term-termID mapping.

🔑 Definition — SPIMI (Single-Pass In-Memory Indexing): An indexing method that builds separate inverted indexes for each block of documents, using per-block dictionaries and no sorting of postings. 📐 Key Idea 1: Generate separate dictionaries for each block – no need to maintain term-termID mapping across blocks. 📌 Key Idea 2: Don’t sort. Accumulate postings in postings lists as they occur. 💡 Why this matters: These two ideas allow generating a complete inverted index for each block with minimal memory overhead.

SPIMI-Invert

The process of creating per-block inverted indexes using SPIMI’s dictionary-per-block approach, then merging these indexes into one global inverted index.

🔑 Definition — SPIMI-Invert: The algorithm that builds an inverted index for each document block in a single pass, then merges all block indexes into a single index. 📌 Example: Process block 1 → generate index A; process block 2 → generate index B; merge A and B into global index. 📎 Note: Merging of blocks is analogous to BSBI (Block Sort-Based Indexing).

⭐ Key Takeaways

Students must remember that SPIMI eliminates the need for global term-termID mapping by creating per-block dictionaries, and it avoids sorting by accumulating postings as they occur, making it more memory-efficient than traditional methods. The key difference from BSBI is that SPIMI builds indexes without sorting within blocks, while BSBI sorts postings per block. Both approaches produce separate block indexes that are later merged into one global inverted index. Understanding these tradeoffs is critical for designing scalable indexing solutions. The lecture concludes that these methods work when data fits on a single machine; larger collections require distributed approaches like MapReduce.

🧠 Quick Revision Questions

1. What are the two key ideas that make Single-pass in-memory indexing (SPIMI) efficient?
2. How does SPIMI-Invert differ from Block Sort-Based Indexing (BSBI)?
3. Why does SPIMI not need to maintain a global term-termID mapping across blocks?
4. What is the analogy between merging blocks in SPIMI and the merging step in BSBI?
5. When does SPIMI become insufficient, and what alternative approaches are needed?

📘 Lecture 16 — Phrase queries

📖 Overview: This lecture covers techniques for handling phrase queries in information retrieval, which require exact matches of word sequences. It introduces biword indexes, extended biwords, and positional indexes as solutions, while discussing their trade-offs in precision and index size. Understanding these approaches is critical for building search engines that can handle nuanced user queries.

🗂️ Topics Covered

The lecture begins by categorizing types of queries (phrase, proximity, wild card), then focuses on phrase queries and the limitations of simple term-document indexes. It presents the biword index approach for two-word phrases and its extension to longer phrases, followed by extended biwords using part-of-speech tagging to reduce false positives. Finally, it introduces positional indexes as a more robust solution, storing term positions within documents for precise phrase matching.

📝 Lecture Summary

Types of Queries

Three main query types are discussed:

1. Phrase Queries: Require exact word order, e.g., "The crops in pakistan" must appear as a contiguous sequence. A sentence like “I went to university at Stanford” would not match the phrase query "Stanford university".
2. Proximity Queries: Specify distance constraints between terms, e.g., LIMIT! /3 STATUTE /3 FEDERAL /2 TORT – meaning “LIMIT” within 3 words of “STATUTE”, etc.
3. Wild Card Queries: Use asterisks for pattern matching, e.g., Results* matches “Results”, “Results-based”, etc.

💡 Why this matters: Simple term-document indexes only tell you if a word appears in a document, not where. Phrase queries require positional information to distinguish “I went to university at Stanford” from “Stanford University”.

Phrase queries

The fundamental problem: a standard inverted index storing <term : docs> pairs cannot verify exact phrase matches. For a query like "Stanford university", we need to ensure the two terms appear adjacent and in that order within the document. Storing only document IDs is insufficient.

A first attempt: Biword indexes

To handle two-word phrases, the lecture introduces biword indexes, which index every consecutive pair of terms in the text as a single phrase unit.

• Example: For the text “Friends, Romans, Countrymen”, the biwords generated are:
  • friends romans
  • romans countrymen
• Each biword becomes a dictionary term, so two-word phrase queries can be answered immediately by looking up the biword.

🔑 Definition — Biword Index: An index where dictionary entries are consecutive word pairs (bigrams) from the text, allowing direct lookup of two-word phrases.

Longer phrase queries

For longer phrases like "stanford university palo alto", the query is processed by breaking it into a Boolean conjunction of overlapping biwords:

• "stanford university" AND "university palo" AND "palo alto"
• Important caveat: Without checking the original document positions, we cannot guarantee that a document matching this Boolean query actually contains the full phrase. False positives occur if the biwords appear far apart in different parts of the text.

📌 Example: A document containing “stanford university has a campus in palo alto” would match all three biwords but not the exact phrase "stanford university palo alto" – it’s a false positive.

Extended biwords

To reduce false positives, extended biwords use part-of-speech tagging (POST) to preprocess text:

1. Parse the indexed text and perform part-of-speech tagging.
2. Bucket terms into (say) Nouns (N) and articles/prepositions (X).
3. Deem any string of terms of the form NX*N (Noun, zero or more X’s, Noun) to be an extended biword.
4. Each extended biword becomes a dictionary term.

• Examples: catcher in the rye (N X X N → extended biword); Capital of Pakistan (N X N → extended biword)

Query processing:

• Given a query, parse it into N’s and X’s
• Segment query into enhanced biwords
• Look up index
• Issues:
  • Parsing longer queries into conjunctions, e.g., tangerine trees and marmalade skies is parsed into tangerine trees AND trees and marmalade AND marmalade skies
  • False positives still occur (as with biwords)
  • Index blowup due to larger dictionary (more terms)

Positional indexes

A more robust solution: positional indexes store term positions within documents. For each term, the index records: <number of docs containing term; doc1: position1, position2 ... ; doc2: position1, position2 ... ; etc.>

• This allows precise verification of phrase order and adjacency by comparing position lists.
• Example: For term “Stanford” in doc1 at positions [5, 10] and term “university” in doc1 at positions [6, 11], a query for "Stanford university" matches because positions 5 and 6 are consecutive.

🔑 Definition — Positional Index: An inverted index where for each term, we store a list of document IDs and, for each document, a list of word positions where the term occurs.

Resources: The lecture references MG 3.6, 4.3; MIR 7.2; and a paper by Williams, Zobel, and Bahle on fast phrase querying.

⭐ Key Takeaways

1. Simple term-document indexes cannot handle phrase queries because they lack word position information; storing only document IDs leads to false positives for multi-word phrases.
2. Biword indexes provide a direct but limited solution for two-word phrases, but for longer phrases require Boolean conjunctions that still produce false positives.
3. Extended biwords use part-of-speech tagging to create meaningful multi-word units (NX*N pattern), reducing but not eliminating false positives, at the cost of a larger dictionary.
4. Positional indexes are the most accurate method for phrase queries, storing exact word positions per document, enabling precise verification of adjacency and order.
5. The trade-off between index size and query precision is central: biword indexes are compact but less accurate, while positional indexes are larger but more powerful for proximity and phrase queries.

🧠 Quick Revision Questions

1. Why can’t a simple <term : list of docs> inverted index correctly answer the query "catcher in the rye"?
2. How does a biword index represent the phrase “Friends, Romans, Countrymen”?
3. What is the main limitation of using biword indexes for a query like "stanford university palo alto"?
4. In extended biwords, what pattern of part-of-speech tags defines a valid extended biword? Provide an example.
5. What additional information does a positional index store compared to a standard inverted index, and how does this solve the phrase query problem?

📘 Lecture 17 — Processing a Phrase Query

📖 Overview: This lecture covers the processing of phrase queries and proximity queries using positional indexes. It explains how to merge inverted index entries to find exact phrase matches and adapts this method for proximity searches where terms must appear within a specified word distance.

🗂️ Topics Covered

The lecture covers processing a phrase query by extracting and merging inverted index entries, proximity queries using /k notation, positional index size considerations, combination schemes that blend biword and positional indexes, and a brief introduction to wildcard queries.

📝 Lecture Summary

Processing a phrase query

To process a phrase query like "to be or not to be", extract the inverted index entries for each distinct term: to, be, or, not. Then merge the doc:position lists to enumerate all positions where the phrase appears consecutively. For example, the entry for "to" might include: 2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191; ... and for "be": 1:17,19; 4:17,191,291,430,434; 5:14,19,101; ... The same general method is used for proximity searches.

💡 Why this matters: This technique allows retrieval systems to find exact phrase matches, which is essential for search queries that require specific word order.

Proximity queries

A proximity query uses the /k notation, meaning "within k words of." For example, LIMIT! /3 STATUTE /3 FEDERAL /2 TORT requires the words to appear within the specified distances. Positional indexes can handle such queries naturally, whereas biword indexes cannot. The exercise is to adapt the linear merge of postings to handle proximity queries for any value of k.

💡 Why this matters: Proximity queries enable flexible matching where words must be near each other but not necessarily adjacent, which is useful for legal or medical document searches.

Positional index size

Positional indexes can compress position values/offsets similarly to how documents were compressed in previous lectures. However, this expands postings storage substantially because an entry is needed for each occurrence, not just once per document. Index size depends on average document size: the average web page has less than 1000 terms, while SEC filings, books, and epic poems can easily reach 100,000 terms. For a term with frequency 0.1%, the positional index grows proportionally.

Rules of thumb

As a rule of thumb, the positional index size factor is 2-4 times larger than a non-positional index. It typically accounts for 35-50% of the volume of the original text. These figures hold for "English-like" languages.

Combination schemes

A positional index expands postings storage because it stores every occurrence. However, biword indexes and positional indexes can be profitably combined. For particular phrases like “Michael Jackson” or “Britney Spears,” it is inefficient to keep merging positional postings lists. This inefficiency is even more pronounced for phrases like “The Who,” where common words appear frequently.

💡 Why this matters: Combining both index types allows the system to handle common phrases efficiently while still supporting general proximity queries.

Wild Card Queries

Wildcard queries allow pattern matching using wildcards. Examples include: Stan* matches Standard, Stanford; ST matches Start; ion matches Option; Paan matches Pakistan; Pat*an matches Pakistan, etc.

💡 Why this matters: Wildcard queries enable users to search for terms when they are unsure of the exact spelling or want to find all variations.

⭐ Key Takeaways

You must remember the three key methods for handling phrase and proximity queries: positional indexes store every word occurrence and allow phrase and proximity matching; biword indexes are efficient for common phrases but cannot handle general proximity; and combination schemes merge both approaches for optimal performance. Positional indexes are 2-4 times larger than non-positional ones and occupy 35-50% of the original text volume. Wildcard queries expand search flexibility by allowing pattern matching on unknown or variable terms.

🧠 Quick Revision Questions

1. How do you process a phrase query like "to be or not to be" using inverted index entries?
2. What does the /k notation mean in a proximity query, and how does it differ from exact phrase matching?
3. Why are positional indexes significantly larger than non-positional indexes?
4. What is the advantage of combining biword indexes with positional indexes?
5. How do wildcard queries like "Stan*" or "Patan" work in terms of pattern matching?

📘 Lecture 18 — Information Retrieval Techniques (Wild Card Queries & B-Tree)

📖 Overview: This lecture focuses on techniques for handling wild-card queries in information retrieval systems, covering how to search for word prefixes, suffixes, and complex patterns. It also introduces the B-Tree and B+ Tree data structures that support efficient lexicon lookup.

🗂️ Topics Covered

The lecture covers wild-card query handling using B-Trees, Permuterm Index, K-Grams, and Soundex Algorithms. It explains how to handle prefix queries like "mon*" and suffix queries like "*mon", and describes the B-Tree and B+ Tree structures used for efficient term retrieval.

📝 Lecture Summary

How to Handle Wild-Card Queries

Wild-card queries allow users to search for terms when they only know part of the word. The lecture outlines several approaches: B-Trees, Permuterm Index, K-Grams, and Soundex Algorithms. These techniques enable the system to find all matching terms in the lexicon efficiently.

🔑 Definition — B-Tree: A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Wild-card queries: *

Wild-card queries use the asterisk () as a placeholder for any sequence of characters. The query mon finds all documents containing any word beginning with "mon". This is easy to handle with a sorted lexicon: retrieve all words in the range mon ≤ w < moo.

However, the query *mon — finding words ending in "mon" — is harder. The solution is to maintain an additional B-tree for terms stored backwards. This allows retrieval of all words in the range nom ≤ w < non.

📐 Formula: For prefix query mon* → range search: mon ≤ w < moo For suffix query *mon → reverse term to nom → range search: nom ≤ w < non

📌 Example: To enumerate all terms meeting the wild-card query pro*cent:

1. Split the query into two parts: pro* and *cent
2. Use the forward B-tree to find all terms starting with pro (range: pro ≤ w < prp)
3. Use the backward B-tree to find all terms ending with cent (reverse to tnec, range: tnec ≤ w < tned)
4. Intersect the two result sets to find terms satisfying both conditions

💡 Why this matters: This approach allows efficient retrieval even for complex wild-card patterns, which is essential for search engines and database systems.

B-Tree

The B-Tree is a fundamental data structure for lexicon storage. It maintains terms in sorted order and supports efficient range queries. The slides show a B-Tree structure where each node contains multiple keys and pointers, allowing fast insertion, deletion, and search operations.

B+ Tree

The B+ Tree is a variant of the B-Tree where all data is stored in the leaves, and internal nodes only contain keys for routing. This structure is particularly efficient for range queries and sequential access, as all leaf nodes are linked together.

Wild-card queries example

The lecture provides an example of the B-Tree structure for handling wild-card queries. It also references resources for further reading:

• IIR 3, MG 4.2 for information retrieval concepts
• K. Kukich (1992) on automatic text correction
• J. Zobel and P. Dart (1995) on approximate matching in large lexicons
• Peter Norvig's guide on how to write a spelling corrector

⭐ Key Takeaways

For wild-card queries, prefix searches (mon) are straightforward using range queries on a forward B-tree, while suffix searches (mon) require a separate backward B-tree. Complex queries like procent* require intersecting results from both forward and backward trees. The B-Tree and B+ Tree are the primary data structures for efficient lexicon storage and retrieval, supporting logarithmic-time searches and range queries. Understanding these techniques is critical for implementing search engines and database systems that handle partial-match queries.

🧠 Quick Revision Questions

1. How would you handle a wild-card query like "comp*" using a B-Tree?
2. What is the key difference between handling prefix queries and suffix queries?
3. How do you enumerate all terms matching the wild-card query "pro*cent"?
4. What is the advantage of storing terms in a backward B-tree for suffix queries?
5. How does a B+ Tree differ from a standard B-Tree in terms of data storage?

📘 Lecture 19 — Permuterm Index, k-gram, Soundex

📖 Overview: This lecture covers techniques for handling wildcard queries in information retrieval systems. It introduces the permuterm index and k-gram indexes as methods for efficient wildcard query processing, and concludes with Soundex, a phonetic algorithm for matching names. Understanding these techniques is essential for building robust search systems that handle imprecise queries.

🗂️ Topics Covered

The lecture covers three main topics: the Permuterm index, which uses a specialized dictionary structure for wildcard queries; k-gram (specifically bigram) indexes, which offer a more space-efficient alternative; and the Soundex algorithm, which matches terms based on their phonetic similarity rather than exact spelling.

📝 Lecture Summary

Permuterm index

The Permuterm index is a technique for handling wildcard queries in information retrieval. It works by creating a special index of all rotations (permutations) of each term in the dictionary, where a special symbol $ marks the end of a word. For example, the word hello generates rotations: hello$, ello$h, llo$he, lo$hel, o$hell, and $hello. To process a wildcard query like hel*o, you rotate the query to o$hel* and look up o$hel* in the permuterm index to find matches like hello$. This technique can handle both single and multiple wildcard characters, but it is space-intensive because the permuterm index can be roughly four times larger than the original dictionary.

🔑 Definition — Permuterm index: A wildcard query processing technique that indexes all rotations of dictionary terms, using a special end-of-word marker, to allow wildcard queries to be executed as exact-match lookups.

📌 Example: For the query mon*, the system rotates the query to mon* and looks up all entries starting with mon in the permuterm index. It would find terms like moon and money.

Bigram (k-gram) indexes

A k-gram index is an alternative to the permuterm index for processing wildcard queries. It indexes all contiguous sequences of ( k ) characters (substrings) from each dictionary term. For example, with k=2 (bigrams), the term moon generates bigrams: $m, mo, oo, on, n$. To process a query like mon*, the system converts the query to bigram constraints: $m AND mo AND on, then finds dictionary terms that contain all three bigrams. This is more space-efficient than the permuterm index but requires a post-filtering step to remove false positives (e.g., moon would be found but must be checked against the original query). Typically, bi-grams (k=2) or tri-grams (k=3) are used; larger k-grams reduce flexibility in query processing.

🔑 Definition — k-gram index: A wildcard query processing technique that indexes all substrings of length ( k ) from dictionary terms to find candidate terms that satisfy bigram constraints.

📐 Formula: For a query mon*, the bigram query becomes: $m AND mo AND on → these are all bigrams from the query, with $ as start-of-word marker.

📌 Example: Query mon* is processed by:

1. Break the query into bigrams: $m, mo, on
2. Look up the posting list for each bigram
3. Find terms that contain all three bigrams: e.g., moon (contains $m, mo, oo, on, n$)
4. Post-filter: check if the candidate term moon matches mon* (yes, it matches month but not moon)
5. Surviving terms are looked up in the term-document inverted index.

💡 Why this matters: The bigram index is fast and space-efficient compared to the permuterm index, making it a practical choice for many search systems.

Soundex

Soundex is a phonetic algorithm that maps words to a code based on their pronunciation, designed to match names that sound alike but are spelled differently. It was invented for the U.S. census in 1918. For example, chebyshev maps to tchebycheff. The algorithm is language-specific, mainly for names, and is used by databases (Oracle, Microsoft, etc.) to provide phonetic matching. It increases recall (finds more relevant results) but lowers precision (includes some irrelevant results). For instance, a Soundex query for SMITH might return Lindsay and William. It is used by Interpol for name matching but is typically tailored to European names.

🔑 Definition — Soundex: A phonetic algorithm that converts a word into a four-character code (<uppercase letter><digit><digit><digit>) to match words that sound alike.

📐 Algorithm (typical):

1. Retain the first letter of the word as the first character of the code.
2. Replace remaining letters with digits (1-6) based on phonetic groups (e.g., b,f,p,v → 1; c,g,j,k,q,s,x,z → 2; d,t → 3; l → 4; m,n → 5; r → 6). Vowels, h, w, and y are ignored (coded as 0).
3. Remove all pairs of consecutive identical digits.
4. Remove all zeros from the resulting string.
5. Pad the resulting string with trailing zeros and return the first four positions.

📌 Example: Herman becomes H655:

• H is retained → H
• e (ignored) → 0, r → 6, m → 5, a (ignored) → 0, n → 5
• String: H06505
• Remove consecutive duplicates: H06505
• Remove zeros: H655
• Pad with trailing zeros (already 4 characters): H655

⭐ Key Takeaways

Students must remember the differences between permuterm index and k-gram indexes for handling wildcard queries: permuterm is more flexible but space-intensive, while k-gram (especially bigram) is more space-efficient but requires post-filtering. The Soundex algorithm is a four-character phonetic code designed for name matching in databases, increasing recall at the cost of precision. For the exam, be able to process a wildcard query using both permuterm and bigram methods, and compute a Soundex code for a given name. The key applications are wildcard query processing in search engines and phonetic name matching in database systems.

🧠 Quick Revision Questions

1. How does the permuterm index process a wildcard query like hel*o? (Include the query rotation step.)
2. For the term moon, list all its bigrams (k=2) with start and end markers.
3. What are the steps to compute a Soundex code for the name Johnson?
4. Which is more space-efficient: the permuterm index or the bigram index? Why?
5. Why does Soundex increase recall but lower precision when used in name searches?

📘 Lecture 20 — Spelling Correction

📖 Overview: This lecture covers techniques for correcting spelling errors in both documents and user queries within information retrieval systems. It explains how spell correction improves search accuracy by handling misspellings through isolated word and context-sensitive methods, focusing on edit distance and n-gram overlap as core approaches.

🗂️ Topics Covered

This lecture covers the two principal uses of spell correction in information retrieval: correcting documents during indexing (especially for OCR) and correcting user queries to retrieve the right results. It distinguishes between isolated word correction and context-sensitive correction, explains edit distance (Levenshtein distance) and weighted edit distance, introduces n-gram overlap, and includes a discussion on dynamic programming with a Fibonacci series example as a problem-solving technique.

📝 Lecture Summary

Spell correction

Spell correction has two principal uses in information retrieval: correcting documents being indexed and correcting user queries to retrieve the “right” answers. There are two main flavors: Isolated word correction checks each word on its own for misspelling but will not catch typos resulting in correctly spelled words (e.g., “from” → “form”). Context-sensitive correction looks at surrounding words to catch such errors (e.g., “I flew form Lahore to Dubai”).

💡 Why this matters: Context-sensitive correction is critical for understanding user intent when a typo produces a valid word.

Document correction

Document correction is especially needed for OCR’ed documents. Correction algorithms are tuned for specific confusions, like rn/m (e.g., “modern” may be considered as “modem”). Algorithms can use domain-specific knowledge — for example, OCR can confuse O and D more often than O and I (adjacent on the QWERTY keyboard, so more likely interchanged in typing). However, web pages and even printed material have typos. The goal is that the dictionary contains fewer misspellings, but often we don’t change the documents and instead fix the query-document mapping.

🔑 Definition — Document correction: The process of fixing spelling errors in the document corpus, especially needed for OCR output, to improve indexing accuracy.

Query mis-spellings

Query misspellings are the principal focus here. For example, the query “Fasbinder” vs. “Fassbinder” (correct German surname). We can either retrieve documents indexed by the correct spelling, OR return several suggested alternative queries with the correct spelling — as seen in Google’s “Did you mean...?” feature.

🔑 Definition — Query misspelling: An incorrectly spelled word in a user’s search query that must be corrected to retrieve relevant documents.

Isolated word correction

The fundamental premise is that there is a lexicon from which the correct spellings come. Two basic choices for this: a standard lexicon (e.g., Webster’s English Dictionary), or an “industry-specific” lexicon — hand-maintained. Additionally, the lexicon of the indexed corpus can be used (e.g., all words on the web, including misspellings). Given a lexicon and a character sequence Q, we must return the words in the lexicon closest to Q. “Closest” is determined using several alternatives: Edit distance (Levenshtein distance), Weighted edit distance, and n-gram overlap.

🔑 Definition — Isolated word correction: A spell correction method that checks each word on its own for misspelling against a lexicon without considering context. 🔑 Definition — Lexicon: A dictionary of correct words used as a reference for spell correction.

Edit distance

Edit distance (also known as Levenshtein distance) is the minimum number of operations to convert one string S₁ to another S₂. Operations are typically character-level: Insert, Delete, Replace, and sometimes Transposition. For example, the edit distance from “dof” to “dog” is 1 (replace f with g). From “cat” to “act” is 2 (delete c, insert a before t) — but just 1 with transpose (swap c and a). From “cat” to “dog” is 3. Generally, edit distance is found by dynamic programming.

📐 Formula: Edit distance = minimum number of insert, delete, replace (and optionally transpose) operations to transform one string into another. 📌 Example: From “cat” to “act”:

• Without transpose: delete ‘c’ (1), insert ‘a’ at start (1) = 2 operations
• With transpose: swap ‘c’ and ‘a’ = 1 operation

Problem Solving Techniques

Dynamic programming solves sub-problems bottom up. The problem cannot be solved until we find all solutions of sub-problems. The solution comes up when the whole problem appears. In contrast, Divide and conquer works by dividing the problem into sub-problems, conquering each sub-problem recursively, and combining these solutions.

🔑 Definition — Dynamic programming: A problem-solving technique that solves sub-problems bottom-up, building solutions incrementally until the full problem is solved.

Fibonacci series

Definition: The first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1, depending on the chosen starting point, and each subsequent number is the sum of the previous two (Wikipedia). The algorithm is:

Fib(n) {
  if (n == 1) return 0;
  if (n == 2) return 1;
  else return Fib(n-1) + Fib(n-2);
}

The Fibonacci Tree shows the recursive calls for computing Fibonacci numbers, demonstrating the overlapping sub-problems that make dynamic programming an efficient approach.

🔑 Definition — Fibonacci series: A sequence where each number is the sum of the two preceding ones, typically starting with 0 and 1.

⭐ Key Takeaways

Spell correction in information retrieval has two main uses: correcting documents (especially OCR output) and correcting user queries. The two main approaches are isolated word correction (checking each word independently against a lexicon) and context-sensitive correction (considering surrounding words). Isolated word correction relies on edit distance (Levenshtein distance) to find the closest matching word in the lexicon, using operations like insert, delete, and replace. Edit distance is calculated using dynamic programming, which solves sub-problems bottom-up. Understanding these concepts is essential for implementing spell checkers in search engines and document processing systems.

🧠 Quick Revision Questions

1. What are the two principal uses of spell correction in information retrieval?
2. What is the difference between isolated word correction and context-sensitive correction?
3. What is edit distance and what operations does it use?
4. Why is dynamic programming used to calculate edit distance?
5. In the context of document correction, what does the confusion "rn/m" mean and why does it occur?

📘 Lecture 21 — Spelling Correction

📖 Overview: This lecture covers techniques for spelling correction in information retrieval systems, focusing on how to handle user query errors. It introduces edit distance and n-gram overlap methods to find and rank potential corrections, which is essential for improving search accuracy and user experience.

🗂️ Topics Covered

The lecture covers edit distance as a metric for measuring string similarity, methods for using edit distances to generate spelling suggestions, weighted edit distance for capturing common errors like OCR or keyboard mistakes, n-gram overlap as an alternative approach, and the Jaccard coefficient as a normalized measure of similarity.

📝 Lecture Summary

Edit distance

Edit distance is a fundamental concept for measuring similarity between two strings. It is defined as the minimum number of operations required to convert one string into another. The standard operations are character-level: Insert, Delete, Replace, and optionally Transposition (swapping two adjacent characters). This distance is typically computed using dynamic programming.

🔑 Definition — Edit distance: The minimum number of character-level operations (Insert, Delete, Replace, Transposition) needed to transform one string into another.

📐 Formula: No single formula, but computed via dynamic programming table. For strings S1 and S2, the cost at position (i,j) is: min(cost of insertion, cost of deletion, cost of substitution)

📌 Example: The edit distance from dof to dog is 1 (replace 'f' with 'g'). From cat to act is 2 (transposition, or 2 operations without transpose). From cat to dog is 3 (replace each character).

💡 Why this matters: Edit distance provides a principled way to quantify how "far apart" two words are, which is crucial for suggesting corrections when a user misspells a query term.

Using edit distances

This section discusses practical strategies for applying edit distance in a search system. The primary approach is to enumerate all character sequences within a preset (or weighted) edit distance (commonly 2) from the query. This set is then intersected with a list of "correct" words (the lexicon). The matching terms are shown to the user as suggestions. Alternatively, the system can look up all possible corrections in the inverted index and return documents, though this is slow. Another approach is to run with a single most likely correction, which disempowers the user but saves a round of interaction.

Weighted edit distance

Weighted edit distance is an extension of basic edit distance where the cost of each operation depends on the specific characters involved. This is designed to capture realistic error patterns such as OCR (Optical Character Recognition) errors or keyboard typing errors. For example, the letter 'm' is more likely to be mis-typed as 'n' (adjacent on keyboard) than as 'q' (distant), so replacing 'm' with 'n' should have a smaller cost than replacing 'm' with 'q'. This approach can be formulated as a probability model and requires a weight matrix as input. The dynamic programming algorithm is modified to incorporate these weights.

🔑 Definition — Weighted edit distance: A variant of edit distance where the cost of each operation (insert, delete, replace) depends on the specific characters involved, rather than being uniform.

n-gram overlap

n-gram overlap provides an alternative method for finding spelling corrections. The process involves enumerating all the n-grams (contiguous subsequences of n characters) in the query string and in the lexicon. The system uses an n-gram index (similar to that used for wild-card searches) to retrieve all lexicon terms that match any of the query's n-grams. Results are then thresholded by the number of matching n-grams. Variants can weight matches by keyboard layout or other factors.

📌 Example with trigrams: Suppose the text is november. Its trigrams are: nov, ove, vem, emb, mbe, ber. The query is december. Its trigrams are: dec, ece, cem, emb, mbe, ber. The overlapping trigrams are emb, mbe, ber — a total of 3 out of 6 in each term.

One option – Jaccard coefficient

To turn raw n-gram overlap counts into a normalized measure of similarity, the Jaccard coefficient is used. It calculates the ratio of the size of the intersection of two sets to the size of their union. For the trigram example: Jaccard coefficient = (size of intersection) / (size of union) = 3 / (6 + 6 - 3) = 3/9 = 1/3.

🔑 Definition — Jaccard coefficient: A normalized measure of similarity between two sets, calculated as the size of their intersection divided by the size of their union.

📐 Formula: Jaccard(A, B) = |A ∩ B| / |A ∪ B| → The fraction of total unique elements that are shared between two sets.

📌 Example: For trigram sets of "november" and "december": intersection size = 3 (emb, mbe, ber), union size = 9 (nov, ove, vem, emb, mbe, ber, dec, ece, cem). Jaccard = 3/9 = 0.333.

⭐ Key Takeaways

The most critical concepts from this lecture are understanding edit distance as the minimum number of operations to convert one string to another, and knowing how to apply it for spelling correction by enumerating sequences within a threshold. Weighted edit distance is crucial for modeling realistic errors like OCR mistakes, where operation costs depend on character pairs. N-gram overlap provides an efficient alternative, especially when combined with an n-gram index, and the Jaccard coefficient normalizes this overlap into a proper similarity metric. The trade-off between returning multiple suggestions vs. a single correction is important for system design.

🧠 Quick Revision Questions

1. What are the four standard operations used in edit distance, and which one is optional?
2. How does weighted edit distance differ from standard edit distance, and what type of errors does it model?
3. What is the edit distance from "cat" to "act" when transposition is allowed versus when it is not?
4. How many trigrams does the word "november" have, and what are they?
5. How is the Jaccard coefficient calculated for n-gram overlap, and what does a value of 0.333 indicate?

📘 Lecture 22 — Spelling Correction

📖 Overview: This lecture focuses on techniques for correcting spelling errors in information retrieval systems, particularly for query terms. It covers matching trigrams, the use of the Jaccard coefficient to identify candidate terms, context-sensitive spell correction, and general issues in spell correction.

🗂️ Topics Covered

The lecture covers matching trigrams using Jaccard coefficient to identify candidate terms, computing the Jaccard coefficient with n-grams, joining n-grams with edit distance for efficient correction, context-sensitive spell correction using surrounding context and query logs, and general issues in spell correction with relevant resources.

📝 Lecture Summary

Matching trigrams

The process of spelling correction often begins with matching trigrams (3-letter n-grams) to find candidate terms from a dictionary. A heuristic approach is used to improve efficiency when computing the Jaccard coefficient (J.C.).

🔑 Definition — Heuristic for Jaccard Coefficient: While computing the Jaccard coefficient, we may disregard the repeating n-grams in the query term as well as in the current dictionary term. The reason is that we are computing a candidate term in any case, which we shall process later using edit distance.

Computing Jaccard coefficient

The Jaccard coefficient is a measure used to compare the similarity and diversity of sample sets. In spell correction, it helps identify candidate terms by comparing the n-gram sets of the query term and dictionary terms.

📐 Formula: Jaccard coefficient = (|A ∩ B|) / (|A ∪ B|) → The number of n-grams common to both sets divided by the total number of unique n-grams in the union of both sets.

📌 Example: For query term "form" and dictionary term "from":

• Trigrams of "form": {"for", "orm"}
• Trigrams of "from": {"fro", "rom"}
• Common trigrams: none
• Jaccard coefficient = 0/4 = 0

Joining N-grams with Edit Distance

The n-gram approach will give an Answer list which contains candidate terms. These terms can then be checked for Edit Distance. This process helps avoid checking the edit distance for all dictionary terms and each term, but restricts it to only candidate terms in the answer list.

💡 Why this matters: This two-step approach significantly reduces computational overhead by filtering the dictionary using n-gram matching before applying the more expensive edit distance calculation.

Context-sensitive spell correction

Context-sensitive correction requires the surrounding context to catch errors that are context-dependent, such as in the phrase "flew form heathrow" (where "form" should be "from"). Natural Language Processing (NLP) is considered too heavyweight for this task in information retrieval.

The first idea is to retrieve dictionary terms close (in weighted edit distance) to each query term. Then, try all possible resulting phrases with one word "fixed" at a time. For example:

• flew from heathrow
• fled form heathrow
• flea form heathrow
• etc.

Suggest the alternative that has lots of hits. It is more appropriate to look for hits in Query Logs rather than in the corpus.

🔑 Definition — Context-sensitive correction: Suppose that for "flew form Heathrow", we have 7 alternatives for "flew", 19 for "form", and 3 for "heathrow". Instead of checking 7193 = 399 combinations, we look for the most frequent (in corpus/in query log) replacement of the first word, combine it with the second to formulate a bigram, then choose the most frequent and then combine it with the third one. This reduces it to much less than 399.

📌 Alternative approaches: Correct each word separately, which will result in 7+19+3 = 29 operations. Another alternative is to only correct the misspelled words.

General issues in spell correction

General issues in spell correction include the efficiency of retrieval, the accuracy of suggestions, and the choice of resources (corpus vs. query logs) for frequency-based decisions.

Resources for further reading include:

• IIR 3, MG 4.2 (textbooks)
• K. Kukich. Techniques for automatically correcting words in text. ACM Computing Surveys 24(4), Dec 1992.
• J. Zobel and P. Dart. Finding approximate matches in large lexicons. Software - practice and experience 25(3), March 1995.
• Mikael Tillenius: Efficient Generation and Ranking of Spelling Error Corrections. Master's thesis at Sweden's Royal Institute of Technology.
• Peter Norvig: How to write a spelling corrector (http://norvig.com/spell-correct.html) — a nice, easy reading on spell correction.

⭐ Key Takeaways

The most critical concepts for the exam are: (1) The Jaccard coefficient is used to measure n-gram similarity between query terms and dictionary terms to identify candidate corrections, with a heuristic to disregard repeating n-grams. (2) N-gram matching filters the dictionary before applying edit distance, significantly improving efficiency. (3) Context-sensitive correction requires surrounding context and can be computationally expensive; using query logs is more appropriate than corpus hits. (4) The phrase approach can be optimized by checking alternatives incrementally (bigram by bigram) rather than evaluating all possible combinations. (5) Spell correction resources include key research papers by Kukich, Zobel and Dart, and a practical introduction by Peter Norvig.

🧠 Quick Revision Questions

1. What is the heuristic used when computing the Jaccard coefficient for n-gram matching, and why is it applied?
2. How does joining n-grams with edit distance improve the efficiency of spell correction?
3. In context-sensitive correction, why is it more appropriate to look for hits in query logs rather than in a corpus?
4. For the phrase "flew form heathrow" with 7 alternatives for "flew", 19 for "form", and 3 for "heathrow", describe two different approaches to reduce the search space from 399 combinations.
5. Which researcher's work on "Techniques for automatically correcting words in text" is referenced as a resource for efficient spell retrieval?