Information Retrieval

Master DSC 2A

Exercises 2020–21

Michel Beigbeder

1 Exercises for lecture 1

Exercise 1

Inverted Index Example

Here is a collection of ten documents (one line, one document). Build its

inverted index usable for a boolean search. Give a represention of this index

both with postings lists and with an incidence matrix.

Please Please Me

Hey Jude

A Day in the Life

I Want To Hold Your Hand

A Hard Day’s Night

Long, Long, Long

The Long and Winding Road

Love Me Do

Love You To

Please Mr. Postman

Exercise 2

Complexity (1.4 from 2009-BOOK-manning)

For the two queries below, can we still run through the intersection in time

O(x + y), where x and y are the lengths of the postings lists for Brutus and

Caesar? If not, what can we achieve?

Query: Brutus AND NOT Caesar

Query: Brutus OR NOT Caesar

Exercise 3

Indexing Algorithm

Write the skeleton of an indexing program which works on ﬁles with one

document per ﬁle.

Exercise 4

Boolean Processing Order Optimization (1.7 and 1.9 from 2009-

BOOK-manning)

4.1. Recommend a query processing order for

Query:

(kaleidoscope OR eyes)

(tangerine OR trees) AND (marmalade OR skies) AND

given the following postings list sizes:

Terme t

eyes

kaleidoscope

marmalade

skies

tangerine

trees

df (t)

213 312

87 009

107 913

271 658

46 653

316 812

4.2. For a conjunctive query, is processing postings lists in order of size guar-

anteed to be optimal? Explain why it is, or give an example where it

isn’t.

** Exercise 5

Boolean querying

The Westlaw query language provides proximity operators /s and /p. The

ﬁrst one is at the sentence level and the second one is at the paragraph level. It

also provides the classical boolean operators: AND represented by the & and the

OR represented by the space character. Fig. 1 displays the best documentation

I found about the Westlaw query language (You can try to ﬁnd a more recent

or a better documentation).

Figure 1: The best documentation I found about the Westlaw query language.

Here are ten queries where A, B, and C represents three diﬀerent terms:

Q1 = A & B

Q2 = A B

Q3 = A /s B

Q4 = (A /s B) /s C

Q5 = (A & B) /s C

Q6 = A & (B /s C)

Q7 = A & B /s C

Q8 = (A /s C) & (B /s C)

Q9 = (A B) /s C

PluralsIf you enter the singular form of a term, Westlaw automatically retrieves the plural form as well; this is true for all regular andmost irregular plurals. If you enter the plural form, only the plural is retrieved. For example, if you type warrant, you retrievewarrantand warrants; if you type woman, you retrieve womanand women; and if you type summons, you retrieve summonsbut not summon. Choosing ConnectorsIn addition to choosing terms for your query, you must also choose connectors to specify the relationships between your searchterms. Click a connector in the Add Connectors or Expanderslist at the bottom of a database Search page to add the connectorsto your query, or click Help next to Add Connectors or Expandersto view a list of connectors and brief explanations of theirfunction in a search.Connector TypeTo retrieve documents that contain ExampleAND&both search termsnarcotics & warrantORa spaceeither search term or both termscarautomobileGrammatical/psearch terms in the same paragraphhearsay /p utteranceConnectors/ssearch terms in the same sentencedesign /s defect+sthe first term preceding the second in the same sentenceattorney +s feeNumerical/nsearch terms within nterms of each otherpersonal /3 jurisdictionConnectors(wherenis a number from 1 to 255)+nthe first term preceding the second byntermsjohn +2 roberts(where nis a number from 1 to 255)Phrase“ ”search terms appearing in the same order“attractive nuisance”as in the quotation marksConnector TypeTo exclude documents that contain ExampleBUTNOT%the terms following the percent symbolr.i.c.o. % “puerto rico”AND connector Use the AND connector (&) to retrieve documents containing two or more search terms anywhere in the document. Forexample, the query seat-belt & mitigat! requires that all forms of the compound term seat-beltand any word with the rootmitigat appear in the document. Keep in mind that when you use the AND connector, the terms may appear on different pages.For this reason, you will often find it desirable to use more restrictive connectors. OR connector Use the OR connector, represented by a space, to search for alternative terms. For example, the query attorney lawyer counselretrieves any document containing at least one of these terms. Same paragraph connectors (/p, +p) The same paragraph connectors require search terms to appear in the same paragraph in a document. If you are not sure whichconnector to use, try /p first. For example, the query pit-bull bull-terrier /p attack! retrieves documents in which forms of theterms pit-bull or bull-terrierappear in the same paragraph with any word with the root attack. You can use the +p connector tospecify that the first term precede the second term within the same paragraph. Same sentence connectors (/s, +s) The same sentence connectors require search terms to appear in the same sentence in a document. For example, the querydesign! /s defect! retrieves documents in which any words with the roots designand defectappear in the same sentence.Documents containing phrases such as the following would be retrieved: !liability for a defectively designedproduct !resulting from alleged designand manufacturing defects!the defendant negligently designedthe defectivesafety latchYou can use the +s connector to specify that the first term precede the second term within the same sentence. Q10 = (A /s C) (B /s C)

