Information Retrieval and Search

CMPT 479/880 Notes
Robert D. Cameron
March 6, 2001

The IR Problem

Given a document collection and a query, retrieve relevant documents matching the query.

Recall and Precision

Two fundamental measures of the quality of information retrieval.

What percentage of relevant documents are retrieved.
What percentage of retrieved documents are relevant.


When is a document relevant?

Vector Space Model

A high-dimensionality vector space is constructed consisting of one dimension for every unique term found in the document collection.

Documents and queries are represented by vectors. The coordinate value along each dimension is a weight, typically based on the number of occurrences of the term in the document or query.

Documents and queries may be matched by vector comparison operations.

Text Analysis

Extraction of the term vector from a text.

Term candidates:
lexical elements extracted from a document that may be used as terms.
Stop words
are commonly occurring words deleted from the list of term candidates.
may be used to reduce the dimensionality by combining words that only differ in suffix.
the number of occurrences of a word in a document.

Term Frequency and Indexing Significance

Luhn: term frequency is useful determining significance for retrieval.

(from Chapter 2 of Information Retrieval, C.J. van Rijsbergen

TF-IDF Weighting

Frequently occurring terms may not be useful if they are equally frequent in all documents.

Term Frequency in a document.
total number of documents.
total number of documents having the term.
Inverse Document Frequency
IDF = log2 N/n
The information content associated with known a term is in a particular document.

Relevance to Web Search Engines

The vector space model with TF-IDF weights is relevant to search engine development.

Raymie Stata, Krishna Bharat and Farzin Maghoul "The Term Vector Database: fast access to indexing terms for Web pages" 9th International World Wide Web Conference ISBN/1-930792-00-X$159