CS726 — Final Term Summary (Lectures 23–45)

📘 Lecture 23 — Performance Evaluation of Information Retrieval Systems

📖 Overview: This lecture explores how we evaluate the effectiveness and performance of Information Retrieval (IR) systems. It identifies the challenges in measuring system quality, defines various performance metrics, and explains how to assess user happiness with search engines across different contexts like web, eCommerce, and enterprise settings.

🗂️ Topics Covered

The lecture begins by asking why we need to evaluate IR systems and highlights the difficulties involved, such as the subjective and dynamic nature of relevancy. It then details the specific measures for a search engine, including indexing speed, search latency, and query expressiveness. The core of the lecture focuses on the concept of measuring user happiness, examining how this varies depending on the setting (web, eCommerce, enterprise). Finally, it discusses practical ways to tell if users are happy, such as analyzing click-through rates, purchase behavior, and user return rates.

📝 Lecture Summary

Why System Evaluation?

There are many different retrieval models, algorithms, and systems, so we need a method to determine which one is best. Evaluation helps us choose the best component for tasks like selecting a ranking function (e.g., dot-product, cosine), choosing term selection methods (e.g., stopword removal, stemming), or deciding on term weighting strategies (e.g., TF, TF-IDF). A key question evaluation answers is how far down a ranked list a user must look to find enough relevant documents.

💡 Why this matters: Without systematic evaluation, we cannot objectively improve search engines or compare different research approaches.

Difficulties in Evaluating IR Systems

Effectiveness is directly related to the relevancy of retrieved items. However, measuring relevancy is inherently difficult. Relevancy is usually not a simple binary classification (relevant/not relevant) but a continuous scale. Even when treated as binary, it can be a difficult judgment for a human to make. From a human perspective, relevancy has four key characteristics:

• Subjective: It depends on a specific user's own judgment.
• Situational: It relates to the user's current needs and context.
• Cognitive: It depends on human perception and behavior.
• Dynamic: It can change over time as the user's knowledge or situation evolves.

Measures for a search engine

Performance can be measured by several factors:

• Indexing Speed: How fast does the system index documents? Measured by the number of documents indexed per hour (considering average document size).
• Search Speed: How fast does it search? Measured by latency as a function of index size.
• Expressiveness of Query Language: The system's ability to allow users to express complex information needs and its speed when processing such complex queries.
• User Interface (UI): An uncluttered and intuitive UI is a crucial performance factor.
• Cost: Is it free or what is the pricing model?

Measuring user happiness

A central issue is who is the user we are trying to make happy, as this depends on the setting.

• Web Engine: The user finds what they want and returns to the engine. Happiness can be measured by the rate of return users. The user's goal is to complete a task, with search being a means, not an end.
• eCommerce Site: The user finds what they want and buys it. The question is whether we measure happiness for the end-user or the eCommerce site. Metrics include time to purchase or the fraction of searchers who become buyers.
• Enterprise (company/govt/academic): The focus is on "user productivity". The key question is how much time users save when looking for information. Other criteria involve breadth of access and secure access.

How do you tell if users are happy?

Several observable behaviors can indicate user happiness at scale:

• Relevance: The search returns products relevant to users.
• Click-through Rate: Search results get clicked a lot. However, be cautious as misleading titles or summaries can cause users to click on irrelevant results.
• Conversion: Users buy after using the search engine, or more generally, users spend a lot of money after using the search engine.
• Repeat Behavior: The presence of repeat visitors or repeat buyers is a strong indicator of happiness.
• Bounce Rate & Retention: Observing if users leave soon after searching, or if they return within a week, month, or year.

⭐ Key Takeaways

Evaluating IR systems is a complex but essential task. The primary challenge is that relevancy is subjective, situational, cognitive, and dynamic, making it difficult to quantify. A system's performance is measured by more than just speed, including indexing rate, search latency, and query expressiveness. The definition of "user happiness" is highly context-dependent, varying between web search, eCommerce, and enterprise settings. Ultimately, user happiness is inferred from behavior like click-throughs, purchases, and repeat visits, but these signals must be interpreted carefully to avoid being misled by, for example, clickbait titles.

🧠 Quick Revision Questions

1. What are the four human-centric characteristics that make relevancy difficult to measure?
2. Name three types of performance measures for a search engine, other than user happiness.
3. How does the definition of "user happiness" differ between a web search engine and an eCommerce site?
4. Explain why a high click-through rate is not always a reliable indicator of user happiness.
5. In an enterprise setting, what is the primary measure of user happiness?

📘 Lecture 24 — Information retrieval techniques

📖 Overview: This lecture focuses on how to evaluate Information Retrieval (IR) systems, focusing on benchmarks, relevance judgments, and the challenges of measuring search quality. Understanding these methods is essential for building and testing effective search algorithms.

🗂️ Topics Covered

The lecture covers the elusive nature of measuring happiness (relevance), the concept of a Gold Standard (human-labeled corpora), how to measure the quality of a new search algorithm, issues with relevance judgments, crowd-sourcing for relevance, standard relevance benchmarks (like TREC), and finally how to evaluate an IR system.

📝 Lecture Summary

Happiness: elusive to measure

The most common proxy for "happiness" in an IR system is the relevance of search results. Measuring relevance requires three elements: (1) a benchmark document collection, (2) a benchmark suite of queries, and (3) a binary assessment (Relevant or Nonrelevant) for each query-document pair. While some work exists on more-than-binary scales, binary assessment is the standard.

Human Labeled Corpora (Gold Standard)

A Gold Standard is created by starting with a corpus of documents, collecting a set of queries for that corpus, and having one or more human experts exhaustively label the relevant documents for each query. This typically assumes binary relevance judgments. This process requires considerable human effort for large document/query corpora.

Relevance judgments

Relevance judgments are usually binary (relevant vs. non-relevant), but can be more nuanced (0, 1, 2, 3...) in other cases. The main issue is the scale: 5 million documents times 50K queries leads to a quarter trillion judgments. Even at 2.5 seconds per judgment, this would take 10¹¹ seconds and cost nearly $300 million at $10 per hour. Additionally, 10,000 new products (documents) are added every day.

🔑 Definition — Gold Standard: A human-labeled corpus where experts have assessed the relevance of documents to specific queries, used as a ground truth for evaluating IR systems.

Crowd source relevance judgments?

One approach to reduce costs is to use crowd-sourcing platforms (like Amazon Mechanical Turk). This involves presenting query-document pairs to low-cost labor online, hoping it's cheaper than hiring qualified assessors. The main takeaway is that while you get some signal, the variance in the resulting judgments is very high.

What else?

Still, you need test queries that are germane to the available documents and representative of actual user needs. Random query terms from the documents are generally not a good idea. Instead, sample from query logs if available. Classically (non-Web), with low query rates and not enough query logs, experts hand-craft "user needs."

Standard relevance benchmarks

The TREC (Text REtrieval Conference) by the National Institute of Standards and Technology (NIST) has run a large IR test bed for many years. It uses Reuters and other benchmark doc collections. "Retrieval tasks" are specified, sometimes as queries. Human experts mark, for each query and for each doc, Relevant or Nonrelevant (or at least for the subset of docs that some system returned for that query).

📌 Example: Public test collections include TREC, Reuters, and others collected by NIST.

Evaluating an IR system

Key insight: The user's information need is translated into a query. Yet, relevance is assessed relative to the user need, not the query itself. For example, the information need might be "My swimming pool bottom is becoming black and needs to be cleaned," while the query is "pool cleaner." The assessor must determine if the document addresses the underlying need, not just whether it contains the words "pool" and "cleaner."

⭐ Key Takeaways

The key point is that evaluating an IR system requires a Gold Standard of human-labeled relevance judgments, but this is extremely costly at scale. Crowd-sourcing offers a cheaper alternative but introduces high variance. The most critical concept is that relevance must be judged against the user's true information need, not merely the query terms they typed, and benchmarks like TREC provide standardized resources for this purpose. Understanding these evaluation methods is fundamental to developing and validating effective search algorithms.

🧠 Quick Revision Questions

1. What are the three essential elements required for measuring relevance in an IR evaluation?
2. What is a "Gold Standard" in the context of IR evaluation, and what is its main limitation?
3. Why is crowd-sourcing for relevance judgments considered problematic, despite being cheaper?
4. What is the key difference between assessing relevance to a "query" versus assessing relevance to a "user need"?
5. Name one major standard relevance benchmark mentioned in the lecture and describe its role.

📘 Lecture 25 — Benchmarks for the Evaluation of IR Systems

📖 Overview: This lecture introduces key evaluation measures for information retrieval (IR) systems, focusing on how to assess system performance. It explains why accuracy is not suitable for IR and details the critical concepts of precision and recall, including their trade-off and calculation methods.

🗂️ Topics Covered

The lecture covers evaluation measures such as precision, recall, accuracy, mean average precision, F-measure/E-measure, non-binary relevance, discounted cumulative gain, and normalized discounted cumulative gain. It then focuses on unranked retrieval evaluation, the trade-off between recall and precision, and computing recall/precision points with an example.

📝 Lecture Summary

Evaluation Measures

This section lists the key evaluation measures used in IR systems. These include Precision, Recall, Accuracy, Mean Average Precision, F-Measure/E-Measure, Non-Binary Relevance, Discounted Cumulative Gain, and Normalized Discounted Cumulative Gain. Each measure provides a different perspective on how well an IR system retrieves relevant documents.

Precision and Recall

Precision is defined as the ability to retrieve top-ranked documents that are mostly relevant. Recall is defined as the ability of the search to find all of the relevant items in the corpus. Determining Recall is difficult because the total number of relevant items is sometimes not available. One method to address this is to sample across the database and perform relevance judgment on these items. Another method is to apply different retrieval algorithms to the same database for the same query, taking the aggregate of relevant items as the total relevant set.

Unranked retrieval evaluation: Precision and Recall

The lecture questions whether accuracy should be used for evaluation. Given a query, an engine classifies each document as "Relevant" or "Nonrelevant." The accuracy of an engine is the fraction of these classifications that are correct.

🔑 Definition — Accuracy: (tp + tn) / (tp + fp + fn + tn), where tp = true positives, tn = true negatives, fp = false positives, fn = false negatives.

Accuracy is a commonly used evaluation measure in machine learning classification work. However, it is not a very useful evaluation measure in IR because it treats all documents equally, and in IR, the focus is on retrieving the most relevant documents from a large corpus where most documents are non-relevant. A system that returns no documents could achieve high accuracy if the query has few relevant documents.

Trade-off between Recall and Precision

There is a fundamental trade-off between recall and precision. Typically, when you try to increase recall (by retrieving more documents), precision tends to decrease. Conversely, when you aim for high precision (by being very selective), recall often suffers because you might miss some relevant documents.

💡 Why this matters: Understanding this trade-off is essential for tuning an IR system to meet specific user needs, such as high precision for a focused search or high recall for a comprehensive search.

Computing Recall/Precision Points

For a given query, you produce a ranked list of retrievals. Adjusting a threshold on this ranked list produces different sets of retrieved documents, and therefore different recall/precision measures. To compute recall/precision points, you mark each document in the ranked list that is relevant according to the gold standard. Then, compute a recall/precision pair for each position in the ranked list that contains a relevant document.

📐 Formula: Recall = (Number of relevant items retrieved) / (Total number of relevant items in the corpus) 📐 Formula: Precision = (Number of relevant items retrieved) / (Total number of items retrieved)

Computing Recall/Precision Points: Example 1

The lecture provides a visual example (not fully detailed in text but described conceptually) where a ranked list of documents is assessed against a gold standard. For each relevant document found at a given rank, recall (cumulative relevant found / total relevant) and precision (cumulative relevant found / rank) are calculated. This creates a series of points that can be plotted to show how precision changes as recall increases.

⭐ Key Takeaways

The most critical concepts from this lecture are the definitions of precision and recall and their trade-off. Accuracy is rejected for IR because it is misleading in large, imbalanced corpora. Computing recall/precision points involves evaluating a ranked list against a gold standard, marking relevant documents, and calculating pairs at each relevant rank. Students must understand that recall is difficult to measure due to unknown total relevant items. The listed evaluation measures, including F-measure and NDCG, are essential for comprehensive IR system benchmarking.

🧠 Quick Revision Questions

1. What are the two main evaluation measures for unranked retrieval discussed in the lecture?
2. Why is accuracy not a useful evaluation measure for Information Retrieval?
3. What is the fundamental trade-off between recall and precision?
4. How do you compute a recall/precision pair for a position in a ranked list?
5. What are two methods suggested for determining the total number of relevant items when it is not available?

📘 Lecture 26 — Precision and Recall

📖 Overview: This lecture explores the fundamental evaluation metrics used in information retrieval systems: precision and recall. It covers how to compute these metrics, interpolate recall/precision curves, and interpret system performance through various derived measures like the F-measure and E-measure, which are essential for comparing and optimizing search engines.

🗂️ Topics Covered

The lecture covers computing recall/precision points with examples, interpolating recall/precision curves, average recall/precision curves for system evaluation across multiple queries, R-Precision, Precision@K, the F-Measure (harmonic mean of recall and precision), and the E-Measure (a parameterized variant of F-Measure that allows weighting emphasis between precision and recall).

📝 Lecture Summary

Computing Recall/Precision Points: Example 1 & 2

To evaluate an IR system, we compute recall and precision at various points in the ranked list of retrieved documents. Recall measures the proportion of relevant documents retrieved, while precision measures the proportion of retrieved documents that are relevant. These points are calculated by examining the ranked output and noting the recall and precision values at each position where a relevant document is found.

🔑 Definition — Recall: The fraction of relevant documents that have been retrieved out of all relevant documents in the collection. 🔑 Definition — Precision: The fraction of retrieved documents that are relevant out of all documents retrieved.

📐 Formula:

• Recall = (Number of relevant documents retrieved) / (Total number of relevant documents in collection)
• Precision = (Number of relevant documents retrieved) / (Total number of documents retrieved)

📌 Example: For a query with 5 relevant documents (R=5), if the system returns 10 documents and 4 of them are relevant, then Precision = 4/10 = 0.4 and Recall = 4/5 = 0.8.

Interpolating a Recall/Precision Curve

Interpolation is used to create a smooth recall/precision curve by estimating precision values at standard recall levels (typically 0.0, 0.1, 0.2, ..., 1.0). This allows comparison across different queries or systems. The standard interpolation method assigns the maximum precision observed at or beyond a given recall level.

🔑 Definition — Interpolation: A technique to estimate precision values at standard recall points by taking the maximum precision achieved at any recall level greater than or equal to the target recall level.

📌 Example 1: If at recall levels 0.2 and 0.4 we have precisions 0.8 and 0.6 respectively, the interpolated precision at recall 0.1 would be 0.8 (maximum precision at or above 0.1).

📌 Example 2: For a system with computed points: (0.0, 1.0), (0.2, 0.75), (0.4, 0.5), (1.0, 0.25), the interpolated precision at recall 0.3 becomes max(0.5, 0.25) = 0.5.

Average Recall/Precision Curve

To evaluate overall system performance across a large set of queries, we compute the average precision at each standard recall level. This creates an average recall/precision curve that represents typical system behavior, smoothing out variations from individual queries.

🔑 Definition — Average Precision: The mean of precision values obtained at each standard recall level across all queries in the test set.

📌 Why this matters: The curve closest to the upper right-hand corner of the graph indicates the best performance, as it shows high precision across all recall levels.

📌 Sample RP Curve for CF Corpus: The curve typically shows high precision at low recall levels, decreasing as recall increases. A system with a curve that remains high across recall levels is superior.

R-Precision

R-Precision is precision measured at the R-th position in the ranked results, where R is the total number of relevant documents for the query. This metric provides a single-point evaluation that balances recall and precision considerations.

🔑 Definition — R-Precision: The precision at rank position R, where R is the total number of relevant documents for the query.

📐 Formula: R-Precision = (Number of relevant documents in top R results) / R

📌 Example: If a query has 10 relevant documents (R=10), and among the top 10 results, 7 are relevant, then R-Precision = 7/10 = 0.7.

Precision@K

Precision@K (P@K) measures precision at a fixed rank position K, regardless of how many relevant documents exist. This is particularly useful in web search where users typically only look at the top few results (e.g., top 10 or top 20).