And now we consider eight documents. These documents are very short. All

of them only contains one paragraph, of one or two sentences. The last word of

a sentence is followed by a dot.

D1 = A.

D2 = B.

D3 = A.

D4 = B C.

D5 = A.

B C.

D6 = A B.

B C.

D7 = A C.

B C.

D8 = A B C.

5.1. Indicate what documents match what queries.

2 Exercises for lecture 2

Exercise 1

Collection Statistics

Explain and comment variations between lines on the table of Slide 18 about

statistics on the Reuters-RCV1 collection.

Exercise 2

Porter’s stemmer

Concerning the Porter’s stemmer rules displayed on Slide 11

2.1. Why does the rule ss → ss appear as it seems to have no eﬀect?

2.2. Apply these rules to the words: circus canaries ponies boss.

2.3. What rule should be added to stem pony too?

2.4. The stemmer output for ponies looks strange as it does not belong to

an usual dictionary. Is this noxious for retrieval?

Exercise 3

Indexing Algorithms Complexity

What are the complexity of the two indexing algorithms of Slides 13–14:

1. Sorted Based Indexing

2. List Memory Indexing

Exercise 4

Positional Indexing

Positions of all the tokens of all types (terms) are to be kept in the index.

Among the two indexing algorithms SBI and LMI, which ones can easily be

modiﬁed for this purpose? Are their complexity modiﬁed?

Exercise 5

Heaps’ Law

Indexing the New York Times between 1990 and 1994 generates a vocabulary

of 1 million types and 400 millions tokens (with some choices of normalization,

digit processing, etc.) Make a prediction of the new vocabulary size and the

number of tokens when indexing the same newspaper between 1990 and 1999.

Precise what assumptions you have to make.

3 Exercises for lecture 3

Exercise 1

Vector Models

1.1. Precise the image (i.e. range) for each tf functions and each idf functions

on slides 26 and 27 of Lecture 2.

1.2. Draw on a single ﬁgure the curves of tﬂ and tﬀ for a given K(d) with

the values 1, 2, 5, 10.

Exercise 2

Vector Model and idf

Indexing a collection of 806 791 documents gives the following postings lists,

sorted by document id:

car,df = 18 165 −→ D1,tf = 27 → D2,tf = 4 → D3,tf = 24 → . . .

auto,df = 6 723 −→ D1,tf = 3 → D2,tf = 33 → D4,. . .

insurance,df = 19 241 −→ D2,tf = 33 → D3,tf = 29 → . . .

best,df = 25 235 −→ D1,tf = 14 → D3,tf = 17 → . . .

2.1. What are the values of tf (auto, D3), tf (insurance, D1), and tf (best, D2)?

2.2. What is the idft value of a term that appears in every documents? Com-

pare with the use of a stop list.

2.3. Compute the idft, and thent the ntn weights of the four terms car, auto,

insurance and best in the three documents D1, D2 and D3.

2.4. How does the base of the logarithm of formula idft inﬂuence the document

