Information Retrieval Exercises

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

2

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

first 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 find 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 different 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

3

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.

B.

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.

4

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 effect?

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

modified for this purpose? Are their complexity modified?

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.

5

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 figure the curves of tfl and tff 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 influence 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 modification/adding to the inverted index structure of the collection?

6

• 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)?

7