01 Boolean Retreival

Question 1

Why is grep not the solution?

Answer 1

• Slow (for large collections)
• grep is line-oriented, IR is document-oriented
• Other operations (e.g., find the word Romans near
  countryman) not feasible

Question 2

Why incidence matrix is not good?

Answer 2

• Matrix is extremely sparse.

Question 3

What is a better representation than incidence matrix?

Answer 3

Inverted index: only record the 1s

Question 4

What is inverted index?

Answer 4

• For each term t, we store a list of all documents that contain t.
• Consists of dictionary and postings

Question 5

How is inverted index constructed?

Answer 5

1.Collect the documents
2. Tokenize
3. Linguistic preprocessing
4. Index the documents > sort > create posting list and count document frequency

Question 6

What is the runtime for conjuctive query (AND) ?

Answer 6

linear in the sum length of the postings lists

only works if postings lists are sorted

Question 7

What are boolean queries?

Answer 7

• queries that use and, or and not to join
  query terms
• Views each document as a set of terms
• Is precise: Document matches condition or not

Question 8

Name commercially successful Boolean retrieval systems

Answer 8

1. Westlaw
2. PubMed

Question 9

What is the best order for processing a query
that is an and of n terms, n > 2?

Example query: Brutus AND Calpurnia AND Caesar

Answer 9

Process in order of increasing frequency

Start with the shortest postings list, then keep cutting further

Question 10

How to process :
(madding or crowd) and (ignoble or strife) and. . .

Answer 10

• Get frequencies for all terms
• Estimate the size of each or by the sum of its frequencies (conservative)
• Process in increasing order of or sizes