scores? If logarithm to base 2 is considered, suggest a simple method to

approximate its value with integer arithmetic and its implemantation in

a programming language.

Exercise 3

Stemming

3.1. We are interested to replace stemming at index time by stemming at

query time. More precisely i) we keep in the dictionnary the non stemmed

terms, and the postings lists associated to these non stemmed terms; ii)

at query time, we accept in the query:

• either A, and only the term A is considered,

• or A+, and all the terms that stem like A are considered.

So cats only matches cats, but cats+ matches cats and cat. Consider:

• how to store the index

What modiﬁcation/adding to the inverted index structure of the collection?

• the BM25 score

How to obtain the necessary data for computing this score?

• the smart’s lnc-ltn weighting

How to obtain the necessary data for computing this score?

Exercise 4

With the indexing algorithms (for instance IndexByPostingsLists) is it pos-

sible to insert in the postings lists the smart’s weights rather than the raw

tf (t, d)?

4 Exercises for lecture 4

Exercise 1

F-Measure

1.1. Prove the equivalence of the two deﬁnitions of the F-measure (with α

and β) of slide 8 (lecture 4).

1.2. Compute α as a function of β.

1.3. Prove that the harmonic mean of two numbers is always lower than their

geometric mean.

1.4. The Dice coeﬃcient measures the resemblance between two sets X and

Y with:

Dice(X, Y ) =

2|X ∩ Y |

|X| + |Y |

Prove that measure F1 is the Dice coeﬃcient between the Retrieved set

and the Relevant Set.

Exercise 2

Recall-Precision

Let us consider an information need for which there are exactly four relevant

documents in the collection. Here are the relevance judgments for the top ten

retrieved documents for two IR systems:

System 1 R N R N N

N N N R R

System 2 N R N N R

R R N N N

(R=Relevant, N=Non-relevant)

2.1. Compute the average precision of these two systems for this information

need.

2.2. Would you have ranked these two IRS in the same order? What is im-

portant to obtain a good average precision?

2.3. What is the R-precision of these two systems? Are the two systems

ranked in the same order with this measure?

Exercise 3

Recall-Precision

NB: Numerical (decimal) values are not the "right" answers. You should show and

explain how you derive your answers. Sometimes, you could leave some values as

fractions p/q of two integers or sums of such fractions.

Here are the relevance judgments for the top twenty answers of an informa-

N N N R N

tion retrieval system in a collection of 10 000 documents:

R R N . N

where:

R means relevant (and hence judged),

N means judged and non relevant,

. means not judged (and considered as non relevant except for measure bpref).

R . . N R

N . .

Twenty documents were judged in the collection, of which eight were judged

relevant. We assume that these are the only ones that are relevant.

3.1. What is the precision on the top twenty answers (P@20)?

3.2. What is the F-measure with β = 1 on the top 20?

3.3. What is(are) the non interpolated precision(s) at 25% recall? What is

the interpolated precision at 25% recall?

3.4. What is the interpolated precision at 33% recall?

3.5. Assuming that this is the full answer list returned by the system, what

is the Average Precision for this topic?

3.6. Now assuming that the system returns all the documents and these are

the ﬁrst 20 ones, what are the minimum and maximum AP values that

the system could obtain?

3.7. What is the relationship between these questions and the TREC evalu-

ation method?

3.8. Compute the bpref of this system for this query.

3.9. What is the bpref for this query of another system who returned:

N R N R .

R R N N N

N N R N R

. .

3.10. Write an algorithm to compute the bpref measure. Give its complexity.

Inputs:

R: the number of judged relevant documents.

N : the number of judged non-relevant documents.

Rel : an associative array of document numbers, the associated value is

either 1 if the document is judged relevant, 0 if the document is judged

non-relevant. The document number is not an element of the set of keys

of the associative array if the document was not judged. So this argument

represents the sets Rel (q) and NRel (q).

l: the ranked list of documents, each element in the list is a 2-uple with

i) the document number (docno); ii) a pointer to the next 2-uple in the

list (next).

Information Retrieval Exercises