01 Boolean retrieval

Question 1

Information Retrievel

Answer 1

IR is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers)

Question 2

Index

Answer 2

The way to avoid linearly scanning the text for each query is to index the docs in advance

Question 3

Terms

Answer 3

Are the indexed units

Question 4

Boolean retreival model

Answer 4

Is a model for information retrieval in which we can pose any query which is in the from of a Boolean expression of terms, that is, in which terms are combined with the operators AND, OR and NOT. The model views each document as just a set of words.

Question 5

Collection (Corpus)

Answer 5

Group of documents over which we perform retrieval task.

Question 6

Ad hoc retrieval

Answer 6

An IR task. In it, a system aims to provide documents from within the collection that are relevant to an arbitrary used information need.

Question 7

Effectiveness

Answer 7

Two key factors:

Precision
What fraction of the returned results are relevant to the information need?

Recall
What fraction of the relevant documents in the collection were returned by the system?

Question 8

Inverted index (II, inverted file)

Answer 8

We keep a dictionary of terms. For each term, we have a list that records which documents the term occurs in

Question 9

Posting

Answer 9

Each item in a Inverted Index records the docID of the term.

Question 10

Posting lists

Answer 10

The list of postings is a posting list

Question 11

Postings

Answer 11

All posting lists put together.

Question 12

Dictionary

Answer 12

All terms in the II put together

Question 13

Sorting

Answer 13

Core idea of II. Terms must be alphabetically ordered.

Question 14

Posting lists intersection (merging posting list)

Answer 14

Must intersect postings lists to find docs that contain both terms.
Common intersection algorithm:

1. Maintain pointers to each PL, starting at the beginning
2. Compare the docID pointed to by the pointers
3. If they are the same, put posting in result list and advance both pointers 4. Otherwise, advance the pointer pointing to the smaller docID and re- peat from step 2.

O(x + y) operations where x and y are the length of the postinglist, but formally the complexity is O(N) where N is the size of the corpus.

Important! To use this algorithm, the PLs must be sorted by a single global ordering.

Question 15

Query optimization

Answer 15

Is the process of selecting how to organize the work of answering a query so that the least total amount of work needs to be done by the systen

Question 16

Ranked retrieval models

Answer 16

The boolean retrieval model contrasts with ranked retrieval models such as the vector space model, in which the system decides which documents best satisfy the query.

Question 17

Proximity operatos

Answer 17

Is a way of specifying that two terms in a query must occur close to each other in the document. More info at Lecture 2: Positional index

Question 18

Term frequency

Answer 18

The number of times a term occurs in a docuemnt