🔑 Definition — Precision@K: The proportion of relevant documents among the top K retrieved documents.

📐 Formula: Precision@K = (Number of relevant documents in top K) / K

📌 Example: If a web search returns 20 results and 12 are relevant in the top 20, then Precision@20 = 12/20 = 0.6.

F-Measure

The F-Measure (also called F1-score) combines both recall and precision into a single metric using the harmonic mean. Unlike the arithmetic mean, both recall and precision need to be high for the harmonic mean to be high, making it a balanced evaluation.

🔑 Definition — F-Measure: A single performance metric that combines recall and precision using their harmonic mean.

📐 Formula: F = 2 × (Precision × Recall) / (Precision + Recall)

📌 Why this matters: The harmonic mean penalizes extreme values more than the arithmetic mean. For example, if Precision=1.0 and Recall=0.0, the arithmetic mean is 0.5 but the harmonic mean is 0.0, correctly indicating poor performance.

E Measure (Parameterized F Measure)

The E Measure is a variant of the F-Measure that allows weighting emphasis on either precision or recall through a parameter β (beta). This provides flexibility for applications where one metric is more important than the other.

🔑 Definition — E Measure: A parameterized version of the F-Measure that allows controlling the trade-off between precision and recall.

📐 Formula: E = (1 + β²) × (Precision × Recall) / (β² × Precision + Recall)

📌 Parameter Interpretation:

• β = 1: Equal weight to precision and recall (E = F)
• β > 1: Weight recall more heavily (emphasizes finding all relevant documents)
• β < 1: Weight precision more heavily (emphasizes finding only relevant documents)

📌 Example: For a medical diagnosis system with β = 0.5 (emphasizing precision to avoid false positives), if Precision=0.8 and Recall=0.6, then E = (1+0.25) × (0.48) / (0.25×0.8 + 0.6) = 1.25 × 0.48 / 0.8 = 0.75.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) Precision and recall form the foundation of IR evaluation—precision measures accuracy of results while recall measures completeness. (2) Interpolation creates standardized recall/precision curves by taking maximum precision at or beyond each recall level, enabling fair system comparison. (3) Average recall/precision curves across multiple queries provide a robust evaluation of overall system performance, with the best system having a curve closest to the upper-right corner. (4) Specialized metrics like R-Precision, Precision@K, F-Measure, and E-Measure offer different perspectives for evaluation depending on the application needs. (5) The E-Measure with parameter β allows flexible weighting between precision and recall, making it adaptable to different search scenarios.

🧠 Quick Revision Questions

1. How do you compute precision and recall at a given point in a ranked retrieval list, and what do these metrics represent differently?

2. What is the standard interpolation method for recall/precision curves, and why must you use the maximum precision at or beyond a given recall level?

3. How is the average recall/precision curve constructed across multiple queries, and what does a curve in the upper-right corner indicate about system performance?

4. What is the difference between R-Precision and Precision@K, and when would you choose one over the other?

5. How does the E-Measure differ from the F-Measure, and what happens to the emphasis when β is set to 0.5 versus 2.0?

📘 Lecture 27 — Mean Average Precision, Non Binary Relevance, DCG, NDCG

📖 Overview: This lecture covers advanced evaluation metrics for information retrieval systems that go beyond simple precision and recall. It introduces the Mean Average Precision (MAP) for evaluating ranked retrieval results, Mean Reciprocal Rank (MRR) for systems with a single relevant item, and most importantly, graded relevance metrics like Cumulative Gain (CG), Discounted Cumulative Gain (DCG), and Normalized Discounted Cumulative Gain (NDCG) that handle non-binary relevance judgments. These metrics are essential for evaluating modern search engines where relevance is not simply binary.

🗂️ Topics Covered

The lecture covers Mean Average Precision and how it computes average precision across multiple recall points; Mean Reciprocal Rank which measures the rank position of the first relevant document; the concept of Non-Binary Relevance where documents have varying degrees of relevance; Cumulative Gain as a simple sum of relevance scores; Discounted Cumulative Gain which reduces the contribution of documents found at lower ranks; and Normalized Discounted Cumulative Gain which standardizes DCG scores against an ideal ranking for cross-query comparison.

📝 Lecture Summary

Mean Average Precision (MAP)

Average Precision is the average of the precision values calculated at each point where a relevant document is retrieved. The computation considers only the ranks at which relevant documents appear. For example, if in a search ranking, relevant documents appear at positions 1, 2, 4, 6, 11, and 26, the precision at each of these points is calculated (1.0 at rank 1, 1.0 at rank 2, 0.75 at rank 4, 0.667 at rank 6, 0.38 at rank 11, and 0 at rank 26 because the last document is not retrieved), and these are averaged: (1 + 1 + 0.75 + 0.667 + 0.38 + 0)/6 = 0.633.

In another example with relevant documents at positions 1, 3, 5, 8, 9, and 18, the precisions are 1.0, 0.667, 0.6, 0.5, 0.556, and 0.429, giving an average of (1 + 0.667 + 0.6 + 0.5 + 0.556 + 0.429)/6 = 0.625. Mean Average Precision (MAP) is then the average of these average precision values across a set of queries. If a relevant document never gets retrieved, its corresponding precision is assumed to be zero.

💡 Why this matters: MAP uses macro-averaging, meaning each query counts equally regardless of how many relevant documents it has. MAP is perhaps the most commonly used evaluation measure in research papers. However, it assumes the user is interested in finding many relevant documents for each query, which may not always be true for web search where users often want just one good result. MAP also requires many relevance judgments in the text collection, making it expensive to compute.

🔑 Definition — Average Precision: The average of precision values computed at each point where a relevant document is retrieved in a ranked list. 📐 Formula: AP = (sum of precision at each relevant rank) / (total number of relevant documents) 📌 Example: For a query with 6 relevant documents retrieved at ranks 1,2,4,6,11,26: AP = (1.0 + 1.0 + 0.75 + 0.667 + 0.38 + 0)/6 = 0.633

Mean Reciprocal Rank

Mean Reciprocal Rank (MRR) focuses on the rank position K of the first relevant document retrieved. This is particularly useful when users are typically looking for a single relevant result, such as in question answering or navigational queries where the user wants the specific website. The Reciprocal Rank for a single query is calculated as 1/K. The Mean Reciprocal Rank (MRR) is then the average of these reciprocal rank scores across multiple queries.

🔑 Definition — Mean Reciprocal Rank (MRR): The average of the reciprocal ranks of the first relevant document across multiple queries. 📐 Formula: MRR = (1/N) * sum(1 / rank_of_first_relevant_doc) for N queries 📌 Example: If for query 1 the first relevant doc is at rank 2 (RR=1/2=0.5), for query 2 at rank 1 (RR=1/1=1.0), and for query 3 at rank 5 (RR=1/5=0.2), then MRR = (0.5 + 1.0 + 0.2)/3 = 0.567

Non-Binary Relevance

Documents are rarely entirely relevant or non-relevant to a query, which is why Non-Binary Relevance assigns graded relevance judgments rather than simple binary (relevant/not relevant) categories. There are many sources of graded relevance judgments, including using a 5-point scale for relevance, having multiple judges evaluate the same document, and analyzing click distribution and deviation from expected click levels. However, the lecture notes caution that click-through data is not equivalent to true relevance judgments.

🔑 Definition — Non-Binary Relevance: A graded or multi-level relevance judgment system where documents can have varying degrees of relevance to a query, rather than being classified as simply relevant or non-relevant.

Cumulative Gain

Cumulative Gain (CG) is the simplest measure for handling graded relevance. It is calculated by summing the relevance scores of documents at each rank position. The gain is accumulated starting at the top of the ranking and moving downward. For example, if documents at the top 10 positions have relevance scores of 3, 2, 3, 0, 1, 2, 3, 2, 1, 0 on a relevance scale, then the cumulative gain at position 10 would be the sum of all these scores.

🔑 Definition — Cumulative Gain (CG): The sum of the graded relevance values of all documents in a ranked list up to a given rank position. 📐 Formula: CG = sum of relevance scores up to rank k 📌 Example: For relevance scores [3, 2, 3, 0, 1] at ranks 1-5, CG at rank 5 = 3 + 2 + 3 + 0 + 1 = 9

Discounted Cumulative Gain

Discounted Cumulative Gain (DCG) improves upon Cumulative Gain by recognizing that users are less likely to examine documents at lower ranks. DCG uses graded relevance as a measure of usefulness, or gain, from examining a document. The gain is accumulated starting at the top of the ranking but is reduced, or discounted, at lower ranks. The typical discount factor is 1/log(rank) using base 2. With base 2, the discount at rank 4 is 1/2 (because log₂(4) = 2), and at rank 8 it is 1/3 (because log₂(8) = 3). This means a relevant document found at position 4 contributes only half as much to the total score as if it were found at position 1.

💡 Why this matters: Discounting Based on Position reflects real user behavior where users scan results from top to bottom, finding documents lower down less useful even if they are highly relevant. DCG penalizes relevant documents that appear at lower ranks.

🔑 Definition — Discounted Cumulative Gain (DCG): A measure of ranking quality that accumulates gain (relevance) from documents while applying a discount factor that decreases with rank position. 📐 Formula: DCG = sum of (relevance of document at rank i) / log₂(i+1) for all documents up to rank position 📌 Example: For relevance scores [3, 2, 3, 0, 1] at ranks 1-5: DCG = 3/log₂(2) + 2/log₂(3) + 3/log₂(4) + 0/log₂(5) + 1/log₂(6) = 3/1 + 2/1.585 + 3/2 + 0/2.322 + 1/2.585 = 3 + 1.262 + 1.5 + 0 + 0.387 = 6.149

Normalized Discounted Cumulative Gain (NDCG)

Normalized Discounted Cumulative Gain (NDCG) addresses the challenge of comparing DCG values across different queries, which may have different numbers of relevant documents and different relevance distributions. To make comparisons meaningful, DCG values are normalized so that an ideal ranking would have an NDCG of 1.0. The ideal ranking is created by sorting all documents in the collection by their relevance scores in descending order, so the most relevant documents appear first. The NDCG is then calculated as the ratio of the actual DCG to the ideal DCG for the same query.

💡 Why this matters: NDCG allows fair comparison of search system performance across queries with different characteristics. A perfect ranking gets a score of 1.0, and real rankings get scores between 0 and 1.

🔑 Definition — Normalized Discounted Cumulative Gain (NDCG): DCG normalized by the ideal DCG (DCG of a perfectly ranked list) to produce a score between 0 and 1. 📐 Formula: NDCG = DCG / Ideal DCG 📌 Example: If a query has actual DCG of 6.149 and the ideal DCG (when documents are sorted by descending relevance) is 8.912, then NDCG = 6.149/8.912 = 0.690, meaning the ranking achieves 69% of the ideal performance.

⭐ Key Takeaways

The most critical concept for exams is understanding that MAP handles binary relevance and averages precision across all relevant documents, while MRR only considers the first relevant document's rank. For graded relevance, CG simply adds up relevance scores, DCG applies a logarithmic discount based on rank position to reflect diminishing user attention at lower ranks, and NDCG normalizes DCG against an ideal ranking to enable cross-query comparison. The discount factor for DCG is typically 1/log₂(rank), with base 2. Students must memorize that NDCG always falls between 0 and 1, with 1.0 representing a perfect ranking. The key distinction is that MAP is for binary relevance and macro-averaging across queries, while DCG/NDCG handle graded relevance with position-based discounting.

🧠 Quick Revision Questions

1. How does the Mean Average Precision (MAP) handle relevant documents that are never retrieved by the search system?
2. What is the discount factor used in Discounted Cumulative Gain (DCG) and why does it use a logarithmic function?
3. Why is Normalized Discounted Cumulative Gain (NDCG) preferred over raw DCG when comparing search engine performance across different queries?
4. What is the fundamental difference between Mean Average Precision (MAP) and Mean Reciprocal Rank (MRR) in terms of what each metric measures?
5. Why does the lecture caution against using click-through data as a direct substitute for relevance judgments in non-binary relevance evaluations?

📘 Lecture 28 — Using User Clicks

📖 Overview: This lecture explores how user click behavior can be used to evaluate and improve Information Retrieval systems. It covers methods for extracting pairwise relevance judgments from click data, metrics for comparing rankings, and practical techniques like interleaved experiments and A/B testing that large search engines use to measure user satisfaction.

🗂️ Topics Covered

The lecture covers what clicks tell us about relevance, relative vs absolute ratings, pairwise relative ratings derived from user clicks, interleaved documents as a method for obtaining pairwise orderings, the Kendall tau distance for comparing rankings, critique of additive relevance in favor of marginal relevance, the Kappa measure for inter-judge agreement, and A/B testing for evaluating search engine innovations.

📝 Lecture Summary

What do clicks tell us?

User clicks on search results provide implicit feedback about relevance. However, clicks are not absolute relevance judgments; they are relative. For a given query, a user clicking on Result A but not Result B suggests A is preferred, but we cannot conclude that the unclicked result is irrelevant.

💡 Why this matters: Clicks are abundant and free, unlike manual relevance judgments, but they need careful interpretation.

Relative vs absolute ratings

Absolute ratings (e.g., "Result 1 is relevant") are hard to derive from clicks with certainty. For example, it is difficult to conclude Result1 > Result3 from click data alone. However, relative judgments are more reliable: if a user clicks Result3 but not Result2, we can probably conclude Result3 > Result2.

🔑 Definition — Relative rating: A judgment that one document is better than another for a given query, without requiring an absolute relevance label.

Pairwise relative ratings

These are pairs of the form: DocA is better than DocB for a query. Importantly, this does not mean DocA is relevant to the query — only that it is preferred over DocB. Pairwise preferences shift evaluation from per-doc relevance assessments to conformance with historical pairwise preferences recorded from user clicks.

A critical caution: Do not learn and test on the same ranking algorithm. If you learn historical clicks from one search engine (e.g., "nozama") and then compare another engine (e.g., "Sergey") against that history, the evaluation is biased.

Interleaved docs (Joachims 2002)

One approach to obtain pairwise orderings is to interleave results from two ranking engines A and B. Users are shown a combined list where results from both engines are mixed. Their clicks then implicitly indicate which engine's results are preferred, generating pairwise comparisons.

Kendall tau distance

This metric measures the agreement between two rankings. Let ( X ) be the number of agreements (pairs in the same order) between a ranking A and a reference ranking P, and ( Y ) be the number of disagreements. The Kendall tau distance is:

📐 Formula: Kendall tau = (X - Y) / (X + Y)

This value ranges from -1 to +1. A value of +1 means perfect agreement, 0 means random agreement, and -1 means complete disagreement.

📌 Example: Say P = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)} and A = (1,3,2,4). P lists all 6 possible pairs in the correct order. For A: pairs (1,2), (1,3), (1,4), (3,2), (3,4), (2,4). Compared to P, we find X=5 agreements and Y=1 disagreement (the pair (3,2) is reversed). Then Kendall tau = (5-1)/(5+1) = 4/6 = 0.667.

Critique of additive relevance

Traditional evaluation assumes additive relevance: the total relevance of a result list is the sum of individual document relevance scores. This is flawed because:

• Relevance vs Marginal Relevance: A document can be redundant even if it is highly relevant (e.g., duplicates, same information from different sources).
• Marginal relevance — the new information a document adds beyond what the user has already seen — is a better measure of utility.
• However, evaluating marginal relevance is harder because it requires considering the entire set of documents shown together.
• This pushes us to assess a slate of results (the whole list) rather than summing individually assessed relevance scores.
• One method: raters are shown two result lists and asked to pick the better one — reminiscent of the interleaved doc idea.

Kappa measure for inter-judge (dis)agreement

The Kappa measure quantifies agreement among judges for categorical judgments, correcting for chance agreement.

📐 Formula: Kappa = [P(A) – P(E)] / [1 – P(E)]

• P(A) = proportion of time judges agree
• P(E) = what agreement would be by chance

