1. Boolean Retrieval

1.1 Introduction

1. What information retrieval (IR) is

   • Searching unstructured data (a DB table = structured)
   • Finding what satisfies an information need
   • Searching within a large collection (a set of documents)

2. Money used to go to the structured side; these days it goes to the unstructured side

3. Boolean retrieval model

   • The simplest model for building an IR system
   • The query is a Boolean expression (e.g. Caesar AND Brutus)
   • Returns every document that satisfies the expression, in no order

4. How Google does it

   1. anchor text: if the link text another page uses to link to this page contains the query word, this page shows up even if the word isn't in its body
   2. Word variants: verb forms, spellings, and synonyms show up too
   3. For long queries, results show up even if a few words are missing
   4. When the expression returns too few results, it widens the conditions
   5. ranking: plain Boolean returns results in no order, but Google puts the good results on top (continued in ch6 6.1)

1.2 Inverted index

grep doesn't work → try a matrix → the matrix is too big → store only the 1s = inverted index

1. Why grep doesn't work

   • It's slow (with a large collection it has to read everything from the start)
   • grep works line by line, but IR works document by document
   • Things like NOT~ need the whole document checked, so it's hard
   • It can't do proximity search like "countryman near Romans"

2. Term-document incidence matrix

   • Rows are terms, columns are documents
   • 1 if the term is in the document, 0 if not
   • Each row is a (0/1) vector; do bit operations on these vectors

• Query: Brutus AND Caesar AND NOT Calpurnia / one position = one document, AND the same positions together

                A&C  JC  Tmp  Ham  Oth  Mac
Brutus           1    1   0    1    0    0
Caesar           1    1   0    1    1    1
NOT Calpurnia    1    0   1    1    1    1    (010000 -> 101111)
---------------------------------------------
AND              1    0   0    1    0    0    = 100100

• Result: Anthony and Cleopatra, Hamlet / Julius Caesar drops out because it contains Calpurnia

3. As the collection grows, the matrix blows up
   • token: every word occurrence, duplicates included
   • term: distinct words, duplicates removed
     • e.g. "the the the" has token=3, term=1

• There are 5×10¹¹ cells but at most 10⁹ of them are 1, so almost everything is 0. This is called a sparse matrix. All the space goes to storing 0s, so the conclusion is to write down only the 1s

4. Inverted index

For each term, store only the list of document numbers (docIDs) that contain it

Brutus    -> 1 -> 2 -> 4 -> 11 -> 31 -> 45 -> 173 -> 174
Caesar    -> 1 -> 2 -> 4 -> 5 -> 6 -> 16 -> 57 -> 132
Calpurnia -> 2 -> 31 -> 54 -> 101

• The set of terms (Brutus, Caesar, Calpurnia): dictionary
• posting: a single docID (e.g. 1)
• postings list: the list of postings (-> 1 -> 2 -> 4 ->...)

5. Four steps to build an inverted index

6. Example of building an inverted index

• Doc 1: I did enact Julius Caesar: I was killed i' the Capitol; Brutus killed me.
• Doc 2: So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious:

• df (document frequency): the number of documents a term appears in (not the number of occurrences) / caesar appears twice in Doc 2 but df = 2; i appears twice in Doc 1 but df = 1

Building large indexes is in ch4, compression in ch5, and indexes for ranked retrieval in ch6–7.

1.3 Processing Boolean queries

1. Steps for processing a two-term AND query

   • Query: Brutus AND Calpurnia
   1. Look up Brutus in the dictionary
   2. Fetch Brutus's postings list
   3. Look up Calpurnia in the dictionary
   4. Fetch Calpurnia's postings list
   5. Intersect the two postings lists
   6. Return the result

2. Intersection algorithm (Intersect)

   Brutus    -> 1 -> 2 -> 4 -> 11 -> 31 -> 45 -> 173 -> 174
   Calpurnia -> 2 -> 31 -> 54 -> 101
   Answer    => 2 -> 31
   

   

3. Evaluating the Boolean model

• Any query that is a Boolean expression joined by AND, OR, NOT can be answered.
• It treats a document as a set of terms. It doesn't care how many times a term appears.
• It is precise. A document either matches the condition or it doesn't
• The mainstay of commercial search tools for 30 years
• Spotlight, email search, and intranet search are Boolean too.

4. Westlaw (the largest legal search service by number of paying subscribers)
   • Boolean search is still the default

• Why people prefer Boolean: precision, transparency, control

1.4 Query optimization

1. With three or more ANDs, the order matters

   • Efficiency depends on which operation runs first.

2. So which one goes first?

   • AND the postings lists starting from the shortest (smallest df).

3. Optimized intersection algorithm

   1. Sort terms by increasing df
   2. Start result with the shortest list; keep only the remaining terms
   3. Intersect result with the next list using the 1.3 Intersect
   4. Repeat 3 while terms remain and result isn't empty
   5. Return result
   • If result becomes empty midway, stop right away (ANDing anything after it gives the empty set)
   • e.g. in the order Caesar(2) → Calpurnia(4) → Brutus(8) / Caesar ∩ Calpurnia = 31, ∩ Brutus = 31

   Intersect(<t1, ..., tn>)
    1 terms <- SortByIncreasingFrequency(<t1, ..., tn>)
    2 result <- postings(first(terms))
    3 terms <- rest(terms)
    4 while terms != nil and result != nil
    5 do result <- Intersect(result, postings(first(terms)))
    6    terms <- rest(terms)
    7 return result
   

4. Queries with OR mixed in

   • Get the df of every term
   • Estimate the size of each OR as the sum of its two dfs
   • Process the ORs with the smallest estimated size first
   • This estimate is called conservative, because the sum of the two dfs is an upper bound on the OR result.