Search and Retrieval on the Web

I. The Information Retrieval 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.

Recall

What percentage of relevant documents are retrieved.

Precision

What percentage of retrieved documents are relevant.

Unsatisfactory extremes:

• Return 1 relevant document: 100% precision, very low recall.
• Return all documents: 100% recall, very low precision.

Relevance: User Judgment

When is a document relevant? When it serves the user's needs.

But: different users may have different notions of relevance for the same query.

Users may make mistakes in query formulation.

Contrast with database queries: We expect 100% recall and 100% precision with database queries. DB queries are expressed in a formalized language with a known semantics.

Document Collection Issues

Document collections span a spectrum from homogeneous to heterogeneous.

• Homogeneous collection: 250-word abstracts of scientific papers in a particular subject area.
• Heterogeneous collections: documents found on the World-Wide Web.

II. Classical IR: The Vector Space Model

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.

Stemming

may be used to reduce the dimensionality by combining words that only differ in suffix.

Frequency

the number of occurrences of a word in a document.

Term Frequency and Indexing Significance

Luhn: term frequency is useful determining significance for retrieval.

TF-IDF Weighting

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

TF

Term Frequency in a document.

N

total number of documents.

n

total number of documents having the term.

IDF

Inverse Document Frequency
IDF = log₂ N/n
The information content associated with knowing a term is in a particular document.

TF*IDF

Multiplying term frequency by inverse document frequency gives the term weight.

III. Modern Relevance Ranking: Google PageRank Algorithm

Issues in Heterogeneous Collections: Quality, Authoritativeness

Classical IR assumes that every document in the collection is valuable with respect to its subject.

This is not true of the web.

The Google PageRank concept is based on the notion that the quality and authoritativeness of a document is based on:

• The citations received (links to) a page.
• The ranking of the citing pages.

Sergey and Brin define PageRanks this way.

We assume page A has pages T1...Tn which point to it (i.e., are citations). The parameter d is a damping factor which can be set between 0 and 1. We usually set d to 0.85. There are more details about d in the next section. Also C(A) is defined as the number of links going out of page A. The PageRank of a page A is given as follows:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks will be one.

Ian Rogers, Page Rank Explained: The Google Pagerank Algorithm and How It Works

Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the Seventh International World Wide Web Conference, Brisbane, Australia, April 1998. On-line version.

Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas, "Finding Authorities and Hubs From Link Structures on the World Wide Web" WWW 10.