Interpretation: Kappa = 0 for chance agreement, 1 for total agreement. Kappa > 0.8 is considered good agreement; 0.67 < Kappa < 0.8 allows "tentative conclusions" (Carletta '96). For more than 2 judges, average pairwise kappas are used.

📌 Example: From the contingency table in the lecture, with 400 total judgments:

• P(A) = 370/400 = 0.925
• P(nonrelevant) = (10+20+70+70)/800 = 0.2125
• P(relevant) = (10+20+300+300)/800 = 0.7878
• P(E) = (0.2125)^2 + (0.7878)^2 = 0.665
• Kappa = (0.925 – 0.665) / (1 – 0.665) = 0.260 / 0.335 = 0.776

This value (0.776) falls in the "tentative conclusions" range.

A/B testing

A/B testing is a practical evaluation method for testing a single innovation in a large search engine.

• Prerequisite: You have a large search engine up and running.
• Have most users use the old system.
• Divert a small proportion of traffic (e.g., 1%) to the new system that includes the innovation.
• Evaluate with an automatic measure like clickthrough on the first result (percentage of users that click on the top result or any result on the first page).
• This directly shows if the innovation improves user happiness.
• Probably the evaluation methodology large search engines trust most.
• In principle less powerful than multivariate regression analysis, but easier to understand and implement.

⭐ Key Takeaways

User clicks provide abundant but noisy relative relevance judgments — we can conclude Document A is preferred to B, but not that A is relevant. To avoid bias, pairwise preferences should be learned from one ranking algorithm and tested on a different one, often using interleaved experiments. The Kendall tau distance quantifies agreement between rankings, while additive relevance is critiqued because it ignores redundancy; marginal relevance and slate-based evaluation are superior but harder. The Kappa measure corrects for chance in inter-judge agreement, and A/B testing with clickthrough metrics is the gold standard for evaluating innovations in large-scale search engines.

🧠 Quick Revision Questions

1. Why is it harder to conclude "Result1 > Result3" than "Result3 > Result2" from click data?
2. What is the key caution when using historical pairwise preferences from clicks to compare two ranking algorithms?
3. In the Kendall tau example, why was the pair (3,2) considered a disagreement with the reference P?
4. Why is marginal relevance considered a better measure of utility than additive relevance, and what makes it harder to evaluate?
5. In the Kappa example, what does a Kappa value of 0.776 tell us about the agreement between the two judges?

📘 Lecture 29 — Cosine Ranking

📖 Overview: This lecture focuses on efficient computation of cosine-based ranking for information retrieval. It covers strategies to speed up the ranking process by reducing the number of cosine computations and dimensions, while maintaining high-quality results for top-K document retrieval.

🗂️ Topics Covered

The lecture covers computing cosine-based ranking with methods to speed up the process, efficient cosine ranking as a K-nearest neighbor problem, computing the K largest cosines using selection vs. sorting, using a heap for selecting top K documents, understanding cosine similarity as a proxy for user satisfaction, generic approach of pruning non-contenders, index elimination techniques, considering high-idf query terms only, and considering documents containing many query terms.

📝 Lecture Summary

Computing cosine-based ranking

Speeding up cosine ranking involves reducing the number of cosine computations. This can be achieved through methods like union of term-wise candidates, sampling and pre-grouping, and reducing the number of dimensions using techniques like random projection and latent semantic indexing. The goal is to efficiently find the most relevant documents without computing all possible cosine similarities.

Efficient cosine ranking

This approach effectively solves the K-nearest neighbor problem for a query vector. In general, high-dimensional spaces make this problem computationally difficult. However, for short queries, it becomes solvable because standard inverted indexes can efficiently identify candidate documents containing query terms.

Computing the K largest cosines: selection vs. sorting

Typically, we want to retrieve the top K docs in the cosine ranking, not to order all documents. This raises the question: can we pick off the K docs with the highest cosines without full sorting? Let J represent the number of documents with nonzero cosines. We seek the K best of these J documents. 📐 Formula: J = number of docs with nonzero cosines → K = number of top docs we want from J.

Measuring the distance between 2 vectors

Distance between two vectors in V-dimensional space is based on the angle between them, assuming each vector has unit length. In 2D, this is visualized as angles on a circle, where the cosine of the angle θ directly measures similarity. 🔑 Definition — Cosine similarity: a measure of similarity between two vectors calculated as the cosine of the angle between them, ranging from 0 to 1 for positive vectors, where 1 indicates identical direction.

Use heap for selecting top K

A heap is a binary tree where each node's value is greater than the values of its children (max-heap). Building a heap takes 2J operations, and each of K winners is read off in 2log J steps. For example, with J=1,000,000 and K=100, this is about 10% of the cost of sorting. The heap building process takes O(n) time. Deleting the max element takes constant time, but fixing the rest of the heap takes log(n) time. With n replaced by J, building takes O(J), each deletion takes log(J) time, and for K operations we need K log(J) operations.

Cosine similarity is only a proxy

The user has a task and a query formulation. Cosine similarity matches documents to the query, but it is only a proxy for user happiness. If we retrieve a list of K documents "close" to the top K by cosine measure, that should be acceptable. 💡 Why this matters: The goal is not perfect ranking but good enough retrieval that satisfies the user's information need.

Generic approach

Find a set A of contenders, where K < |A| << N (N is total documents). Set A does not necessarily contain the top K, but has many documents from among the top K. Then return the top K documents in A. This approach prunes non-contenders and is also used for other (non-cosine) scoring functions. Several schemes follow this approach.

Index elimination

The basic cosine computation algorithm only considers documents containing at least one query term. Index elimination takes this further by: only considering high-idf query terms, and only considering documents containing many query terms. 📌 Example: For query "catcher in the rye", only accumulate scores from "catcher" and "rye", ignoring "in" and "the".

High-idf query terms only

For a query such as catcher in the rye, only accumulate scores from catcher and rye. The intuition is that in and the contribute little to the scores and don't alter rank-ordering much. The benefit is that postings of low-idf terms have many documents, so these (many) documents get eliminated from the set A of contenders.

Docs containing many query terms

Any document with at least one query term is a candidate for the top K output list. For multi-term queries, only compute scores for documents containing several of the query terms — for example, at least 3 out of 4. This imposes a "soft conjunction" on queries, as seen on web search engines (early Google). It is easy to implement in postings traversal.

⭐ Key Takeaways

The most critical concept is that computing cosine ranking efficiently requires strategic pruning rather than exhaustive calculation. The heap data structure provides an efficient way to select the top K documents without sorting all candidates, using O(J) to build and O(K log J) to extract winners. Cosine similarity is recognized as a proxy for user satisfaction, not an exact measure of relevance. Index elimination techniques like considering only high-idf terms or requiring documents to contain multiple query terms significantly reduce the candidate set. The generic approach of creating a contender set A with |A| much smaller than N while still capturing most top K documents is the fundamental strategy behind all these methods.

🧠 Quick Revision Questions

1. Why is cosine similarity described as "only a proxy" for user happiness?
2. How does using a heap for selecting top K documents compare in complexity to full sorting?
3. What is the benefit of considering only high-idf query terms in cosine ranking?
4. What does the "soft conjunction" mean in the context of considering docs containing many query terms?
5. What are the two main strategies mentioned for reducing the number of dimensions in cosine ranking?

📘 Lecture 30 — Sampling and pre-grouping

📖 Overview: This lecture covers techniques for efficient information retrieval by pre-computing term-wise candidate lists and using sampling-based pre-grouping methods. These approaches reduce query processing time by narrowing the search space to a small set of promising documents rather than scanning the entire collection.

🗂️ Topics Covered

The lecture examines term-wise candidate preprocessing where each term’s nearest documents are pre-computed and stored as preferred lists. It then discusses storage strategies for these preferred lists and how to handle cases where preferred lists fail to produce enough results. The main focus is on sampling and pre-grouping using leaders and followers, along with general variants that allow multiple leader attachments and recursive construction.

📝 Lecture Summary

Term-wise candidates

Preprocess: Pre-compute, for each term, its k nearest docs.

• Treat each term as a 1-term query.
• Requires lots of preprocessing.
• Result: "preferred list" for each term.

Search:

• For a t-term query, take the union of their t preferred lists — call this set S.
• Compute cosines from the query to only the docs in S, and choose top k.

Preferred List storage

• Store postings in descending order of similarity to the term.
• This would disturb the postings merging, as it won’t be stored in a sorted order of DocID.
• Store separate postings list, which is the preferred list.
• Store the postings in the ascending order of DocID.
• This would keep the merging of posting lists easy.
• Requires extra storage.

Number of Required Results:

• In case the preferred lists are not able to produce required number of top results, go to the normal postings lists.
• Generate estimated number of total results against a query by using total number of postings against the terms.
• Produce top results by using preferred lists.

Sampling and pre-grouping

First run a pre-processing phase:

• Pick √N docs at random: call these leaders.
• For each other doc, pre-compute nearest leader.
• Docs attached to a leader: its followers.
• Likely: each leader has ~ √N followers.

Process a query as follows:

• Given query Q, find its nearest leader L.
• Seek k nearest docs from among L's followers.

💡 Why this matters: This technique dramatically reduces the number of documents that must be scored during query processing, from the entire collection (N documents) to only about √N followers of a single leader.

Why use random sampling:

• Fast
• Leaders reflect data distribution
• Random sampling is computationally efficient and statistically representative.

Visualization: The lecture includes a diagram showing leaders (represented as larger icons) with their followers (smaller icons grouped around each leader), and a query Q with arrows pointing to its nearest leader L.

General variants

• Have each follower attached to a=3 (say) nearest leaders.
• From query, find b=4 (say) nearest leaders and their followers.
• Can recur on leader/follower construction.

💡 Why this matters: Multiple attachments improve recall by ensuring a query’s nearest documents aren’t missed if they’re followers of a leader that isn’t the query’s absolute nearest. Recursive construction allows hierarchical partitioning for even faster search.

⭐ Key Takeaways

The lecture presents two main strategies for efficient approximate nearest neighbor search in information retrieval. Term-wise candidates pre-compute preferred lists for each term, requiring union operations at query time and extra storage. Sampling and pre-grouping randomly selects √N documents as leaders, assigns each remaining document to its nearest leader as a follower, and at query time only searches followers of the query’s nearest leader. General variants improve this by attaching each follower to multiple nearest leaders and finding multiple nearest leaders at query time, while recursion enables hierarchical clustering. Both methods dramatically reduce the number of documents that need cosine computations, trading some precision for significant speed gains.

🧠 Quick Revision Questions

1. How many leaders are selected in the sampling and pre-grouping approach, and roughly how many followers does each leader typically have?
2. What is the difference between storing a preferred list in descending order of similarity versus ascending order of DocID?
3. When would a retrieval system need to fall back from using preferred lists to using normal posting lists?
4. In the general variant with multiple attachments, what do the parameters a=3 and b=4 represent?
5. Why is random sampling preferred over other methods for selecting leaders in the pre-grouping approach?

📘 Lecture 31 — Dimensionality reduction

📖 Overview: This lecture explores techniques for reducing the number of dimensions in vector space representations of documents, which speeds up cosine similarity computations and improves retrieval efficiency. It covers two main approaches—random projection and Latent Semantic Indexing (LSI)—and explains the underlying linear algebra concepts, including Singular-Value Decomposition (SVD) and eigenvalue analysis.

🗂️ Topics Covered

The lecture covers two dimensionality reduction methods: random projection onto fewer axes and its computation, and Latent Semantic Indexing (LSI) which is data-dependent. It then reviews notions from linear algebra including matrix rank, eigenvectors, eigenvalues, and Singular-Value Decomposition (SVD). Finally, it discusses dimension reduction by zeroing out all but the largest eigenvalues, document-document similarities, and query processing.

📝 Lecture Summary

Dimensionality reduction

What if we could take our vectors and “pack” them into fewer dimensions (say 10000→100) while preserving distances? (Well, almost.) This speeds up cosine computations. Two methods: Random projection and “Latent semantic indexing”.

Random projection onto k<<m axes.

• Choose a random direction x₁ in the vector space.
• For i = 2 to k, choose a random direction xᵢ that is orthogonal to x₁, x₂, ... xᵢ₋₁.
• Project each doc vector into the subspace x₁, x₂, ... xₖ.

Guarantee: With high probability, relative distances are (approximately) preserved by projection. Pointer to precise theorem in Resources.

Computing the random projection

Projecting n vectors from m dimensions down to k dimensions:

• Start with m × n matrix of terms × docs, A.
• Find random k × m orthogonal projection matrix R.
• Compute matrix product W = R × A.
• jth column of W is the vector corresponding to doc j, but now in k << m dimensions.

Cost of computation: This takes a total of kmn multiplications. Expensive - see Resources for ways to do essentially the same thing, quicker.

• Exercise: by projecting from 10000 dimensions down to 100, are we really going to make each cosine computation faster? Size of the vectors would decrease. Will result into smaller postings.

Latent semantic indexing (LSI)

Another technique for dimension reduction. Random projection was data-independent. LSI on the other hand is data-dependent. It eliminates redundant axes and pulls together “related” axes—for example, car and automobile.

Notions from linear algebra: Matrix, vector, matrix transpose and product, rank, eigenvalues and eigenvectors.

The matrix

The matrix
has rank 2: the first two rows are linearly independent, so the rank is at least 2, but all three rows are linearly dependent (the first is equal to the sum of the second and third) so the rank must be less than 3.

• The matrix
  has rank 1: there are nonzero columns. So the rank is positive, but any pair of columns is linearly dependent.

Similarly, the transpose of A has rank 1. Indeed, since the column vectors of A are the row vectors of the transpose of A, the statement that the column rank of a matrix equals its row rank is equivalent to the statement that the rank of a matrix is equal to the rank of its transpose, i.e., rk(A) = rk(Aᵀ).

Singular-Value Decomposition: Recall m × n matrix of terms × docs, A. A has rank r ≤ m,n.

• Define term-term correlation matrix T = AAᵀ
• Aᵀ denotes the matrix transpose of A.
• T is a square, symmetric m × m matrix.

Eigenvectors: Denote by P the m × r matrix of eigenvectors of T. Denote by R the n × r matrix of eigenvectors of D. It turns out A can be expressed (decomposed) as A = PQRᵀ. Q is a diagonal matrix with the eigenvalues of AAᵀ in sorted order.

🔑 Definition — Eigenvectors and Eigenvalues: For a square matrix, eigenvectors are non-zero vectors that, when multiplied by the matrix, result in a scalar multiple of themselves. The scalar is called the eigenvalue.

💡 Why this matters: This decomposition allows us to identify which dimensions capture the most variance in the document-term relationships, enabling effective compression.

Dimension reduction

For some s << r, zero out all but the s biggest eigenvalues in Q. Denote by Qₛ this new version of Q. Typically s in the hundreds while r could be in the (tens of) thousands. Let Aₛ = P Qₛ Rᵀ. Turns out Aₛ is a pretty good approximation to A.

Guarantee: Relative distances are (approximately) preserved by projection. Of all m × n rank s matrices, Aₛ is the best approximation to A. Pointer to precise theorem in Resources.

Doc-doc similarities: Aₛ Aₛᵀ is a matrix of doc-doc similarities: the (j,k) entry is a measure of the similarity of doc j to doc k.

Semi-precise intuition: We accomplish more than dimension reduction here:

• Docs with lots of overlapping terms stay together
• Terms from these docs also get pulled together.
• Thus car and automobile get pulled together because both co-occur in docs with tires, radiator, cylinder, etc.

Query processing

View a query as a (short) doc: call it row 0 of Aₛ. Now the entries in row 0 of Aₛ Aₛᵀ give the similarities of the query with each doc. Entry (0,j) is the score of doc j on the query. Exercise: fill in the details of scoring/ranking.

• LSI is expensive in terms of computation...
• Randomly choosing a subset of documents for dimensional reduction can give a significant boost in performance.

⭐ Key Takeaways

The two primary methods for dimensionality reduction in information retrieval are random projection (data-independent, fast, preserves distances with high probability) and Latent Semantic Indexing (data-dependent, uses SVD to capture term co-occurrence patterns). Random projection reduces dimensions by projecting vectors onto a random k-dimensional subspace, requiring kmn multiplications. LSI reduces dimensions by zeroing out all but the s largest eigenvalues in the singular-value decomposition of the term-document matrix, with s typically in the hundreds. LSI not only reduces dimensions but also semantically pulls together related terms like car and automobile, improving query-document matching. Both methods preserve relative distances approximately, but LSI requires expensive SVD computation, though performance can be boosted by using a random subset of documents.

🧠 Quick Revision Questions

1. What are the two main methods for dimensionality reduction covered in this lecture, and how do they differ in their data dependence?
2. In random projection, what is the cost of projecting n vectors from m dimensions down to k dimensions, and what is the formula for the matrix product?
3. In LSI, what is the role of eigenvalues and the diagonal matrix Q in the Singular-Value Decomposition (SVD) of the term-document matrix A?
4. How does the dimension reduction step work in LSI: what does Aₛ = P Qₛ Rᵀ represent, and what is the guarantee about Aₛ?
5. How does LSI pull together related terms like "car" and "automobile," and how is a query processed using the resulting doc-doc similarity matrix?

📘 Lecture 32 — Web Search

📖 Overview: This lecture explores the evolution and challenges of web search, from the early days of the World Wide Web to modern search engines. It covers the historical development of browsers and search engines, the unique challenges the web poses for information retrieval, the graph structure of the web, and the business models that power web search.

🗂️ Topics Covered

The lecture covers the World Wide Web, its pre-history, and the history of web browsers and search engines. It then addresses the specific challenges the web presents for information retrieval, including distributed, volatile, and large-volume data. The graph structure of the web is analyzed using the Bowtie model, and Zipf's law is applied to web page characteristics. The lecture concludes with a discussion of manual hierarchical web taxonomies and various business models for web search.

📝 Lecture Summary

The World Wide Web

The World Wide Web was developed by Tim Berners-Lee in 1990 at CERN to organize research documents available on the Internet. It combined the idea of documents available by FTP with the concept of hypertext to link documents. Berners-Lee developed the initial HTTP network protocol, URLs, HTML, and the first “web server.”

Web Pre-History

The concept of hypertext was first developed by Ted Nelson in 1965. Doug Engelbart invented the mouse and built the first implementation of hypertext in the late 1960’s at SRI. The ARPANET was developed in the early 1970’s. While the basic technology was in place in the 1970’s, it took the PC revolution and widespread networking to inspire the web and make it practical.

Web Browser History

Early browsers like Erwise and ViolaWWW were developed in 1992. In 1993, Marc Andreessen and Eric Bina at UIUC NCSA developed the Mosaic browser and distributed it widely. Andreessen joined with James Clark to form Mosaic Communications Inc. in 1994, which became Netscape. Microsoft later licensed the original Mosaic from UIUC to build Internet Explorer in 1995.

Search Engine Early History

By the late 1980’s, many files were available by anonymous FTP. In 1990, Alan Emtage of McGill Univ. developed Archie (short for “archives”), which assembled lists of files available on many FTP servers and allowed regex search of these file names. In 1993, Veronica and Jughead were developed to search names of text files available through Gopher servers.

Web Search History

In 1993, early web robots (spiders) were built to collect URL’s, including Wanderer, ALIWEB, and the WWW Worm. In 1994, Stanford grad students David Filo and Jerry Yang started manually collecting popular web sites into a topical hierarchy called Yahoo. Later that year, Brian Pinkerton developed WebCrawler as a class project, and Fuzzy Maudlin developed Lycos, which was the first to use a standard IR system and index a large set of pages. In late 1995, DEC developed Altavista, which supported boolean operators, phrases, and "reverse pointer" queries.

Web Search Recent History

In 1998, Larry Page and Sergey Brin, Ph.D. students at Stanford, started Google. Its main advance was the use of link analysis to rank results based partially on authority.

Web Challenges for IR

The web presents several challenges for information retrieval:

• Distributed Data: Documents are spread over millions of different web servers.
• Volatile Data: Many documents change or disappear rapidly (e.g., dead links).
• Large Volume: There are billions of separate documents.
• Unstructured and Redundant Data: No uniform structure exists, with HTML errors and up to 30% (near) duplicate documents.
• Quality of Data: There is no editorial control, leading to false information, poor quality writing, and typos.
• Heterogeneous Data: Multiple media types (images, video, VRML), languages, and character sets are present.

Zipf’s Law on the Web

Zipf's Law applies to the web in several ways:

• Number of in-links/out-links to/from a page has a Zipfian distribution.
• Length of web pages has a Zipfian distribution.
• Number of hits to a web page has a Zipfian distribution.

Manual Hierarchical Web Taxonomies

The Yahoo approach used human editors to assemble a large hierarchically structured directory of web pages (http://www.yahoo.com/). The Open Directory Project (dmoz.org) is a similar approach based on the distributed labor of volunteer editors, where “net-citizens provide the collective brain.” It was started by Netscape and is used by most other search engines.

Business Models for Web Search

Several business models are used for web search:

• Advertisers pay for banner ads on the site that do not depend on a user’s query.
• CPM (Cost Per Mille): Pay for each ad display (thousand impressions).
• CPC (Cost Per Click): Pay only when a user clicks on an ad.
• CTR (Click Through Rate): Fraction of ad impressions that result in clicks throughs. CPC = CPM / (CTR * 1000)
• CPA (Cost Per Action/Acquisition): Pay only when a user actually makes a purchase on the target site.
• Advertisers bid for keywords. Ads for the highest bidders are displayed when a user query contains a purchased keyword.
• PPC (Pay Per Click): CPC for bid word ads (e.g., Google AdWords).

⭐ Key Takeaways

The web evolved from Tim Berners-Lee's initial system through key milestones like the Mosaic browser and the early search engines such as Archie, Yahoo, and Lycos. Google's major innovation was its use of link analysis (PageRank) to rank results by authority, moving beyond simple text matching. The web presents unique challenges for IR, including distributed, volatile, massive, unstructured, low-quality, and heterogeneous data. The graph structure of the web is not arbitrary; it follows the Bowtie model and exhibits Zipfian distributions for links, page length, and traffic. Finally, web search is funded by advertising business models like CPM, CPC, and CPA, with keyword bidding being a central mechanism.

🧠 Quick Revision Questions

1. Who developed the World Wide Web, and what core technologies did they create?
2. What was the main innovation that Google introduced for web search ranking?
3. List four specific challenges that the web presents for information retrieval.
4. According to the lecture, what characteristics of the web follow a Zipfian distribution?
5. Explain the difference between CPM, CPC, and CPA in the context of web search advertising.

📘 Lecture 33 — Spidering

📖 Overview: This lecture focuses on the fundamental techniques for web crawling, also known as spidering, which is the process by which search engines automatically discover and download web pages. It covers the essential protocols and strategies that crawlers must follow to be polite, robust, and efficient, including search strategies for traversing the web graph, mechanisms for avoiding duplicate pages, and methods for respecting website owner restrictions via the Robots Exclusion Protocol and META tags.

🗂️ Topics Covered

This lecture covers web search using IR, defines spiders (robots/bots/crawlers) and their basic operations, outlines what any crawler must do (polite and robust) and what any crawler should do (distributed, scalable, high-quality). It explains search strategies comparing breadth-first and depth-first search, presents the basic crawl architecture including the spidering algorithm and queueing strategy, covers avoiding page duplication, and details methods for restricting spidering through Robot Exclusion Protocol and Robots META Tags.

📝 Lecture Summary

Spiders (Robots/Bots/Crawlers)

Spiders are automated programs that systematically browse the World Wide Web to discover and download web pages. They start with a comprehensive set of root URLs from which to begin the search. The spider then follows all links on these pages recursively to find additional pages. As novel pages are encountered, they are indexed, typically in an inverted index. Spiders may also allow users to directly submit pages to be indexed, which then become part of the crawl starting set.

What any crawler must do

A crawler must be Polite by respecting both implicit and explicit politeness considerations. This includes only crawling allowed pages and respecting the robots.txt file. A crawler must also be Robust, meaning it must be immune to spider traps and other malicious behavior from web servers that could cause it to get stuck or waste resources.

What any crawler should do

An ideal crawler should be capable of distributed operation, designed to run on multiple distributed machines. It should be scalable, designed to increase the crawl rate simply by adding more machines. It must have high performance/efficiency to permit full use of available processing and network resources. Additionally, it should fetch pages of higher quality first, support continuous operation by fetching fresh copies of previously fetched pages, and be extensible to adapt to new data formats and protocols.

Search Strategy Trade-Off’s

There is a fundamental trade-off between breadth-first and depth-first search strategies. Breadth-first explores uniformly outward from the root page but requires memory of all nodes on the previous level, which is exponential in depth, making it the standard spidering method. Depth-first requires memory of only depth times branching-factor (linear in depth) but can get "lost" pursuing a single thread. Both strategies are implementable using a queue of links (URLs).

🔑 Definition — Breadth-first search: Explores all nodes at the present depth level before moving on to nodes at the next depth level. 🔑 Definition — Depth-first search: Explores as far as possible along each branch before backtracking.

Avoiding Page Duplication

Since the web is a graph, not a tree, a crawler must detect when it is revisiting a page that has already been spidered. It must efficiently index visited pages to allow rapid recognition. One method is to index pages using the URL as a key, using data structures like a tree index (e.g., trie) or a hashtable. URLs must be canonicalized (e.g., deleting ending "/") to treat equivalent URLs as the same page. However, this method does not detect duplicated or mirrored pages with different URLs. An alternative is to index pages using textual content as a key, but this requires first downloading the page before determining if it is a duplicate.

Spidering Algorithm

The spidering algorithm is a step-by-step process for downloading and indexing web pages:

1. Initialize a queue (Q) with an initial set of known URLs.
2. Until the queue is empty or a page/time limit is exhausted:
   • Pop a URL, L, from the front of Q.
   • If L is not to an HTML page (e.g., .gif, .jpeg, .ps, .pdf, .ppt...), continue the loop.
   • If L has already been visited, continue the loop.
   • Download page, P, for L.
   • If P cannot be downloaded (e.g., 404 error, robot excluded), continue the loop.
   • Index P (e.g., add to inverted index or store cached copy).
   • Parse P to obtain a list of new links N.
   • Append N to the end of Q.

Queueing Strategy

How new links are added to the queue determines the search strategy. Using FIFO (First-In, First-Out), appending to the end of the queue, gives breadth-first search. Using LIFO (Last-In, First-Out), adding to the front of the queue, gives depth-first search. Heuristically ordering the queue gives a "focused crawler" that directs its search towards "interesting" pages based on specific criteria.

🔑 Definition — Focused crawler: A crawler that uses heuristics to prioritize the fetching of pages that are likely to be of higher quality or relevance to a specific topic.

Restricting Spidering

Spidering can be restricted in several ways: restricting the spider to a particular site by removing links to other sites from the queue; restricting the spider to a particular directory by removing links not in the specified directory; and obeying page-owner restrictions through robot exclusion.

Link Extraction

To follow links, a crawler must find all links in a page and extract their URLs. This includes <a href="URL"> tags and <frame src="URL"> tags. The crawler must also complete relative URLs using the current page's URL. For example, <a href="proj3"> relative to http://www.cs.utexas.edu/users/mooney/ir-course/ becomes http://www.cs.utexas.edu/users/mooney/ir-course/proj3. Another example: <a href="../cs343/syllabus.html"> becomes http://www.cs.utexas.edu/users/mooney/cs343/syllabus.html.

URL Syntax

A URL has the following syntax: <scheme>://<authority><path>?<query>#<fragment>. An authority has the syntax <host>:<port-number>. A query passes variable values from an HTML form and has the syntax <variable>=<value>&<variable>=<value>.... A fragment, also called a reference or ref, is a pointer within the document to a point specified by an anchor tag of the form <A NAME="<fragment>">.

Robot Exclusion

Web sites and pages can specify that robots should not crawl or index certain areas. This involves two components: the Robots Exclusion Protocol, which is a site-wide specification of excluded directories, and the Robots META Tag, which is an individual document tag to exclude indexing or following links.

🔑 Definition — Robots.txt: A file placed at the root of a host's web directory (e.g., http://www.ebay.com/robots.txt) that lists excluded directories for a given robot (user-agent). 📌 Example: To exclude all robots from the entire site, the robots.txt file contains:

User-agent: *
Disallow: /

📌 Example: To exclude specific directories from all robots:

User-agent: *
Disallow: /tmp/
Disallow: /cgi-bin/
Disallow: /users/paranoid/

📌 Example: To exclude a specific robot (e.g., GoogleBot):

User-agent: GoogleBot
Disallow: /

📌 Example: To allow a specific robot while excluding all others:

User-agent: GoogleBot
Disallow:
User-agent: *
Disallow: /

Robots META Tag

This META tag is included in the HEAD section of a specific HTML document. The format is <meta name="robots" content="value">. The content value is a pair of values for two aspects: index | noindex (allow/disallow indexing of this page) and follow | nofollow (allow/disallow following links on this page).

• Special values: all = index,follow; none = noindex,nofollow 📌 Example: <meta name="robots" content="noindex,follow"> — allows following links but does not index the page. 📌 Example: <meta name="robots" content="index,nofollow"> — indexes the page but does not follow its links. 📌 Example: <meta name="robots" content="none"> — neither indexes the page nor follows its links.

⭐ Key Takeaways

The most critical concepts from this lecture for the exam are the fundamental differences between breadth-first and depth-first search strategies for crawling, including their memory requirements and the risk of getting "lost". You must understand the complete spidering algorithm, the role of the queue (FIFO for breadth-first, LIFO for depth-first), and how to canonicalize URLs and avoid page duplication. The two components of the Robot Exclusion protocol—the site-wide robots.txt file and the per-page robots META tag—with their specific syntax and values (User-agent, Disallow, index/noindex, follow/nofollow) are essential. Finally, recognizing spider traps, understanding URL syntax (scheme, authority, path, query, fragment), and being able to complete relative URLs are all examinable skills.

🧠 Quick Revision Questions

1. What are the two mandatory behaviors every crawler must exhibit, and what does each entail?
2. Compare breadth-first and depth-first search strategies in terms of memory requirements and the risk of getting "lost".
3. Explain the difference between the Robots Exclusion Protocol and the Robots META Tag, and provide an example of a robots.txt file that blocks all robots from the entire site.
4. What is the purpose of URL canonicalization, and what is one common example of this process?
5. Describe the spidering algorithm step-by-step, including what happens when a non-HTML file or a page that cannot be downloaded is encountered.

📘 Lecture 34 — Web Crawler

📖 Overview: This lecture focuses on the architecture and operation of web crawlers, essential tools for information retrieval that systematically browse the web to collect pages. It covers crawling politeness, freshness, the Mercator URL frontier scheme, and techniques for detecting duplicate and near-duplicate documents.

🗂️ Topics Covered

The lecture begins with basic crawl architecture and communication between nodes. It then discusses the URL frontier with a focus on politeness and freshness, followed by a detailed explanation of the Mercator scheme including front queues, back queues, and back queue heap. Finally, it covers duplicate document detection, specifically near-duplicate detection using shingles and set intersection.

📝 Lecture Summary

Basic crawl architecture

The lecture introduces the basic architecture of a web crawler. The output of the URL filter at each node is sent to the Dup URL Eliminator of the appropriate node. This ensures that duplicate URLs are removed before crawling.

Communication between nodes

The communication flow involves passing filtered URLs from one node to another for duplicate elimination. This coordination is crucial for efficient distributed crawling.

URL frontier: two main considerations

The URL frontier manages the queue of URLs to be crawled. Two main considerations guide its design:

• Politeness: Do not hit a web server too frequently to avoid overloading it.
• Freshness: Crawl some pages more often than others, e.g., pages (such as News sites) whose content changes often.

💡 Why this matters: These goals may conflict each other. For example, a simple priority queue fails because many links out of a page go to its own site, creating a burst of accesses to that site.

Politeness – challenges

Even if we restrict only one thread to fetch from a host, it can still hit the host repeatedly. A common heuristic is to insert a time gap between successive requests to a host that is much larger than the time for the most recent fetch from that host.

URL frontier: Mercator scheme

The Mercator URL frontier is a sophisticated scheme to handle both politeness and freshness. It uses two sets of queues:

• Front queues: Manage prioritization
• Back queues: Enforce politeness
• Each queue is First-In-First-Out (FIFO)

URLs flow in from the top into the frontier.

Front queues

The Prioritizer assigns to each URL an integer priority between 1 and K and appends the URL to the corresponding queue. Heuristics for assigning priority include:

• Refresh rate sampled from previous crawls
• Application-specific rules (e.g., “crawl news sites more often”)

Back queue invariants

Back queues maintain three invariants:

1. Each back queue is kept non-empty while the crawl is in progress
2. Each back queue only contains URLs from a single host
3. A table is maintained from hosts to back queues

Biased front queue selector

When a back queue requests a URL, the biased front queue selector picks a front queue from which to pull a URL. This choice can be:

• Round robin biased to queues of higher priority
• Some more sophisticated variant
• Randomized

Back queue heap

The back queue heap contains one entry for each back queue. The entry is the earliest time tₑ at which the host corresponding to the back queue can be hit again. This earliest time is determined from:

• Last access to that host
• Any time buffer heuristic we choose

Back queue processing

When a crawler thread seeks a URL to crawl:

1. Extracts the root of the heap
2. Fetches URL at head of corresponding back queue q (look up from table)
3. Checks if queue q is now empty – if so, pulls a URL v from front queues
4. If there’s already a back queue for v’s host, append v to q and pull another URL from front queues, repeat
5. Else add v to q
6. When q is non-empty, create heap entry for it

Number of back queues B

To keep all threads busy while respecting politeness, the Mercator recommendation is three times as many back queues as crawler threads.

Duplicate documents

The web is full of duplicated content.

• Strict duplicate detection = exact match – not as common
• But many, many cases of near duplicates, e.g., Last modified date the only difference between two copies of a page

🔑 Definition — Duplicate Detection: Identifying two or more documents that are identical or nearly identical in content.

Duplicate/Near-Duplicate Detection

• Duplication: Exact match can be detected with fingerprints
• Near-Duplication: Approximate match
• Overview: Compute syntactic similarity with an edit-distance measure. Use a similarity threshold to detect near-duplicates.
  • E.g., Similarity > 80% => Documents are “near duplicates”
  • Not transitive though sometimes used transitively

Computing Similarity

Features used for similarity computation:

• Segments of a document (natural or artificial breakpoints)
• Shingles (Word N-Grams)
  • Example: "a rose is a rose is a rose" → 4-grams are:
    • a_rose_is_a
    • rose_is_a_rose
    • is_a_rose_is
    • a_rose_is_a

📐 Formula: Similarity Measure between two docs (= sets of shingles) → Set Intersection. Specifically: Size_of_Intersection / Size_of_Union

Shingles + Set Intersection

Computing exact set intersection of shingles between all pairs of documents is expensive and intractable. Instead, approximate using a cleverly chosen subset of shingles from each document (a sketch). Estimate (size_of_intersection / size_of_union) based on a short sketch.

Sketch of a document

Create a “sketch vector” (of size ~200) for each document. Documents that share ≥ t (say 80%) corresponding vector elements are deemed near duplicates.

For document D, sketch_D[i] is computed as follows:

• Let f map all shingles in the universe to 0..2^m (e.g., f = fingerprinting)
• Let π_i be a random permutation on 0..2^m
• Pick MIN {π_i(f(s))} over all shingles s in D

Final notes

• Shingling is a randomized algorithm
• The analysis did not presume any probability model on the inputs
• It will give us the right (wrong) answer with some probability on any input
• We’ve described how to detect near duplication in a pair of documents
• In “real life” we’ll have to concurrently look at many pairs → Use Locality Sensitive Hashing for this

⭐ Key Takeaways

The Mercator URL frontier is essential for balancing politeness (not overwhelming servers) and freshness (crawling frequently updated pages). It uses two tiers of queues: front queues for priority and back queues for host-specific politeness, managed by a heap of earliest access times. For duplicate detection, exact matches are identified with fingerprints, while near-duplicates use shingle-based similarity (word n-grams) computed via set intersection. Since exact set intersection is expensive, a sketch vector of about 200 elements is used, comparing the minimum of randomly permuted shingle fingerprints. Locality Sensitive Hashing is the practical method for scaling near-duplicate detection across many document pairs concurrently.

🧠 Quick Revision Questions

1. What are the two main considerations (goals) of a URL frontier, and why might they conflict?
2. In the Mercator scheme, what is the role of front queues versus back queues?
3. How does the back queue heap determine when a host can be accessed again?
4. What is a shingle in the context of near-duplicate detection, and how is similarity measured between two documents using shingles?
5. How is a sketch vector for a document created, and what threshold is typically used to deem documents as near-duplicates?

📘 Lecture 35 — Distributed Index

📖 Overview: This lecture explores how large-scale information retrieval systems handle indexing across multiple machines, including distributed indexing using MapReduce, dynamic indexing strategies for updating documents, and the challenges of maintaining collection statistics in dynamic environments. It provides essential techniques for building scalable search engines.

🗂️ Topics Covered

The lecture covers distributed indexing concepts, the MapReduce framework for parallel index construction, mapping IR tasks onto Hadoop MapReduce, dynamic indexing approaches including simple and logarithmic merge strategies, and key issues such as maintaining collection statistics and handling deletions with invalidation bit-vectors.

📝 Lecture Summary

Distributed Index

In large-scale IR systems, the inverted index is not stored on a single machine due to storage and performance limitations. Instead, it is distributed across multiple machines in cluster computing or grid computing environments. Large-scale IR systems typically operate data centers containing thousands of machines.

Map Reduce

MapReduce is a programming model that utilizes several machines to construct indexes in parallel. It consists of two phases:

• Map Phase: Takes documents and parses them. Documents can be split into shards based on criteria such as alphabetical ranges (e.g., a-h, i-p, q-z).
• Reduce Phase: Performs inversion — building the inverted index from the mapped data.

Apache Hadoop is an open-source framework for implementing MapReduce. Each phase of an IR system can be mapped to the MapReduce paradigm.

🔑 Definition — MapReduce: A programming model for processing large datasets in parallel across distributed clusters, consisting of Map (parsing/filtering) and Reduce (aggregation/inversion) phases.

Mapping onto Hadoop Map Reduce

The Map phase takes documents and produces (TermId, DocId) pairs. The Reducer receives these pairs and, based on a defined mapping criterion (e.g., DocId ranges or alphabetical groups like a-g), assigns pairs to different reducers. The reducers then sort the information by DocId and generate postings lists for different terms.

📐 Formula: Map → (TermId, DocId) pairs → Reducer → Sorted postings lists

Dynamic Indexing

Documents in a dynamic corpus are frequently updated or deleted. A simple approach involves:

• Maintaining a big main index on disk.
• Storing new documents in an auxiliary small index built in RAM.
• Answering queries by searching both indexes and merging results.
• For deletions: Use invalidation bit-vectors for deleted documents. The size of the bit-vector equals the number of documents in the corpus. Search results are filtered using this bit-vector.
• Periodically merge the main and auxiliary indexes.

💡 Why this matters: Without dynamic indexing, every document update or deletion would require rebuilding the entire index, which is computationally infeasible for large collections.

Dynamic Indexing (Logarithmic Merge)

The logarithmic merge strategy improves merge efficiency. Indexes are sized as powers of two:

• Z0: index in memory
• I1, I2, I3...: indexes of increasing sizes (2¹, 2², 2³...)

When Z0 exceeds a threshold 'n' (number of tokens), it merges with I1. If I1 already exists, the merged result becomes I1, and Z0 resets. This continues, with Z0 growing and merging into progressively larger indexes.

Searching involves querying all existing indexes. If there are T terms in the index, there will be at most log(T) indexes. Query processing requires O(log T) merges.

📐 Formula: Number of indexes ≤ log₂(T) where T = total terms 📌 Example: If there are 1,000,000 terms, there will be at most log₂(1,000,000) ≈ 20 indexes.

Issues in Dynamic Indexing

Key challenges include:

• Collection Statistics: IDF (Inverse Document Frequency) is harder to maintain with multiple indexes because term frequency across the entire corpus is distributed.
• Spelling Correction: Traditional spelling correction assumes a single unified index.
• Invalidation bit-vectors must be incorporated when computing word statistics.

Solutions include:

• A simple heuristic: use the LARGEST index for statistics, though it reflects inaccurate information.
• Large search engines build a new index on separate machines and switch to it once complete.
• Google Dance: The historical practice of Google periodically updating its entire index.

💡 Why this matters: Accurate collection statistics are critical for ranking relevance; maintaining them in dynamic environments is a complex engineering challenge.

⭐ Key Takeaways

Students must understand that distributed indexing using MapReduce enables parallel construction of inverted indexes across clusters. Dynamic indexing requires strategies like maintaining an auxiliary index in RAM with periodic merges to handle document updates and deletions. The logarithmic merge approach keeps merge costs at O(log T) by maintaining indexes of exponentially increasing sizes. Key challenges include maintaining accurate collection statistics like IDF and handling deletions via invalidation bit-vectors. Large search engines solve these issues by building complete new indexes on separate machines before switching over.

🧠 Quick Revision Questions

1. What are the two phases of MapReduce, and what does each phase do in the context of building an inverted index?
2. How does the logarithmic merge strategy keep the number of indexes at most log(T)?
3. What is an invalidation bit-vector, and how is its size determined?
4. Why is IDF harder to maintain in a dynamic indexing environment with multiple indexes?
5. What is the "Google Dance" and what problem does it solve?

📘 Lecture 36 — Link Analysis

📖 Overview: This lecture shifts focus from content-based retrieval to link analysis, exploring how hyperlinks between web pages serve as powerful sources of authority and ranking. It introduces foundational concepts like the web as a directed graph, anchor text indexing, and PageRank scoring, which are critical for modern search engines and information retrieval.

🗂️ Topics Covered

The lecture covers hypertext and links and their role in authority, the web as a directed graph with adjacency lists and gap encodings, anchor text indexing for improved search accuracy, citation analysis concepts, and PageRank scoring with teleportation to handle dead-ends, along with resource references.

📝 Lecture Summary

Hypertext and Links

This section explains that we move beyond document content to examine hyperlinks between documents. Links address questions about authority (conferral of authority to pages), relevance (e.g., a page linked from CERN likely about high energy physics), and are applicable to the web, email, and social networks. Links are powerful sources of authenticity and authority used for spam detection, host quality assessment, and analysis of phone call logs.

The lecture introduces the Good, Bad, Unknown model: Good nodes won’t point to Bad nodes. All other combinations (Good→Good, Good→Unknown, Bad→Bad, Bad→Good, Bad→Unknown, Unknown→any) are plausible. Simple iterative logic is applied: if you point to a Bad node, you’re Bad; if a Good node points to you, you’re Good. Sometimes probabilistic analogs are needed (e.g., for mail spam). Primary interests are link analysis for IR—scoring, ranking, clustering (topical structure from links), classification (linked documents likely on same subject), and crawling (where to go next based on links).

The Web as a Directed Graph

The web is represented as a directed graph where web pages are nodes and hyperlinks are directed edges. This graph structure enables analysis of connectivity, authority flow, and ranking.

Anchor Text

Anchor text is the visible, clickable text in a hyperlink. The WWW Worm (McBryan, 1994) used anchor text to distinguish between pages about a topic like "IBM": IBM’s home page (mostly graphical), IBM’s copyright page (high term frequency for "ibm"), and a rival’s spam page (arbitrarily high term frequency). This shows how anchor text provides better context than raw page content.

🔑 Definition — Anchor Text: The clickable text in a hyperlink that describes the target page, used as a feature for indexing and ranking.

📌 Example: For "ibm," anchor text like "IBM Home Page" helps identify the real IBM site even if the target page is mostly graphical with low text content, while a spam page with artificially high "ibm" frequency can be identified as less relevant.

Indexing anchor text

When indexing a document D, include (with some weight) anchor text from links pointing to D. This improves search accuracy because anchor text often describes the target page more reliably than its own content.

Adjacency lists

Adjacency lists represent the set of neighbors of a node. Assume each URL is represented by an integer (e.g., 32 bits for 4 billion pages). Naively, each hyperlink needs 64 bits, but Boldi/Vigna achieved ~3 bits/link on average, with further work reducing to 2 bits/link.

Main ideas of Boldi/Vigna: Consider a lexicographically ordered list of all URLs (e.g., www.stanford.edu/alchemy, www.stanford.edu/biology, etc.). This ordering enables efficient compression.

Gap encodings: Given a sorted list of integers x, y, z..., represent by x, y-x, z-y... Compress each integer using a code:

• γ code: Number of bits = 1 + 2⌊lg x⌋
• δ code: Number of bits = ...
• Information theoretic bound: 1 + ⌊lg x⌋ bits
• ζ code: Works well for integers from a power law (Boldi Vigna DCC 2004)

Citation Analysis

Citation analysis includes:

• Citation frequency: How often a document is cited
• Bibliographic coupling frequency: Articles that co-cite the same articles are related
• Citation indexing: Who is this author cited by? (Garfield 1972)
• Pagerank preview: Pinsker and Narin (1960s) asked which journals are authoritative

The web differs from scholarly citation: millions of self-interested participants, widespread spamming, and link farms (groups of websites that heavily link to one another) complicate analysis.

PageRank scoring

PageRank scoring imagines a browser doing a random walk on web pages:

• Start at a random page
• At each step, go out of the current page along one of the links on that page, equiprobably
• “In the long run” each page has a long-term visit rate—use this as the page’s score

Not quite enough: The web is full of dead-ends where the random walk can get stuck, making long-term visit rates meaningless.

Teleporting solves this:

• At a dead end, jump to a random web page
• At any non-dead end, with probability 10%, jump to a random web page
• With remaining probability (90%), go out on a random link
• 10% is a parameter

Result of teleporting: Cannot get stuck locally; there is a long-term rate at which any page is visited. This visit rate is computed to derive the PageRank score.

💡 Why this matters: PageRank was the foundational algorithm that made Google’s search results significantly better than competitors by leveraging link structure rather than just text content.

⭐ Key Takeaways

A student must remember that link analysis uses hyperlinks as sources of authority, with the "Good, Bad, Unknown" model and iterative logic for classifying nodes. The web as a directed graph enables PageRank scoring via random walk with teleportation (10% jump probability) to handle dead-ends, producing long-term visit rates as page scores. Anchor text indexing improves search by including link descriptions when indexing target pages. Adjacency lists with gap encodings (γ, δ, ζ codes) efficiently compress link data. Citation analysis concepts (bibliographic coupling, citation indexing) preceded web link analysis but the web differs due to spam and self-interested participants.

🧠 Quick Revision Questions

1. What is the "Good, Bad, Unknown" model, and what rule governs Good nodes regarding Bad nodes?
2. How does teleporting solve the dead-end problem in PageRank scoring, and what is the typical teleportation probability used?
3. Explain how anchor text indexing works and why it is more reliable than raw page content for some queries.
4. What are gap encodings, and which codes (γ, δ, ζ) are mentioned for compressing adjacency lists?
5. How does citation analysis differ from web link analysis regarding participant behavior and spam?

📘 Lecture 37 — Markov chains

📖 Overview: This lecture introduces Markov chains as a foundational concept for understanding PageRank and web information retrieval. It explains how random surfer models can be used to compute long-term visit rates for web pages, and how these concepts extend to query processing and personalized search results.

🗂️ Topics Covered

The lecture covers Markov chains and their transition probability matrices, ergodic Markov chains and steady-state probability distributions, Markov chains with teleporting using the random surfer model, query processing by integrating PageRank with relevance, personalized PageRank through biased random jumps, and Google PageRank-biased spidering for focused crawling.

📝 Lecture Summary

Markov chains

A Markov chain consists of n states, plus an n × n transition probability matrix P. At each step, we are in one of the states. For 1 ≤ i,j ≤ n, the matrix entry P_ij tells us the probability of j being the next state, given we are currently in state i.

🔑 Definition — Markov chain: A stochastic model consisting of n states and an n × n transition probability matrix P, where each entry P_ij represents the probability of moving from state i to state j in one step.

📐 Formula: P = [P_ij] for 1 ≤ i,j ≤ n → The matrix entry at row i, column j gives the probability of transitioning to state j from state i.

📌 Example: If there are 3 web pages (states A, B, C), and from page A there is a 0.5 probability of going to B and 0.5 to C, then P_AB = 0.5 and P_AC = 0.5 in the transition matrix.

Ergodic Markov chains

For any ergodic Markov chain, there is a unique long-term visit rate for each state. This is called the steady-state probability distribution. Over a long time-period, we visit each state in proportion to this rate. It does not matter where we start.

🔑 Definition — Ergodic Markov chain: A Markov chain that is irreducible (every state can be reached from every other state) and aperiodic (no cycles that force regular patterns), guaranteeing a unique steady-state distribution.

📐 Formula: Steady-state distribution π = πP, where π is a probability vector and P is the transition matrix → The stationary distribution remains unchanged after one transition step.

💡 Why this matters: Ergodic chains ensure that PageRank calculations converge to a unique ranking regardless of the starting point, making web ranking stable and predictable.

Markov Chain with Teleporting: Random Surfer Model

The random surfer model adds a teleporting mechanism to overcome the problem of dead ends (pages with no outgoing links) and spider traps (pages that trap the surfer). At each step, with probability (1 - β), the surfer "teleports" to a random page uniformly, and with probability β, follows an outgoing link. This creates an ergodic Markov chain.

🔑 Definition — Teleporting: A mechanism in the random surfer model where the surfer, with probability (1 - β), jumps to a random page instead of following a link, ensuring all pages are reachable.

📐 Formula: Modified transition matrix: P' = βP + (1 - β)E, where E is a matrix of uniform teleport probabilities (1/n for all entries) → Combines link-following with random jumps to ensure ergodicity.

📌 Example: If β = 0.85 and there are 10 pages, with 85% probability the surfer follows links, and with 15% probability they teleport to any of the 10 pages equally (each with 0.15/10 = 0.015 probability).

Query Processing

The query processing approach involves: first, compute PageRank for all pages in the index; second, run the query against the index to find relevant pages; third, sort the obtained pages based on their PageRank scores; and fourth, integrate PageRank and relevance to produce the final ranking of results.

🔑 Definition — Query Processing: The multi-step process of ranking search results by combining traditional relevance scoring with PageRank importance scores.

📌 Example: For a query "machine learning," the system first retrieves all pages containing these terms, then sorts them by PageRank, and finally blends relevance scores (e.g., TF-IDF) with PageRank using a weighted formula like 0.6 × relevance + 0.4 × PageRank to produce the final result list.

Personalized PageRank

Personalized PageRank can be achieved by changing the teleport distribution E to a non-uniform distribution. This restricts "random jumps" to a set of specified relevant pages. For example, let E(p) = 0 except for one's own home page, for which E(p) = α. This results in a bias towards pages that are closer in the web graph to your own homepage. Another example is using 0.6 × sports + 0.4 × news as the teleport distribution.

🔑 Definition — Personalized PageRank: A modified PageRank algorithm where the teleport probability vector E is customized to reflect personal preferences, biasing the ranking toward pages related to specific topics or user interests.

📐 Formula: Personalized PageRank: R' = βPR' + (1 - β)E', where E' is a non-uniform personalization vector → The teleport distribution is tailored to user-specific interests.

📌 Example: For a sports fan with E(sports_page) = 0.6 and E(news_page) = 0.4 (and 0 for all others), the random surfer teleports to sports pages 60% of the time and news pages 40% of the time, causing sports-related pages to receive higher PageRank scores.

Google PageRank-Biased Spidering

PageRank-biased spidering uses PageRank to direct a spider on "important" pages. The system computes PageRank using the current set of crawled pages. It then orders the spider's search queue based on current estimated PageRank. This approach includes Topic Directed PageRank, where crawling is focused on pages relevant to specific topics.

🔑 Definition — PageRank-Biased Spidering: A web crawling strategy that prioritizes pages with higher estimated PageRank scores, ensuring that important pages are discovered and indexed earlier.

📌 Example: If a spider has two uncrawled URLs—one with estimated PageRank 0.05 and another with 0.001—it will crawl the first page first because of its higher importance score, leading to more efficient resource utilization.

⭐ Key Takeaways

Markov chains provide the mathematical foundation for PageRank, with transition probability matrices modeling the random surfer's behavior across web pages. Ergodic Markov chains guarantee a unique steady-state probability distribution, which is essential for stable PageRank calculations that converge regardless of starting point. The random surfer model with teleporting solves the problems of dead ends and spider traps by allowing random jumps, ensuring the Markov chain is ergodic. Query processing combines PageRank scores with relevance scores to produce final search rankings, balancing importance with topical relevance. Personalized PageRank customizes the teleport distribution to user preferences, biasing results toward specific topics or personal home pages.

🧠 Quick Revision Questions

1. What are the two key conditions for a Markov chain to be considered ergodic?
2. How does the teleporting mechanism in the random surfer model solve the problem of dead ends and spider traps?
3. What is the formula for the modified transition matrix in a Markov chain with teleporting?
4. How does personalized PageRank differ from standard PageRank in terms of the teleport distribution?
5. What is the purpose of PageRank-biased spidering in web crawling, and how does it prioritize pages?

📘 Lecture 38 — HITS

📖 Overview: This lecture introduces Hyperlink-Induced Topic Search (HITS), an algorithm that models web pages as hubs and authorities based on link analysis. It explains how to compute these scores iteratively, addresses practical limitations, and demonstrates applications like similar-page finding and clustering ambiguous queries.

🗂️ Topics Covered

The lecture covers the HITS algorithm including hubs and authorities definitions and their circular relationship, building a base set from a root set, iterative computation of hub and authority scores with normalization, practical limitations and scaling, proof of convergence using matrix notation, finding similar pages via link structure, using HITS for clustering ambiguous queries, and issues like topic drift and mutually reinforcing affiliates.

📝 Lecture Summary

Hyperlink-Induced Topic Search (HITS)

In response to a query, instead of an ordered list of pages each meeting the query, find two sets of inter-related pages: Hub pages are good lists of links on a subject (e.g., “Bob’s list of cancer-related links”). Authority pages occur recurrently on good hubs for the subject. HITS is best suited for “broad topic” queries (informational queries) rather than page-finding queries, and gets at a broader slice of common opinion.

Hubs and Authorities

A good hub page for a topic points to many authoritative pages for that topic. A good authority page for a topic is pointed to by many good hubs for that topic. This is a circular definition that will be turned into an iterative computation.

Authorities are pages recognized as providing significant, trustworthy, and useful information on a topic. In-degree (number of pointers to a page) is one simple measure of authority, but it treats all links as equal. Should links from pages that are themselves authoritative count more?

Hubs are index pages that provide lots of useful links to relevant content pages (topic authorities). For example, hub pages for information retrieval are included in course home pages.

The hope

High-level scheme: extract from the web a base set of pages that could be good hubs or authorities, then from these identify a small set of top hub and authority pages using an iterative algorithm.

Base set: Given a text query (e.g., “browser”), use a text index to get all pages containing the query term — call this the root set of pages. Add any page that either points to a page in the root set, or is pointed to by a page in the root set. Call this the base set.

Distilling hubs and authorities

Compute, for each page x in the base set, a hub score h(x) and an authority score a(x). Initialize: for all x, h(x)←1; a(x)←1. Iteratively update all h(x), a(x). After iterations, output pages with highest h() scores as top hubs and highest a() scores as top authorities.

Base limitations — to limit computational expense: limit number of root pages to the top 200 pages retrieved for the query; limit number of “back-pointer” pages to a random set of at most 50 pages. To eliminate purely navigational links: eliminate links between two pages on the same host. To eliminate “non-authority-conveying” links: allow only m (m≃4–8) pages from a given host as pointers to any individual page.

Iterative update: Repeat the following updates for all x:

• a(x) ← sum of h(y) over all pages y that link to x
• h(x) ← sum of a(z) over all pages z that x links to

Scaling: To prevent the h() and a() values from getting too big, scale down after each iteration. The scaling factor doesn’t matter because we only care about the relative values of the scores.

How many iterations? Claim: relative values of scores will converge after a few iterations. Suitably scaled, h() and a() scores settle into a steady state. In practice, ~5 iterations get you close to stability.

Results: For query “Java” — authorities include java.sun.com, comp.lang.java FAQ. For query “search engine” — authorities include Yahoo.com, Excite.com, Lycos.com, Altavista.com. For query “Gates” — authorities include Microsoft.com, roadahead.com.

Proof of convergence

n × n adjacency matrix A: each of the n pages in the base set has a row and column in the matrix. Entry Aij = 1 if page i links to page j, else = 0.

Hub/authority vectors: View the hub scores h() and authority scores a() as vectors with n components. Recall the iterative updates: a(x) ← sum of h(y) for y linking to x, and h(x) ← sum of a(z) for z that x links to.

Rewrite in matrix form: Let a = A^T · h and h = A · a, where A is the adjacency matrix. Then a = A^T · A · a and h = A · A^T · h, showing that a is the principal eigenvector of A^T A and h is the principal eigenvector of A A^T.

Finding Similar Pages Using Link Structure

Given a page P, let R (the root set) be t (e.g., 200) pages that point to P. Grow a base set S from R. Run HITS on S. Return the best authorities in S as the best similar-pages for P. Finds authorities in the “link neighborhood” of P.

Similar Page Results: Given “honda.com” — similar pages include toyota.com, ford.com, bmwusa.com, saturncars.com, nissanmotors.com, audi.com, volvocars.com.

HITS for Clustering

An ambiguous query can result in the principal eigenvector only covering one of the possible meanings. Non-principal eigenvectors may contain hubs and authorities for other meanings. Example: query “jaguar” — Atari video game (principal eigenvector), NFL Football team (2nd non-principal eigenvector), Automobile (3rd non-principal eigenvector).

Issues

Topic Drift: Off-topic pages can cause off-topic “authorities” to be returned (e.g., the neighborhood graph can be about a “super topic”).

Mutually Reinforcing Affiliates: Affiliated pages/sites can boost each others’ scores. Linkage between affiliated pages is not a useful signal.

💡 Why this matters: Understanding HITS reveals how early search engines used link structure beyond simple in-degree, and how eigenvector analysis can reveal multiple themes in ambiguous queries through non-principal components.

⭐ Key Takeaways

The HITS algorithm models web pages as hubs (pages pointing to many good sources) and authorities (pages pointed to by many good hubs), computed iteratively with mutual reinforcement. Starting from a query’s root set, a base set is built by including linked and linking pages, then hub and authority scores converge after about 5 iterations via eigenvector computation. Practical limitations require capping root set size (200 pages) and back-links (50 pages), removing same-host navigational links, and limiting cross-host pointers. HITS can find similar pages by analyzing link neighborhoods, and non-principal eigenvectors can disambiguate multiple meanings of ambiguous queries. However, topic drift and mutually reinforcing affiliates can degrade results.

🧠 Quick Revision Questions

1. What is the circular definition that connects hubs and authorities in HITS?
2. How is the base set constructed starting from a root set?
3. Write the mathematical expression for the iterative update of authority scores.
4. How many iterations are typically sufficient for HITS to reach stability?
5. What issue arises when using HITS for clustering an ambiguous query like “jaguar”?

📘 Lecture 39 — Search Computing

📖 Overview: This lecture introduces Search Computing, a paradigm for answering multi-domain queries that span multiple, distinct data sources (e.g., finding a theatre, a recent thriller movie, and a good steak house nearby). It explains why traditional search engines fail at such tasks, presents the observed trends enabling this approach, and details the architecture and manifesto of Search Computing.

🗂️ Topics Covered

The lecture begins by motivating multi-domain queries with ranking, explains why search engines cannot handle them, and reviews observed trends like Web APIs and linked data. It then defines Search Computing as service composition on demand, presents the Search Computing “Manifesto,” and concludes with the overall Search Computing architecture.

📝 Lecture Summary

Motivation: multi-domain queries with ranking

The lecture opens with a scenario: a user wants to watch a recent thriller at a close theatre and then eat at a good steak house. A single keyword search fails because the required information (movie listings, theatre locations, restaurant reviews) is spread across different web pages. Users must manually split the task, search for theatres, inspect details, find a thriller is missing, then independently search for a steak house, and finally integrate and rank results manually in their brain. This process is inefficient and highlights the need for automated multi-domain search.

Why Search Engines can’t do it?

Traditional search engines fail for two key reasons:

• The query is about distinct domains that should be linked (e.g., movies, locations, restaurants).
• The query deals with multiple rankings that are hard to compute together (e.g., "close" theatre, "recent" thriller, "good" steak house). Although enough data exists on the Web, it is not on a single web page, making integration and ranking impossible for standard search engines.

🔑 Definition — Multi-domain query: A query that spans multiple, conceptually different domains (e.g., entertainment, dining, location).

Observed trends

Several trends enable the Search Computing approach:

• More data sources become accessible through Web APIs (as services), including both surface and deep Web content.
• Data sources are often coupled with search APIs, making them programmatically queryable.
• Publishing of structured and interconnected data is becoming popular (e.g., Linked Open Data). This creates an opportunity to build focused search systems that compose results from several data sources. Such systems are easy-to-build, easy-to-query, easy-to-maintain, and easy-to-scale, covering the functionality of vertical search systems (e.g., Expedia, Amazon) on more focused application domains like localized real estate, leisure planning, or biomedical research.

🔑 Definition — Vertical search systems: Specialized search engines focused on a specific domain (e.g., travel, e-commerce).

Search Computing = service composition “on demand”

Search Computing is defined as the composition of search services on demand. Key aspects of composition abstractions include:

• Service invocations: calling individual data sources.
• Fundamental operations: parallel invocations, joins, pipelining.
• Global constraints on execution: ensuring overall coherence. Data composition should be search-driven, aimed at producing few top results very fast. For example, a query like "a house in a walkable area, close to public transportation, and located in a pleasant neighborhood" requires composing results from real estate, transit, and neighborhood rating services.

🔑 Definition — Search Computing: A paradigm for building global answers by combining data from multiple search services, ranking them according to a global ranking criteria.

The Search Computing “Manifesto”

The manifesto outlines the core goals:

• Build theories, methods, and tools to support search-oriented multi-domain queries.
• Given a multi-domain query over a set of search services, build global answers by combining data from each service.
• Rank global answers according to a global ranking and output results in ranking order.
• Support user-friendly query formulation and browsing of results.
• Include new domains while the search process proceeds.
• Possibly change the relative weight of each partial ranking. This is described as "searching via interactive/dynamic mashups of ranked data sources."

Search Computing architecture: overall view

The architecture is presented in a diagram (not fully described in text). It suggests an overall system where user queries are processed by combining multiple ranked data sources, with components for service invocation, data composition, and global ranking. The architecture supports the dynamic inclusion of new domains and adjustment of ranking weights.

💡 Why this matters: Search Computing directly addresses the limitation of current search engines for complex, real-world queries that require integrating and ranking information from multiple, independent sources.

⭐ Key Takeaways

Search Computing solves the problem of multi-domain queries that traditional search engines cannot handle because the required data is spread across multiple pages and domains. It leverages trends like Web APIs, deep Web data, and linked open data to compose results on demand. The Search Computing Manifesto emphasizes building global ranked answers from multiple services, supporting dynamic domain inclusion, and adjusting ranking weights. The architecture supports service invocations, joins, pipelining, and global constraints to produce top results fast. The ultimate goal is user-friendly query formulation and browsing for complex, multi-faceted searches like leisure planning or real estate.

🧠 Quick Revision Questions

1. What are the two main reasons traditional search engines cannot handle multi-domain queries like "find a recent thriller at a close theatre and a good steak house nearby"?
2. List three observed trends that enable the Search Computing approach.
3. What does "Search Computing = service composition on demand" mean in practice?
4. According to the Search Computing Manifesto, what are the six key methods or tools that should be built?
5. What is the primary goal of the Search Computing architecture?

📘 Lecture 40 — Top-k Query Processing

📖 Overview: This lecture introduces Top-k Query Processing, a set of techniques for efficiently retrieving the highest-ranked objects from multiple sorted lists. It covers two main algorithms — Fagin’s Algorithm (FA) and the Threshold Algorithm (TA) — and compares their performance in terms of objects seen, random accesses, and buffer requirements. The lecture also explores extensions of TA for scenarios with restricted or impossible random access.

🗂️ Topics Covered

The lecture begins with an introduction to Top-k Query Processing and a Simple Database model. It then presents Fagin’s Algorithm, followed by the Threshold Algorithm as a new idea. A detailed Comparison of Fagin’s and Threshold Algorithm is provided, including discussions on the best algorithm based on instance optimality and aggregation function characteristics. The lecture concludes with extensions of TA for various real-world constraints.

📝 Lecture Summary

Top-k Query Processing

Top-k Query Processing is a technique for finding the top k objects (e.g., documents, items) that have the highest combined score across multiple sorted lists. The goal is to minimize the number of accesses to the database, especially when random access is expensive.

🔑 Definition — Top-k Query: A query that retrieves the k objects with the highest overall score, where the score is computed from multiple attributes via an aggregation function.

Simple Database model

The database model consists of m sorted lists, each containing object IDs and their scores for a specific attribute. Objects have a grade (score) in each list. The overall grade for an object is computed by a monotone aggregation function t that combines the individual grades.

Fagin’s Algorithm

Fagin’s Algorithm (FA) works by doing sorted access in parallel to all m lists until at least k objects have been seen in all lists (i.e., k objects are "common" across all lists). At that point, random access is performed to retrieve the missing grades for those common objects, and the top k are determined.

📌 Example: Suppose we have 2 lists of movies (A and B) sorted by rating. We want top 3 movies. FA reads movies from both lists until 3 movies appear in both lists. Then, it randomly accesses the missing ratings for those 3 movies and computes their total score to select the top 3.

Threshold Algorithm (TA)

The Threshold Algorithm (TA) improves on FA by maintaining a threshold value T, which is the maximum possible grade any unseen object can achieve. TA does sorted access and for each newly seen object, performs random access to get its missing grades and computes its overall grade. It keeps a buffer of the top k objects seen so far. The algorithm stops when the scores of the top k objects are all greater than or equal to the current threshold T.

🔑 Definition — Threshold (T) in TA: The sum of the last scores seen in each sorted list during sorted access. It represents the maximum possible score of any object not yet fully seen.

💡 Why this matters: TA stops earlier than FA because it uses the threshold to know when it is safe to stop, without needing to wait for k common objects.

Comparison of Fagin’s and Threshold Algorithm

The lecture compares FA and TA across several dimensions:

• Objects seen: TA sees fewer objects than FA.
• Stopping point: TA stops at least as early as FA.
• Common objects grade: When k objects are in common in FA, their grades are higher than or equal to the threshold in TA.
• Random accesses: TA may perform more random accesses (m-1 per object) than FA, which does all random accesses only at the end.
• Buffer space: TA requires only bounded buffer space of size k, while FA needs unbounded buffers (to store all seen objects).
• Cost trade-off: TA uses fewer random accesses overall but more random seeks, while FA uses more buffer space.

The best algorithm

The "best" algorithm depends on the middleware cost model and the concept of instance optimality. Instance optimality means that the algorithm performs within a constant factor of the optimal algorithm for any data instance.

Key factors in choosing the best algorithm:

• Wild guesses: Random accesses without prior sorted access.
• Aggregation function characteristics:
  • Monotone: t(x1,...,xm) ≤ t(x'1,...,x'm) if xi ≤ x'i for every i
  • Strictly monotone: t(x1,...,xm) < t(x'1,...,x'm) if xi < x'i for every i
  • Strict: t(x1,...,xm) = 1 precisely when xi = 1 for every i
• Database restrictions: e.g., the distinctness property of objects across lists.

🔑 Definition — Instance optimality: An algorithm A is instance optimal if for every instance I, the cost of A on I is within a constant factor of the optimal algorithm's cost on I.

Extending TA

The lecture presents several extensions of TA for real-world constraints:

• TAz: For restricted sorted access (e.g., distance databases).
• No Random Access Algorithm (NRA): For cases where random access is impossible (e.g., web search engines).
• TAθ: For approximate top-k results (only approximate answers needed).
• Combined Algorithm: A hybrid between TA and NRA that considers the relative costs of random and sorted access.

A Taxonomy of Top-k Joins is also mentioned, which categorizes these algorithms based on access patterns and constraints.

⭐ Key Takeaways

The most critical concepts from this lecture are: Top-k query processing efficiently finds the highest-ranked objects from multiple sorted lists. Fagin’s Algorithm waits until k objects appear in all lists, while the Threshold Algorithm uses a threshold to stop earlier, at the cost of more random accesses. TA requires only bounded buffer space (k), whereas FA needs unbounded buffers. The choice between TA and FA depends on the middleware cost, aggregation function properties (monotone, strictly monotone, strict), and database restrictions like the distinctness property. Extensions like NRA and TAθ adapt the core TA idea for scenarios with restricted random access or approximate results.

🧠 Quick Revision Questions

1. What is the main difference between Fagin’s Algorithm (FA) and the Threshold Algorithm (TA) in terms of when they stop?
2. In the Threshold Algorithm, what does the “threshold” T represent, and how is it calculated?
3. Why might TA perform more random accesses than FA, even though it sees fewer objects?
4. What is instance optimality, and why is it important when comparing algorithms like FA and TA?
5. Name two extensions of TA and describe the real-world constraints they address.

📘 Lecture 41 — Clustering

📖 Overview: This lecture introduces clustering, an unsupervised learning technique that groups similar documents together. It covers the fundamental concepts, applications in Information Retrieval, issues to consider, similarity/distance measures, and two major clustering approaches: flat (K-means) and hierarchical algorithms.

🗂️ Topics Covered

This lecture covers the definition and purpose of clustering, its applications in IR such as improving search recall, navigation, and visualization. It discusses key issues like representation, similarity, and cluster count, explains hard vs. soft clustering, and provides an in-depth look at the K-means clustering algorithm, its convergence, and seed choice, followed by an introduction to hierarchical clustering.

📝 Lecture Summary

What is clustering?

Clustering is the process of grouping a set of objects into classes of similar objects. Documents within a cluster should be similar, while documents from different clusters should be dissimilar. It is the most common form of unsupervised learning, meaning it learns from raw data without pre-labeled examples, as opposed to supervised learning. Clustering is a common and important task in Information Retrieval and other fields.

🔑 Definition — Clustering: The process of grouping a set of objects into classes of similar objects.

📌 Example: A data set with clear cluster structure shows natural groupings of points that a clustering algorithm would identify.

Applications of clustering in IR

Clustering has several applications in IR:

• Whole corpus analysis/navigation: Providing a better user interface for browsing without typing.
• For improving recall in search applications: Getting better search results, similar to pseudo-relevance feedback.
• For better navigation of search results: Effective “user recall” will be higher.
• For speeding up vector space retrieval: Cluster-based retrieval gives faster search.

For improving search recall

The cluster hypothesis states that documents in the same cluster behave similarly with respect to relevance to information needs. To improve search recall, documents in the corpus are clustered a priori. When a query matches document D, other documents in the cluster containing D are also returned. The hope is that a query for “car” will also return documents containing “automobile” because clustering grouped those documents together.

🔑 Definition — Cluster hypothesis: Documents in the same cluster behave similarly with respect to relevance to information needs.

📌 Example: A search for “car” returns not only documents with the word “car” but also documents containing “automobile” that were grouped into the same cluster.

💡 Why this matters: This technique effectively increases recall by leveraging the semantic relationships discovered by clustering.

Yippy.com is mentioned as an example of a search engine that groups search results into clusters.

Visualization is another application, helping users understand the structure of a document collection.

Issues for clustering

Key issues to consider for clustering include:

• Representation for clustering: How to represent documents (e.g., vector space model, normalization).
• Need a notion of similarity/distance: A method to measure how close or far apart documents are.
• How many clusters?: This number can be fixed a priori or determined completely from the data.
• Avoid “trivial” clusters: Clusters that are too large or too small are undesirable. If a cluster is too large, it wastes a user’s click for navigation without significantly narrowing down the document set.

Notion of similarity/distance

The ideal measure is semantic similarity, but the practical approach uses term-statistical similarity, where documents are treated as vectors. The most common measure is cosine similarity. For many algorithms, it is easier to think in terms of a distance (the opposite of similarity), such as Euclidean distance. However, real implementations often use cosine similarity.

🔑 Definition — Cosine similarity: A measure of similarity between two non-zero vectors that measures the cosine of the angle between them.

Hard vs. soft clustering

• Hard clustering: Each document belongs to exactly one cluster. This is more common and easier to do.
• Soft clustering: A document can belong to more than one cluster. This is more appropriate for applications like creating browsable hierarchies.

📌 Example of Soft Clustering: A pair of sneakers could be put in two clusters: (i) sports apparel and (ii) shoes. This is only possible with a soft clustering approach.

Clustering Algorithms

Two main types of clustering algorithms:

• Flat algorithms: Usually start with a random (partial) partitioning and refine it iteratively. The key example is K-means clustering.
• Hierarchical algorithms: Build a tree of clusters (bottom-up, agglomerative, or top-down, divisive).

Partitioning Algorithms

A partitioning method constructs a partition of n documents into a set of K clusters. Given a set of documents and the number K, the goal is to find a partition of K clusters that optimizes a chosen partitioning criterion. Finding the globally optimal solution is intractable for many objective functions, so effective heuristic methods like K-means and K-medoids algorithms are used.

K-Means

K-means assumes documents are real-valued vectors. Clusters are based on centroids (the center of gravity or mean) of points in a cluster. The reassignment of instances to clusters is based on distance to the current cluster centroids.

🔑 Definition — Centroid: The center of gravity or mean of all points in a cluster, represented by c.

📐 Formula: Centroid c = (1/|S|) * Σ(d in S) d → The centroid is the average position of all documents in the cluster.

Termination conditions for K-means include:

• A fixed number of iterations.
• Document partition unchanged.
• Centroid positions don’t change.

Convergence of K-means is guaranteed because it is a special case of the Expectation Maximization (EM) algorithm. While the number of iterations could be large, in practice it usually isn’t.

Convergence of K-Means

The Residual Sum of Squares (RSS) is a goodness measure of a cluster, defined as the sum of squared distances from the cluster centroid.

• For a cluster j: RSS_j = Σ_i |d_i – c_j|² (sum over all d_i in cluster j)
• For all clusters: RSS = Σ_j RSS_j

The reassignment step monotonically decreases RSS because each vector is assigned to the closest centroid. The recomputation step also monotonically decreases each RSS_j.

🔑 Definition — Residual Sum of Squares (RSS): A measure of cluster goodness, representing the sum of squared distances of all points in a cluster from its centroid.

📐 Formula: RSS = Σ_j Σ_i |d_i – c_j|² → The total RSS is the sum of all cluster RSS values.

Seed Choice

The choice of initial centroids (seeds) can affect the final clustering result.

Hierarchical Clustering

Hierarchical clustering builds a tree-based hierarchical taxonomy, known as a dendrogram, from a set of documents. One approach is the recursive application of a partitional clustering algorithm.

🔑 Definition — Hierarchical clustering: An approach that builds a tree-based hierarchy (dendrogram) of document clusters.

Final word and resources

In clustering, clusters are inferred from the data without human input (unsupervised learning). However, in practice, many choices influence the outcome, including number of clusters, similarity measure, and representation of documents.

• Resources: IIR 16 (except 16.5) and IIR 17.1–17.3.

⭐ Key Takeaways

Clustering is a powerful unsupervised learning technique for grouping similar documents, based on the cluster hypothesis that improves search recall. The lecture distinguishes between hard and soft clustering and covers key similarity measures like cosine and Euclidean distance. The K-means algorithm is the primary flat clustering method, iteratively assigning points to the nearest centroid and updating centroids, with convergence guaranteed because RSS monotonically decreases. Hierarchical clustering offers an alternative approach by building a tree structure (dendrogram) of documents.

🧠 Quick Revision Questions

1. What is the difference between supervised and unsupervised learning in the context of clustering?
2. Explain the cluster hypothesis and how it can be used to improve search recall.
3. What is the difference between hard clustering and soft clustering, and why would you use one over the other?
4. Describe the steps of the K-means algorithm and state two termination conditions.
5. What is the Residual Sum of Squares (RSS) and why does its monotonic decrease guarantee convergence of K-means?

📘 Lecture 42 — Classification

📖 Overview: This lecture introduces classification techniques in Information Retrieval, focusing on the probabilistic foundation for document ranking and categorization. It explains why probabilities are essential for handling uncertainty in IR, and presents key classification methods including the Naïve Bayes classifier, Bayes’ Rule, Bernoulli Random Variables, and smoothing functions.

🗂️ Topics Covered

The lecture covers the role of probabilities in information retrieval, the document ranking problem, three main classification methods (manual, rule-based, and supervised learning), document classification using Bayes’ Rule, Bernoulli Random Variables for modeling term presence/absence, smoothing functions to handle zero probabilities, and an alternative version of Naïve Bayes using term frequency.

📝 Lecture Summary

Why probabilities in IR?

In traditional IR systems, matching between each document and query is attempted in a semantically imprecise space of index terms. Probabilities provide a principled foundation for uncertain reasoning. We can use probabilities to quantify our uncertainties about document relevance.

💡 Why this matters: Probabilistic models allow IR systems to rank documents by their estimated relevance, moving beyond simple keyword matching.

The document ranking problem

• We have a collection of documents and a user issues a query
• A list of documents needs to be returned
• Ranking method is the core of an IR system: in what order do we present documents to the user?
• We want the “best” document to be first, second best second, etc.
• Idea: Rank by probability of relevance of the document w.r.t. information need
• P(R=1|documentᵢ, query)

Classification Methods (1): Manual classification

• Used by the original Yahoo! Directory, Looksmart, about.com, ODP, PubMed
• Accurate when job is done by experts
• Consistent when the problem size and team is small
• Difficult and expensive to scale
• Means we need automatic classification methods for big problems

Classification Methods (2): Hand-coded rule-based classifiers

• Rules are defined by subject experts
• Commercial systems have complex query languages
• Accuracy can be high if a rule has been carefully refined over time by a subject expert
• Building and maintaining these rules is expensive

Classification Methods (3): Supervised learning

Given:

• A document d
• A fixed set of classes: C = {c₁, c₂, ..., cⱼ}
• A training set D of documents each with a label in C

Determine:

• A learning method or algorithm which will enable us to learn a classifier γ
• For a test document d, we assign it the class γ(d) ∈ C

Bayes’ Rule For Text Classification

• There are “V” terms in the vocabulary. Vocabulary = |V|
• The Document “D” contains “k” words: D = <w₁,w₂,...,wk>
• K << |V|

🔑 Definition — Bayes’ Rule: P(C|D) = P(D|C) × P(C) / P(D)

Where:

• P(C|D) = probability that document D belongs to class C (posterior)
• P(D|C) = probability of observing document D given class C (likelihood)
• P(C) = prior probability of class C
• P(D) = evidence or marginal probability of document D

Bernoulli Random Variables

• There are a₁, a₂, a₃, ..., a_L “L” words which are not present in the document “D” from the vocabulary |V|
• <w₁,w₂,...,wk> = {P(ā₁|C) P(ā₂|C) P(ā₃|C) ... P(ā_L|C)}
• <w₁,w₂,...,wk> = [1 – {P(a₁|C) P(a₂|C) P(a₃|C) ... P(a_L|C)}]

Training Set of Documents

The numbers (0 or 1) indicate absence or presence of each term in the document.

Smoothing Function

Smoothing is used to handle the problem of zero probabilities when a term does not appear in any training document of a particular class. Without smoothing, a missing term would make the entire probability zero.

📐 Formula: Add-one smoothing (Laplace smoothing): P(t|c) = (count(t,c) + 1) / (∑count(t',c) + |V|) → Plain English: Add 1 to every term count to avoid zero probabilities

Another version of Naïve Bayes

• In the previous version we consider the document frequency of a term (i.e., in how many documents is it present)
• In this newer version we consider term frequency in the document and in the corpus

Naïve Bayes Characteristics

• Underflow error may occur in both cases when we implement it on a machine
• We take log of both sides which converts multiplication into addition and avoids underflow
• Feature Selection: cut down the size of vocabulary
• Consider the subset of terms, i.e., drop rare terms and stop words

⭐ Key Takeaways

Probabilistic classification is essential for modern IR because it provides a principled way to handle uncertainty in document-query matching. The Naïve Bayes classifier uses Bayes’ Rule with a strong independence assumption to compute the probability of a document belonging to a class. Three classification paradigms exist: manual (expert-based, expensive to scale), rule-based (accurate but expensive to maintain), and supervised learning (automatic, scalable with training data). Bernoulli models treat terms as binary (present/absent), while the alternative version considers term frequency. Smoothing (like add-one smoothing) is critical to prevent zero probabilities from making entire calculations invalid, and log-transformation prevents underflow errors in computation.

🧠 Quick Revision Questions

1. What is the core idea behind ranking documents using probabilities?
2. List the three main classification methods discussed in this lecture and one advantage of each.
3. Write Bayes’ Rule for text classification and explain each term.
4. Why is smoothing necessary in Naïve Bayes classification?
5. What is the difference between the Bernoulli version of Naïve Bayes and the version that uses term frequency?

📘 Lecture 43 — Classification

📖 Overview: This lecture covers classification techniques in information retrieval, focusing on vector space methods. It explains how to classify documents based on their similarity to prototype vectors or nearest neighbors, and discusses the trade-offs between different algorithms, including Rocchio classification and k-Nearest Neighbors.

🗂️ Topics Covered

The lecture covers Rocchio classification using centroids and prototype vectors, the k-Nearest Neighbor (kNN) algorithm including its lazy learning paradigm, decision boundaries for kNN, and the important concept of bias vs. variance in model selection. It also includes a discussion on evaluating categorization performance.

📝 Lecture Summary

Classification Using Vector Spaces

In vector space classification, the training set is represented as a labeled set of points (vectors) in a multidimensional space. The core premise is that documents in the same class form a contiguous region of space, while documents from different classes don’t overlap much. Learning a classifier involves building surfaces to delineate classes in this space.

💡 Why this matters: This geometric view allows us to use distance and similarity measures to automatically determine which class a new document belongs to.

Rocchio Algorithm

The Rocchio algorithm adapts relevance feedback methods for text categorization. It uses standard tf-idf weighted vectors to represent documents. For each category, a prototype vector (centroid) is computed by summing the vectors of all training documents in that category. A test document is assigned to the category with the closest prototype vector based on cosine similarity.

The algorithm works by finding the centroid of members of each class. However, one issue is that if there are many more vectors along one axis (e.g., y-axis) in a class, they will drift the centroid toward that axis, potentially misclassifying an "awkward" red document that lies near the blue centroid.

🔑 Definition — Rocchio classification: A classification method that computes a prototype vector (centroid) for each class and assigns test documents to the nearest centroid using cosine similarity.

📐 Formula: μ(c) = (1/|D_c|) * Σ( d in D_c ) v(d) → The centroid μ of class c is the average of all document vectors in that class.

📌 Example: If class "Government" has two documents with vectors [1,0] and [0.5,0.5], the centroid would be the average: [0.75, 0.25]. A test document with vector [0.8, 0.2] would be classified as "Government" because it is closest to this centroid by cosine similarity.

k Nearest Neighbor Classification

Nearest-Neighbor Learning is also called case-based learning or memory-based learning because it simply stores all labeled training examples. For a test instance x under 1NN, it computes similarity between x and all examples, then assigns x the category of the most similar example.

k Nearest Neighbor (kNN) improves robustness by finding the k closest examples and returning the majority category of these k neighbors. k is typically odd (3 and 5 are most common) to avoid ties. The rationale is the contiguity hypothesis: documents near a given input document will decide its class.

🔑 Definition — k Nearest Neighbor (kNN): A lazy learning algorithm that classifies a new document based on the majority class of its k most similar training examples.

📌 Example: With k=3, if a test document's three nearest neighbors are from classes "Sports", "Sports", and "Politics", the test document is classified as "Sports" (majority vote).

kNN decision boundaries

kNN decision boundaries are non-linear and adapt to the local structure of data. Unlike Rocchio, kNN tends to handle polymorphic categories better because it doesn't assume a single prototype can represent an entire class.

kNN Discussion:

• Advantages: No feature selection necessary, no training required, scales well with large number of classes, and is more accurate than NB or Rocchio in most cases.
• Disadvantages: May be expensive at test time (must compare to all training examples).

Evaluating Categorization

Evaluation must be done on test data that are independent of the training data. Sometimes cross-validation is used (averaging results over multiple training and test splits). It is easy to get good performance on a test set that was available to the learner during training (e.g., just memorize the test set).

Bias vs. variance: Choosing the correct model capacity

This concept addresses the trade-off between bias (error due to overly simplistic model assumptions) and variance (error due to model sensitivity to small fluctuations in training data). A model with high bias may underfit, while one with high variance may overfit. The goal is to find the correct model capacity that minimizes total error.

🔑 Definition — Bias vs. Variance: Bias measures how far a model's predictions are from correct values on average, while variance measures how much predictions vary for different training sets. The optimal model balances these two sources of error.

⭐ Key Takeaways

The most critical concepts from this lecture are understanding Rocchio classification using centroids versus kNN using multiple neighbors. Rocchio is cheap to train but may fail with polymorphic categories, while kNN is more accurate but expensive at test time. The contiguity hypothesis underpins kNN, and k=3 or 5 with majority voting handles noise better than 1NN. Finally, evaluation must use independent test data, and the bias-variance trade-off is essential for choosing model complexity.

🧠 Quick Revision Questions

1. What is a prototype vector in Rocchio classification, and how is it computed?
2. Why does kNN use k=3 or 5 instead of just 1 nearest neighbor?
3. According to the contiguity hypothesis, what determines the class of a test document?
4. Why is kNN considered a "lazy learning" algorithm?
5. What is the trade-off between bias and variance in model selection?

📘 Lecture 44 — Recommender Systems

📖 Overview: This lecture introduces recommender systems, software that suggests items (books, movies, web pages) to users based on their preferences. It covers two fundamental approaches—collaborative filtering and content-based recommending—their methods, applications, and limitations, which are essential for understanding personalization in information retrieval and e-commerce.

🗂️ Topics Covered

The lecture begins with recommender systems and their role in personalization, then outlines the two basic types. It explores collaborative filtering in detail, including similarity weighting using Pearson correlation, significance weighting, neighbor selection, and rating prediction. It ends with problems of collaborative filtering and a full treatment of content-based recommending, its advantages, disadvantages, and a specific example (LIBRA).

📝 Lecture Summary

Recommender Systems

Recommender systems are systems for recommending items (e.g. books, movies, CD’s, web pages, newsgroup messages) to users based on examples of their preferences. Many on-line stores provide recommendations (e.g. Amazon, CDNow). Recommenders have been shown to substantially increase sales at on-line stores. A book recommender visually shows recommendations grouped by category or preference.

Personalization

Personalization concerns adapting to the individual needs, interests, and preferences of each user. Recommenders are instances of personalization software. Personalization includes:

• Recommending
• Filtering
• Predicting (e.g. form or calendar appointment completion)

From a business perspective, it is viewed as part of Customer Relationship Management (CRM).

Basic Types of Recommender Systems

There are two basic approaches to recommending:

• Collaborative Filtering (a.k.a. social filtering)
• Content-based

Collaborative Filtering

Collaborative filtering maintains a database of many users’ ratings of a variety of items. For a given user, it finds other similar users whose ratings strongly correlate with the current user. It then recommends items rated highly by these similar users, but not rated by the current user. Almost all existing commercial recommenders use this approach (e.g. Amazon).

Collaborative Filtering Method:

1. Weight all users with respect to similarity with the active user.
2. Select a subset of the users (neighbors) to use as predictors.
3. Normalize ratings and compute a prediction from a weighted combination of the selected neighbors’ ratings.
4. Present items with highest predicted ratings as recommendations.

Similarity Weighting: Typically use Pearson correlation coefficient between ratings for active user, a, and another user, u.

$$ w_{a,u} = \frac{\sum_{i=1}^{m} (r_{a,i} - \bar{r}a)(r{u,i} - \bar{r}u)}{\sqrt{\sum{i=1}^{m} (r_{a,i} - \bar{r}a)^2} \sqrt{\sum{i=1}^{m} (r_{u,i} - \bar{r}_u)^2}} $$

where rₐ and rᵤ are the ratings vectors for the m items rated by both a and u.

Covariance and Standard Deviation:

• Covariance: $\text{cov}(r_a, r_u) = \frac{1}{m} \sum_{i=1}^{m} (r_{a,i} - \bar{r}a)(r{u,i} - \bar{r}_u)$, where rₓ,ᵧ is user x’s rating for item y.
• Standard Deviation: $\sigma_{r_a} = \sqrt{\frac{1}{m} \sum_{i=1}^{m} (r_{a,i} - \bar{r}_a)^2}$

Significance Weighting: Important not to trust correlations based on very few co-rated items. Include significance weights, sₐ,ᵤ, based on number of co-rated items, m.

$$ s_{a,u} = \frac{m}{m + \text{threshold}} \cdot w_{a,u} $$

Neighbor Selection: For a given active user, a, select correlated users to serve as source of predictions. The standard approach is to use the most similar n users, u, based on similarity weights, wₐ,ᵤ. An alternate approach is to include all users whose similarity weight is above a given threshold.

Rating Prediction: Predict a rating, pₐ,ᵢ, for each item i, for active user, a, by using the n selected neighbor users, u ∈ {1,2,...n}. To account for users’ different rating levels, base predictions on differences from a user’s average rating. Weight users’ rating contribution by their similarity to the active user.

$$ p_{a,i} = \bar{r}a + \frac{\sum{u=1}^{n} (r_{u,i} - \bar{r}u) \cdot w{a,u}}{\sum_{u=1}^{n} w_{a,u}} $$

Problems with Collaborative Filtering:

• Cold Start: There needs to be enough other users already in the system to find a match.
• Sparsity: If there are many items to be recommended, even if there are many users, the user/ratings matrix is sparse, and it is hard to find users that have rated the same items.
• First Rater: Cannot recommend an item that has not been previously rated (new items, esoteric/unique items).
• Popularity Bias: Cannot recommend items to someone with unique tastes; tends to recommend popular items.

💡 Why this matters: These problems are critical practical limitations—any real-world recommender system must design solutions to overcome cold start, sparsity, and popularity bias to provide useful recommendations for all users.

Content-Based Recommending

Content-based recommending bases recommendations on information on the content of items rather than on other users’ opinions. It uses a machine learning algorithm to induce a profile of the user’s preferences from examples based on a featural description of content. Some previous applications:

• Newsweeder (Lang, 1995)
• Syskill and Webert (Pazzani et al., 1996)

Advantages of Content-Based Approach:

• No need for data on other users
• No cold-start or sparsity problems
• Able to recommend to users with unique tastes
• Able to recommend new and unpopular items (no first-rater problem)
• Can provide explanations of recommended items by listing content-features that caused an item to be recommended

Disadvantages of Content-Based Method:

• Requires content that can be encoded as meaningful features
• Users’ tastes must be represented as a learnable function of these content features
• Unable to exploit quality judgments of other users (unless these are somehow included in the content features)

LIBRA (Learning Intelligent Book Recommending Agent): A content-based recommender for books using information about titles extracted from Amazon. It uses information extraction from the web to organize text into fields:

• Author
• Title
• Editorial Reviews
• Customer Comments
• Subject terms
• Related authors
• Related titles

💡 Why this matters: LIBRA demonstrates how content-based recommending works in practice—by extracting structured features from unstructured web text, it can recommend books without needing other users' ratings, solving several problems that collaborative filtering faces.

⭐ Key Takeaways

Recommender systems are personalization tools that significantly boost e-commerce sales by suggesting items based on user preferences. The two main approaches are collaborative filtering, which relies on finding similar users through Pearson correlation and predicting ratings from their weighted average, and content-based recommending, which builds a user profile from item features using machine learning. Collaborative filtering suffers from cold start, sparsity, first-rater, and popularity bias problems, while content-based methods overcome these but require meaningful content features and cannot exploit quality judgments from other users. Understanding both approaches, their mathematical foundations (similarity weighting, rating prediction), and their trade-offs is essential for designing effective recommendation systems.

🧠 Quick Revision Questions

1. What are the four main steps in the collaborative filtering method?
2. How is the Pearson correlation coefficient used to compute similarity between two users in collaborative filtering?
3. What problems does the "first rater" problem cause in collaborative filtering, and why doesn't it exist in content-based recommending?
4. List three advantages and three disadvantages of content-based recommending over collaborative filtering.
5. How does LIBRA implement content-based recommending, and what types of features does it extract?

📘 Lecture 45 — Final Notes on Information Retrieval

📖 Overview: This final lecture serves as a comprehensive review of the entire Information Retrieval course, summarizing all major topics covered from IR models through system implementation and web-based techniques. It also looks ahead to current research directions in database management, including personalization, social data, data quality, and large-scale data management, providing students with a complete framework for understanding the field.

🗂️ Topics Covered

This lecture recaps all major topics from the course, including IR Models (Boolean, Vector Space, Probability), IR System Implementation with Inverted Index (from naïve to scalable realistic implementations), Query Processing and Data Handling, Deep Web Searching (Search Computing), Web-Based IR (Page Rank, Crawling), Classification/Clustering, and Recommender Systems. It then transitions into Database Management Research, covering Personalization, Social Data, Collaborative Working, Wisdom of the Crowd, Data Quality, Data Extraction, Question Answering, Cross-Lingual Processing, Document Summarization, Plagiarism Detection, and Large-scale/Big Data Management.

📝 Lecture Summary

Topics that we covered

This section provides a complete list of all concepts taught throughout the course. The fundamental IR Models include Boolean, Vector Space, and Probability models. IR System Implementation focused on building the Inverted Index at different levels, starting from a Naïve Implementation to a Scalable realistic implementation. Key Optimizations were applied to query processing and index building through compression. The course covered Types of Queries and data handling, including Deep Web Searching (search computing). Web Based IR techniques included Page Rank and Crawling. The course also addressed Classification and Clustering, as well as Recommender Systems.

Database Management Research

This section explores current research directions for improving web search and surfing. Personalization involves adapting results based on User Preferences and localization. Social Data approaches seek to leverage community interaction to create refine content, using experts, friends, and sub-communities of shared interests. Collaborative Working includes the concept of Wisdom of the crowd — applied through mechanisms like page rank, reviews, feedback (Crowd Sourcing). Specific examples include Collaborative editing (Wikipedia) and Collaborative Searching (crowd search). Harnessing the collaborative power is exemplified by platforms like Amazon Mechanical Turk. Data Quality concerns include Provenance/Lineage/Source, Confidence on the source, and Correlation (did we agree with source before). A practical example given: "What is the mileage of my Honda Civic (so many sites...)"

🔑 Definition — Personalization: [adapting search results based on individual user preferences and location] 🔑 Definition — Wisdom of the Crowd: [aggregating collective input from multiple users (through page rank, reviews, feedback) to improve results]

Database Management Research (continued)

This section continues with additional research directions. Data Extraction focuses on extracting relevant information from documents. Question answering distinguishes between Knowledge vs Reasoning Engines (comparing Google vs Wolfram Alpha). The field addresses Domain Specific knowledge and Cross Lingual information retrieval. Document Summarization and Plagiarism Detection are important applications. Finally, Large-scale Data Management involves Scalability and Big Data Management.

🔑 Definition — Knowledge vs Reasoning Engines: [Knowledge engines (like Google) retrieve stored information, while reasoning engines (like Wolfram Alpha) compute answers from underlying data] 💡 Why this matters: Understanding the difference between retrieval and computation is critical as knowledge engines provide existing facts while reasoning engines derive new information through algorithms.

⭐ Key Takeaways

This lecture emphasizes that Information Retrieval spans from fundamental models (Boolean, Vector Space, Probability) through practical implementation using inverted indexes with compression and optimization, to advanced web techniques like Page Rank, crawling, and recommender systems. The future of the field lies in integrating social data and personalization, leveraging crowd wisdom for collaborative filtering and editing, and addressing data quality concerns around provenance and confidence. Key research challenges include data extraction, cross-lingual processing, document summarization, plagiarism detection, and especially large-scale/big data management. Students must understand the complete pipeline from query processing to scalable index building, and how web-based IR extends classic models with ranking and social collaboration.

🧠 Quick Revision Questions

1. What are the three fundamental IR models covered in this course, and what distinguishes each one?
2. Describe the progression from a naïve inverted index implementation to a scalable realistic one — what optimizations are applied?
3. How does "Wisdom of the Crowd" apply to web search, and give two specific examples of collaborative working mentioned in the lecture?
4. What is the difference between a "Knowledge Engine" and a "Reasoning Engine," and which real-world systems exemplify each?
5. List three major research challenges in database management that were discussed in this final lecture, and explain why each matters for the future of web search.