Online edition (c) 2009 Cambridge UP
DRAFT! © April 1, 2009 Cambridge University Press. Feedback welcome. 1
1 Boolean retrieval
The meaning of the term information retrieval can be very broad. Just getting
a credit card out of your wallet so that you can type in the card number
is a form of information retrieval. However, as an academic ﬁeld of study,
information retrieval might be deﬁned thus:INFORMATION
RETRIEVAL
Information retrieval (IR) is ﬁnding material (usually documents) of
an unstructured nature (usually text) that satisﬁes an information need
from within large collections (usually stored on computers).
As deﬁned in this way, information retrieval used to be an activity that only
a few people engaged in: reference librarians, paralegals, and similar professional
searchers. Now the world has changed, and hundreds of millions
of people engage in information retrieval every day when they use a web
search engine or search their email.1 Information retrieval is fast becoming
the dominant form of information access, overtaking traditional databasestyle
searching (the sort that is going on when a clerk says to you: “I’m sorry,
I can only look up your order if you can give me your Order ID”).
IR can also cover other kinds of data and information problems beyond
that speciﬁed in the core deﬁnition above. The term “unstructured data”
refers to data which does not have clear, semantically overt, easy-for-a-computer
structure. It is the opposite of structured data, the canonical example of
which is a relational database, of the sort companies usually use to maintain
product inventories and personnel records. In reality, almost no data
are truly “unstructured”. This is deﬁnitely true of all text data if you count
the latent linguistic structure of human languages. But even accepting that
the intended notion of structure is overt structure, most text has structure,
such as headings and paragraphs and footnotes, which is commonly represented
in documents by explicit markup (such as the coding underlying web
1. In modern parlance, the word “search” has tended to replace “(information) retrieval”; the
term “search” is quite ambiguous, but in context we use the two synonymously.
Online edition (c) 2009 Cambridge UP
2 1 Boolean retrieval
pages). IR is also used to facilitate “semistructured” search such as ﬁnding a
document where the title contains Java and the body contains threading.
The ﬁeld of information retrieval also covers supporting users in browsing
or ﬁltering document collections or further processing a set of retrieved documents.
Given a set of documents, clustering is the task of coming up with a
good grouping of the documents based on their contents. It is similar to arranging
books on a bookshelf according to their topic. Given a set of topics,
standing information needs, or other categories (such as suitability of texts
for different age groups), classiﬁcation is the task of deciding which class(es),
if any, each of a set of documents belongs to. It is often approached by ﬁrst
manually classifying some documents and then hoping to be able to classify
new documents automatically.
Information retrieval systems can also be distinguished by the scale at
which they operate, and it is useful to distinguish three prominent scales.
In web search, the system has to provide search over billions of documents
stored on millions of computers. Distinctive issues are needing to gather
documents for indexing, being able to build systems that work efﬁciently
at this enormous scale, and handling particular aspects of the web, such as
the exploitation of hypertext and not being fooled by site providers manipulating
page content in an attempt to boost their search engine rankings,
given the commercial importance of the web. We focus on all these issues
in Chapters 19–21. At the other extreme is personal information retrieval. In
the last few years, consumer operating systems have integrated information
retrieval (such as Apple’s Mac OS X Spotlight or Windows Vista’s Instant
Search). Email programs usually not only provide search but also text classiﬁcation:
they at least provide a spam (junk mail) ﬁlter, and commonly also
provide either manual or automatic means for classifying mail so that it can
be placed directly into particular folders. Distinctive issues here include handling
the broad range of document types on a typical personal computer,
and making the search system maintenance free and sufﬁciently lightweight
in terms of startup, processing, and disk space usage that it can run on one
machine without annoying its owner. In between is the space of enterprise,
institutional, and domain-speciﬁc search, where retrieval might be provided for
collections such as a corporation’s internal documents, a database of patents,
or research articles on biochemistry. In this case, the documents will typically
be stored on centralized ﬁle systems and one or a handful of dedicated
machines will provide search over the collection. This book contains techniques
of value over this whole spectrum, but our coverage of some aspects
of parallel and distributed search in web-scale search systems is comparatively
light owing to the relatively small published literature on the details
of such systems. However, outside of a handful of web search companies, a
software developer is most likely to encounter the personal search and enterprise
scenarios.
Online edition (c) 2009 Cambridge UP
1.1 An example information retrieval problem 3
In this chapter we begin with a very simple example of an information
retrieval problem, and introduce the idea of a term-document matrix (Section
1.1) and the central inverted index data structure (Section 1.2). We will
then examine the Boolean retrieval model and how Boolean queries are processed
(Sections 1.3 and 1.4).
1.1 An example information retrieval problem
A fat book which many people own is Shakespeare’s Collected Works. Suppose
you wanted to determine which plays of Shakespeare contain the words
Brutus AND Caesar AND NOT Calpurnia. One way to do that is to start at the
beginning and to read through all the text, noting for each play whether
it contains Brutus and Caesar and excluding it from consideration if it contains
Calpurnia. The simplest form of document retrieval is for a computer
to do this sort of linear scan through documents. This process is commonly
referred to as grepping through text, after the Unix command grep, whichGREP
performs this process. Grepping through text can be a very effective process,
especially given the speed of modern computers, and often allows useful
possibilities for wildcard pattern matching through the use of regular expressions.
With modern computers, for simple querying of modest collections
(the size of Shakespeare’s Collected Works is a bit under one million words
of text in total), you really need nothing more.
But for many purposes, you do need more:
1. To process large document collections quickly. The amount of online data
has grown at least as quickly as the speed of computers, and we would
now like to be able to search collections that total in the order of billions
to trillions of words.
2. To allow more ﬂexible matching operations. For example, it is impractical
to perform the query Romans NEAR countrymen with grep, where NEAR
might be deﬁned as “within 5 words” or “within the same sentence”.
3. To allow ranked retrieval: in many cases you want the best answer to an
information need among many documents that contain certain words.
The way to avoid linearly scanning the texts for each query is to index theINDEX
documents in advance. Let us stick with Shakespeare’s Collected Works,
and use it to introduce the basics of the Boolean retrieval model. Suppose
we record for each document – here a play of Shakespeare’s – whether it
contains each word out of all the words Shakespeare used (Shakespeare used
about 32,000 different words). The result is a binary term-document incidenceINCIDENCE MATRIX
matrix, as in Figure 1.1. Terms are the indexed units (further discussed inTERM
Section 2.2); they are usually words, and for the moment you can think of
Online edition (c) 2009 Cambridge UP
4 1 Boolean retrieval
Antony Julius The Hamlet Othello Macbeth ...
and Caesar Tempest
Cleopatra
Antony 1 1 0 0 0 1
Brutus 1 1 0 1 0 0
Caesar 1 1 0 1 1 1
Calpurnia 0 1 0 0 0 0
Cleopatra 1 0 0 0 0 0
mercy 1 0 1 1 1 1
worser 1 0 1 1 1 0
...
◮ Figure 1.1 A term-document incidence matrix. Matrix element (t, d) is 1 if the
play in column d contains the word in row t, and is 0 otherwise.
them as words, but the information retrieval literature normally speaks of
terms because some of them, such as perhaps I-9 or Hong Kong are not usually
thought of as words. Now, depending on whether we look at the matrix rows
or columns, we can have a vector for each term, which shows the documents
it appears in, or a vector for each document, showing the terms that occur in
it.2
To answer the query Brutus AND Caesar AND NOT Calpurnia, we take the
vectors for Brutus, Caesar and Calpurnia, complement the last, and then do a
bitwise AND:
110100 AND 110111 AND 101111 = 100100
The answers for this query are thus Antony and Cleopatra and Hamlet (Figure
1.2).
The Boolean retrieval model is a model for information retrieval in which weBOOLEAN RETRIEVAL
MODEL can pose any query which is in the form 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.
Let us now consider a more realistic scenario, simultaneously using the
opportunity to introduce some terminology and notation. Suppose we have
N = 1 million documents. By documents we mean whatever units we haveDOCUMENT
decided to build a retrieval system over. They might be individual memos
or chapters of a book (see Section 2.1.2 (page 20) for further discussion). We
will refer to the group of documents over which we perform retrieval as the
(document) collection. It is sometimes also referred to as a corpus (a body ofCOLLECTION
CORPUS texts). Suppose each document is about 1000 words long (2–3 book pages). If
2. Formally, we take the transpose of the matrix to be able to get the terms as column vectors.
Online edition (c) 2009 Cambridge UP
1.1 An example information retrieval problem 5
Antony and Cleopatra, Act III, Scene ii
Agrippa [Aside to Domitius Enobarbus]: Why, Enobarbus,
When Antony found Julius Caesar dead,
He cried almost to roaring; and he wept
When at Philippi he found Brutus slain.
Hamlet, Act III, Scene ii
Lord Polonius: I did enact Julius Caesar: I was killed i’ the
Capitol; Brutus killed me.
◮ Figure 1.2 Results from Shakespeare for the query Brutus AND Caesar AND NOT
Calpurnia.
we assume an average of 6 bytes per word including spaces and punctuation,
then this is a document collection about 6 GB in size. Typically, there might
be about M = 500,000 distinct terms in these documents. There is nothing
special about the numbers we have chosen, and they might vary by an order
of magnitude or more, but they give us some idea of the dimensions of the
kinds of problems we need to handle. We will discuss and model these size
assumptions in Section 5.1 (page 86).
Our goal is to develop a system to address the ad hoc retrieval task. This isAD HOC RETRIEVAL
the most standard IR task. In it, a system aims to provide documents from
within the collection that are relevant to an arbitrary user information need,
communicated to the system by means of a one-off, user-initiated query. An
information need is the topic about which the user desires to know more, andINFORMATION NEED
is differentiated from a query, which is what the user conveys to the com-QUERY
puter in an attempt to communicate the information need. A document is
relevant if it is one that the user perceives as containing information of valueRELEVANCE
with respect to their personal information need. Our example above was
rather artiﬁcial in that the information need was deﬁned in terms of particular
words, whereas usually a user is interested in a topic like “pipeline
leaks” and would like to ﬁnd relevant documents regardless of whether they
precisely use those words or express the concept with other words such as
pipeline rupture. To assess the effectiveness of an IR system (i.e., the quality ofEFFECTIVENESS
its search results), a user will usually want to know two key statistics about
the system’s returned results for a query:
Precision: What fraction of the returned results are relevant to the informa-PRECISION
tion need?
Recall: What fraction of the relevant documents in the collection were re-RECALL
turned by the system?
Online edition (c) 2009 Cambridge UP
6 1 Boolean retrieval
Detailed discussion of relevance and evaluation measures including precision
and recall is found in Chapter 8.
We now cannot build a term-document matrix in a naive way. A 500K ×
1M matrix has half-a-trillion 0’s and 1’s – too many to ﬁt in a computer’s
memory. But the crucial observation is that the matrix is extremely sparse,
that is, it has few non-zero entries. Because each document is 1000 words
long, the matrix has no more than one billion 1’s, so a minimum of 99.8% of
the cells are zero. A much better representation is to record only the things
that do occur, that is, the 1 positions.
This idea is central to the ﬁrst major concept in information retrieval, the
inverted index. The name is actually redundant: an index always maps backINVERTED INDEX
from terms to the parts of a document where they occur. Nevertheless, inverted
index, or sometimes inverted ﬁle, has become the standard term in information
retrieval.3 The basic idea of an inverted index is shown in Figure 1.3.
We keep a dictionary of terms (sometimes also referred to as a vocabulary orDICTIONARY
VOCABULARY lexicon; in this book, we use dictionary for the data structure and vocabulary
LEXICON
for the set of terms). Then for each term, we have a list that records which
documents the term occurs in. Each item in the list – which records that a
term appeared in a document (and, later, often, the positions in the document)
– is conventionally called a posting.4 The list is then called a postingsPOSTING
POSTINGS LIST list (or inverted list), and all the postings lists taken together are referred to as
the postings. The dictionary in Figure 1.3 has been sorted alphabetically andPOSTINGS
each postings list is sorted by document ID. We will see why this is useful in
Section 1.3, below, but later we will also consider alternatives to doing this
(Section 7.1.5).
1.2 A ﬁrst take at building an inverted index
To gain the speed beneﬁts of indexing at retrieval time, we have to build the
index in advance. The major steps in this are:
1. Collect the documents to be indexed:
Friends, Romans, countrymen. So let it be with Caesar ...
2. Tokenize the text, turning each document into a list of tokens:
Friends Romans countrymen So ...
3. Some information retrieval researchers prefer the term inverted ﬁle, but expressions like index
construction and index compression are much more common than inverted ﬁle construction and
inverted ﬁle compression. For consistency, we use (inverted) index throughout this book.
4. In a (non-positional) inverted index, a posting is just a document ID, but it is inherently
associated with a term, via the postings list it is placed on; sometimes we will also talk of a
(term, docID) pair as a posting.
Online edition (c) 2009 Cambridge UP
1.2 A ﬁrst take at building an inverted index 7
Brutus −→ 1 2 4 11 31 45 173 174
Caesar −→ 1 2 4 5 6 16 57 132 ...
Calpurnia −→ 2 31 54 101
...
Dictionary Postings
◮ Figure 1.3 The two parts of an inverted index. The dictionary is commonly kept
in memory, with pointers to each postings list, which is stored on disk.
3. Do linguistic preprocessing, producing a list of normalized tokens, which
are the indexing terms: friend roman countryman so ...
4. Index the documents that each term occurs in by creating an inverted index,
consisting of a dictionary and postings.
We will deﬁne and discuss the earlier stages of processing, that is, steps 1–3,
in Section 2.2 (page 22). Until then you can think of tokens and normalized
tokens as also loosely equivalent to words. Here, we assume that the ﬁrst
3 steps have already been done, and we examine building a basic inverted
index by sort-based indexing.
Within a document collection, we assume that each document has a unique
serial number, known as the document identiﬁer (docID). During index con-DOCID
struction, we can simply assign successive integers to each new document
when it is ﬁrst encountered. The input to indexing is a list of normalized
tokens for each document, which we can equally think of as a list of pairs of
term and docID, as in Figure 1.4. The core indexing step is sorting this listSORTING
so that the terms are alphabetical, giving us the representation in the middle
column of Figure 1.4. Multiple occurrences of the same term from the same
document are then merged.5 Instances of the same term are then grouped,
and the result is split into a dictionary and postings, as shown in the right
column of Figure 1.4. Since a term generally occurs in a number of documents,
this data organization already reduces the storage requirements of
the index. The dictionary also records some statistics, such as the number of
documents which contain each term (the document frequency, which is hereDOCUMENT
FREQUENCY also the length of each postings list). This information is not vital for a basic
Boolean search engine, but it allows us to improve the efﬁciency of the
5. Unix users can note that these steps are similar to use of the sort and then uniq commands.
Online edition (c) 2009 Cambridge UP
8 1 Boolean retrieval
Doc 1 Doc 2
I did enact Julius Caesar: I was killed
i’ the Capitol; Brutus killed me.
So let it be with Caesar. The noble Brutus
hath told you Caesar was ambitious:
term docID
I 1
did 1
enact 1
julius 1
caesar 1
I 1
was 1
killed 1
i’ 1
the 1
capitol 1
brutus 1
killed 1
me 1
so 2
let 2
it 2
be 2
with 2
caesar 2
the 2
noble 2
brutus 2
hath 2
told 2
you 2
caesar 2
was 2
ambitious 2
=⇒
term docID
ambitious 2
be 2
brutus 1
brutus 2
capitol 1
caesar 1
caesar 2
caesar 2
did 1
enact 1
hath 1
I 1
I 1
i’ 1
it 2
julius 1
killed 1
killed 1
let 2
me 1
noble 2
so 2
the 1
the 2
told 2
you 2
was 1
was 2
with 2
=⇒
term doc. freq. → postings lists
ambitious 1 → 2
be 1 → 2
brutus 2 → 1 → 2
capitol 1 → 1
caesar 2 → 1 → 2
did 1 → 1
enact 1 → 1
hath 1 → 2
I 1 → 1
i’ 1 → 1
it 1 → 2
julius 1 → 1
killed 1 → 1
let 1 → 2
me 1 → 1
noble 1 → 2
so 1 → 2
the 2 → 1 → 2
told 1 → 2
you 1 → 2
was 2 → 1 → 2
with 1 → 2
◮ Figure 1.4 Building an index by sorting and grouping. The sequence of terms
in each document, tagged by their documentID (left) is sorted alphabetically (middle).
Instances of the same term are then grouped by word and then by documentID.
The terms and documentIDs are then separated out (right). The dictionary stores
the terms, and has a pointer to the postings list for each term. It commonly also
stores other summary information such as, here, the document frequency of each
term. We use this information for improving query time efﬁciency and, later, for
weighting in ranked retrieval models. Each postings list stores the list of documents
in which a term occurs, and may store other information such as the term frequency
(the frequency of each term in each document) or the position(s) of the term in each
document.
Online edition (c) 2009 Cambridge UP
1.2 A ﬁrst take at building an inverted index 9
search engine at query time, and it is a statistic later used in many ranked retrieval
models. The postings are secondarily sorted by docID. This provides
the basis for efﬁcient query processing. This inverted index structure is essentially
without rivals as the most efﬁcient structure for supporting ad hoc
text search.
In the resulting index, we pay for storage of both the dictionary and the
postings lists. The latter are much larger, but the dictionary is commonly
kept in memory, while postings lists are normally kept on disk, so the size
of each is important, and in Chapter 5 we will examine how each can be
optimized for storage and access efﬁciency. What data structure should be
used for a postings list? A ﬁxed length array would be wasteful as some
words occur in many documents, and others in very few. For an in-memory
postings list, two good alternatives are singly linked lists or variable length
arrays. Singly linked lists allow cheap insertion of documents into postings
lists (following updates, such as when recrawling the web for updated documents),
and naturally extend to more advanced indexing strategies such as
skip lists (Section 2.3), which require additional pointers. Variable length arrays
win in space requirements by avoiding the overhead for pointers and in
time requirements because their use of contiguous memory increases speed
on modern processors with memory caches. Extra pointers can in practice be
encoded into the lists as offsets. If updates are relatively infrequent, variable
length arrays will be more compact and faster to traverse. We can also use a
hybrid scheme with a linked list of ﬁxed length arrays for each term. When
postings lists are stored on disk, they are stored (perhaps compressed) as a
contiguous run of postings without explicit pointers (as in Figure 1.3), so as
to minimize the size of the postings list and the number of disk seeks to read
a postings list into memory.
?
Exercise 1.1 [⋆]
Draw the inverted index that would be built for the following document collection.
(See Figure 1.3 for an example.)
Doc 1 new home sales top forecasts
Doc 2 home sales rise in july
Doc 3 increase in home sales in july
Doc 4 july new home sales rise
Exercise 1.2 [⋆]
Consider these documents:
Doc 1 breakthrough drug for schizophrenia
Doc 2 new schizophrenia drug
Doc 3 new approach for treatment of schizophrenia
Doc 4 new hopes for schizophrenia patients
a. Draw the term-document incidence matrix for this document collection.
Online edition (c) 2009 Cambridge UP
10 1 Boolean retrieval
Brutus −→ 1 → 2 → 4 → 11 → 31 → 45 → 173 → 174
Calpurnia −→ 2 → 31 → 54 → 101
Intersection =⇒ 2 → 31
◮ Figure 1.5 Intersecting the postings lists for Brutus and Calpurnia from Figure 1.3.
b. Draw the inverted index representation for this collection, as in Figure 1.3 (page 7).
Exercise 1.3 [⋆]
For the document collection shown in Exercise 1.2, what are the returned results for
these queries:
a. schizophrenia AND drug
b. for AND NOT(drug OR approach)
1.3 Processing Boolean queries
How do we process a query using an inverted index and the basic Boolean
retrieval model? Consider processing the simple conjunctive query:SIMPLE CONJUNCTIVE
QUERIES
(1.1) Brutus AND Calpurnia
over the inverted index partially shown in Figure 1.3 (page 7). We:
1. Locate Brutus in the Dictionary
2. Retrieve its postings
3. Locate Calpurnia in the Dictionary
4. Retrieve its postings
5. Intersect the two postings lists, as shown in Figure 1.5.
The intersection operation is the crucial one: we need to efﬁciently intersectPOSTINGS LIST
INTERSECTION postings lists so as to be able to quickly ﬁnd documents that contain both
terms. (This operation is sometimes referred to as merging postings lists:POSTINGS MERGE
this slightly counterintuitive name reﬂects using the term merge algorithm for
a general family of algorithms that combine multiple sorted lists by interleaved
advancing of pointers through each; here we are merging the lists
with a logical AND operation.)
There is a simple and effective method of intersecting postings lists using
the merge algorithm (see Figure 1.6): we maintain pointers into both lists
Online edition (c) 2009 Cambridge UP
1.3 Processing Boolean queries 11
INTERSECT(p1, p2)
1 answer ←
2 while p1 = NIL and p2 = NIL
3 do if docID(p1) = docID(p2)
4 then ADD(answer, docID(p1))
5 p1 ← next(p1)
6 p2 ← next(p2)
7 else if docID(p1) < docID(p2)
8 then p1 ← next(p1)
9 else p2 ← next(p2)
10 return answer
◮ Figure 1.6 Algorithm for the intersection of two postings lists p1 and p2.
and walk through the two postings lists simultaneously, in time linear in
the total number of postings entries. At each step, we compare the docID
pointed to by both pointers. If they are the same, we put that docID in the
results list, and advance both pointers. Otherwise we advance the pointer
pointing to the smaller docID. If the lengths of the postings lists are x and
y, the intersection takes O(x + y) operations. Formally, the complexity of
querying is Θ(N), where N is the number of documents in the collection.6
Our indexing methods gain us just a constant, not a difference in Θ time
complexity compared to a linear scan, but in practice the constant is huge.
To use this algorithm, it is crucial that postings be sorted by a single global
ordering. Using a numeric sort by docID is one simple way to achieve this.
We can extend the intersection operation to process more complicated queries
like:
(1.2) (Brutus OR Caesar) AND NOT Calpurnia
Query optimization is the process of selecting how to organize the work of an-QUERY OPTIMIZATION
swering a query so that the least total amount of work needs to be done by
the system. A major element of this for Boolean queries is the order in which
postings lists are accessed. What is the best order for query processing? Consider
a query that is an AND of t terms, for instance:
(1.3) Brutus AND Caesar AND Calpurnia
For each of the t terms, we need to get its postings, then AND them together.
The standard heuristic is to process terms in order of increasing document
6. The notation Θ(·) is used to express an asymptotically tight bound on the complexity of
an algorithm. Informally, this is often written as O(·), but this notation really expresses an
asymptotic upper bound, which need not be tight (Cormen et al. 1990).
Online edition (c) 2009 Cambridge UP
12 1 Boolean retrieval
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
◮ Figure 1.7 Algorithm for conjunctive queries that returns the set of documents
containing each term in the input list of terms.
frequency: if we start by intersecting the two smallest postings lists, then all
intermediate results must be no bigger than the smallest postings list, and we
are therefore likely to do the least amount of total work. So, for the postings
lists in Figure 1.3 (page 7), we execute the above query as:
(1.4) (Calpurnia AND Brutus) AND Caesar
This is a ﬁrst justiﬁcation for keeping the frequency of terms in the dictionary:
it allows us to make this ordering decision based on in-memory data before
accessing any postings list.
Consider now the optimization of more general queries, such as:
(1.5) (madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)
As before, we will get the frequencies for all terms, and we can then (conservatively)
estimate the size of each OR by the sum of the frequencies of its
disjuncts. We can then process the query in increasing order of the size of
each disjunctive term.
For arbitrary Boolean queries, we have to evaluate and temporarily store
the answers for intermediate expressions in a complex expression. However,
in many circumstances, either because of the nature of the query language,
or just because this is the most common type of query that users submit, a
query is purely conjunctive. In this case, rather than viewing merging postings
lists as a function with two inputs and a distinct output, it is more efﬁcient
to intersect each retrieved postings list with the current intermediate
result in memory, where we initialize the intermediate result by loading the
postings list of the least frequent term. This algorithm is shown in Figure 1.7.
The intersection operation is then asymmetric: the intermediate results list
is in memory while the list it is being intersected with is being read from
disk. Moreover the intermediate results list is always at least as short as the
other list, and in many cases it is orders of magnitude shorter. The postings
Online edition (c) 2009 Cambridge UP
1.3 Processing Boolean queries 13
intersection can still be done by the algorithm in Figure 1.6, but when the
difference between the list lengths is very large, opportunities to use alternative
techniques open up. The intersection can be calculated in place by
destructively modifying or marking invalid items in the intermediate results
list. Or the intersection can be done as a sequence of binary searches in the
long postings lists for each posting in the intermediate results list. Another
possibility is to store the long postings list as a hashtable, so that membership
of an intermediate result item can be calculated in constant rather than linear
or log time. However, such alternative techniques are difﬁcult to combine
with postings list compression of the sort discussed in Chapter 5. Moreover,
standard postings list intersection operations remain necessary when both
terms of a query are very common.
?
Exercise 1.4 [⋆]
For the 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?
a. Brutus AND NOT Caesar
b. Brutus OR NOT Caesar
Exercise 1.5 [⋆]
Extend the postings merge algorithm to arbitrary Boolean query formulas. What is
its time complexity? For instance, consider:
c. (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)
Can we always merge in linear time? Linear in what? Can we do better than this?
Exercise 1.6 [⋆⋆]
We can use distributive laws for AND and OR to rewrite queries.
a. Show how to rewrite the query in Exercise 1.5 into disjunctive normal form using
the distributive laws.
b. Would the resulting query be more or less efﬁciently evaluated than the original
form of this query?
c. Is this result true in general or does it depend on the words and the contents of
the document collection?
Exercise 1.7 [⋆]
Recommend a query processing order for
d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
given the following postings list sizes:
Online edition (c) 2009 Cambridge UP
14 1 Boolean retrieval
Term Postings size
eyes 213312
kaleidoscope 87009
marmalade 107913
skies 271658
tangerine 46653
trees 316812
Exercise 1.8 [⋆]
If the query is:
e. friends AND romans AND (NOT countrymen)
how could we use the frequency of countrymen in evaluating the best query evaluation
order? In particular, propose a way of handling negation in determining the order of
query processing.
Exercise 1.9 [⋆⋆]
For a conjunctive query, is processing postings lists in order of size guaranteed to be
optimal? Explain why it is, or give an example where it isn’t.
Exercise 1.10 [⋆⋆]
Write out a postings merge algorithm, in the style of Figure 1.6 (page 11), for an x OR y
query.
Exercise 1.11 [⋆⋆]
How should the Boolean query x AND NOT y be handled? Why is naive evaluation
of this query normally very expensive? Write out a postings merge algorithm that
evaluates this query efﬁciently.
1.4 The extended Boolean model versus ranked retrieval
The Boolean retrieval model contrasts with ranked retrieval models such as theRANKED RETRIEVAL
MODEL vector space model (Section 6.3), in which users largely use free text queries,
FREE TEXT QUERIES
that is, just typing one or more words rather than using a precise language
with operators for building up query expressions, and the system decides
which documents best satisfy the query. Despite decades of academic research
on the advantages of ranked retrieval, systems implementing the Boolean
retrieval model were the main or only search option provided by large
commercial information providers for three decades until the early 1990s (approximately
the date of arrival of the World Wide Web). However, these
systems did not have just the basic Boolean operations (AND, OR, and NOT)
which we have presented so far. A strict Boolean expression over terms with
an unordered results set is too limited for many of the information needs
that people have, and these systems implemented extended Boolean retrieval
models by incorporating additional operators such as term proximity operators.
A proximity operator is a way of specifying that two terms in a queryPROXIMITY OPERATOR
Online edition (c) 2009 Cambridge UP
1.4 The extended Boolean model versus ranked retrieval 15
must occur close to each other in a document, where closeness may be measured
by limiting the allowed number of intervening words or by reference
to a structural unit such as a sentence or paragraph.
 Example 1.1: Commercial Boolean searching: Westlaw. Westlaw (http://www.westlaw.com/)
is the largest commercial legal search service (in terms of the number of paying subscribers),
with over half a million subscribers performing millions of searches a day
over tens of terabytes of text data. The service was started in 1975. In 2005, Boolean
search (called “Terms and Connectors” by Westlaw) was still the default, and used
by a large percentage of users, although ranked free text querying (called “Natural
Language” by Westlaw) was added in 1992. Here are some example Boolean queries
on Westlaw:
Information need: Information on the legal theories involved in preventing the
disclosure of trade secrets by employees formerly employed by a competing
company. Query: "trade secret" /s disclos! /s prevent /s employe!
Information need: Requirements for disabled people to be able to access a work-
place.
Query: disab! /p access! /s work-site work-place (employment /3 place)
Information need: Cases about a host’s responsibility for drunk guests.
Query: host! /p (responsib! liab!) /p (intoxicat! drunk!) /p guest
Note the long, precise queries and the use of proximity operators, both uncommon
in web search. Submitted queries average about ten words in length. Unlike web
search conventions, a space between words represents disjunction (the tightest binding
operator), & is AND and /s, /p, and /k ask for matches in the same sentence,
same paragraph or within k words respectively. Double quotes give a phrase search
(consecutive words); see Section 2.4 (page 39). The exclamation mark (!) gives a trailing
wildcard query (see Section 3.2, page 51); thus liab! matches all words starting
with liab. Additionally work-site matches any of worksite, work-site or work site; see
Section 2.2.1 (page 22). Typical expert queries are usually carefully deﬁned and incrementally
developed until they obtain what look to be good results to the user.
Many users, particularly professionals, prefer Boolean query models. Boolean
queries are precise: a document either matches the query or it does not. This offers
the user greater control and transparency over what is retrieved. And some domains,
such as legal materials, allow an effective means of document ranking within a
Boolean model: Westlaw returns documents in reverse chronological order, which is
in practice quite effective. In 2007, the majority of law librarians still seem to recommend
terms and connectors for high recall searches, and the majority of legal
users think they are getting greater control by using them. However, this does not
mean that Boolean queries are more effective for professional searchers. Indeed, experimenting
on a Westlaw subcollection, Turtle (1994) found that free text queries
produced better results than Boolean queries prepared by Westlaw’s own reference
librarians for the majority of the information needs in his experiments. A general
problem with Boolean search is that using AND operators tends to produce high precision
but low recall searches, while using OR operators gives low precision but high
recall searches, and it is difﬁcult or impossible to ﬁnd a satisfactory middle ground.
In this chapter, we have looked at the structure and construction of a basic
Online edition (c) 2009 Cambridge UP
16 1 Boolean retrieval
inverted index, comprising a dictionary and postings lists. We introduced
the Boolean retrieval model, and examined how to do efﬁcient retrieval via
linear time merges and simple query optimization. In Chapters 2–7 we will
consider in detail richer query models and the sort of augmented index structures
that are needed to handle them efﬁciently. Here we just mention a few
of the main additional things we would like to be able to do:
1. We would like to better determine the set of terms in the dictionary and
to provide retrieval that is tolerant to spelling mistakes and inconsistent
choice of words.
2. It is often useful to search for compounds or phrases that denote a concept
such as “operating system”. As the Westlaw examples show, we might also
wish to do proximity queries such as Gates NEAR Microsoft. To answer
such queries, the index has to be augmented to capture the proximities of
terms in documents.
3. A Boolean model only records term presence or absence, but often we
would like to accumulate evidence, giving more weight to documents that
have a term several times as opposed to ones that contain it only once. To
be able to do this we need term frequency information (the number of timesTERM FREQUENCY
a term occurs in a document) in postings lists.
4. Boolean queries just retrieve a set of matching documents, but commonly
we wish to have an effective method to order (or “rank”) the returned
results. This requires having a mechanism for determining a document
score which encapsulates how good a match a document is for a query.
With these additional ideas, we will have seen most of the basic technology
that supports ad hoc searching over unstructured information. Ad hoc
searching over documents has recently conquered the world, powering not
only web search engines but the kind of unstructured search that lies behind
the large eCommerce websites. Although the main web search engines differ
by emphasizing free text querying, most of the basic issues and technologies
of indexing and querying remain the same, as we will see in later chapters.
Moreover, over time, web search engines have added at least partial implementations
of some of the most popular operators from extended Boolean
models: phrase search is especially popular and most have a very partial
implementation of Boolean operators. Nevertheless, while these options are
liked by expert searchers, they are little used by most people and are not the
main focus in work on trying to improve web search engine performance.
?
Exercise 1.12 [⋆]
Write a query using Westlaw syntax which would ﬁnd any of the words professor,
teacher, or lecturer in the same sentence as a form of the verb explain.
Online edition (c) 2009 Cambridge UP
1.5 References and further reading 17
Exercise 1.13 [⋆]
Try using the Boolean search features on a couple of major web search engines. For
instance, choose a word, such as burglar, and submit the queries (i) burglar, (ii) burglar
AND burglar, and (iii) burglar OR burglar. Look at the estimated number of results and
top hits. Do they make sense in terms of Boolean logic? Often they haven’t for major
search engines. Can you make sense of what is going on? What about if you try
different words? For example, query for (i) knight, (ii) conquer, and then (iii) knight OR
conquer. What bound should the number of results from the ﬁrst two queries place
on the third query? Is this bound observed?
1.5 References and further reading
The practical pursuit of computerized information retrieval began in the late
1940s (Cleverdon 1991, Liddy 2005). A great increase in the production of
scientiﬁc literature, much in the form of less formal technical reports rather
than traditional journal articles, coupled with the availability of computers,
led to interest in automatic document retrieval. However, in those days, document
retrieval was always based on author, title, and keywords; full-text
search came much later.
The article of Bush (1945) provided lasting inspiration for the new ﬁeld:
“Consider a future device for individual use, which is a sort of mechanized
private ﬁle and library. It needs a name, and, to coin one at
random, ‘memex’ will do. A memex is a device in which an individual
stores all his books, records, and communications, and which is mechanized
so that it may be consulted with exceeding speed and ﬂexibility.
It is an enlarged intimate supplement to his memory.”
The term Information Retrieval was coined by Calvin Mooers in 1948/1950
(Mooers 1950).
In 1958, much newspaper attention was paid to demonstrations at a conference
(see Taube and Wooster 1958) of IBM “auto-indexing” machines, based
primarily on the work of H. P. Luhn. Commercial interest quickly gravitated
towards Boolean retrieval systems, but the early years saw a heady debate
over various disparate technologies for retrieval systems. For example Mooers
(1961) dissented:
“It is a common fallacy, underwritten at this date by the investment of
several million dollars in a variety of retrieval hardware, that the algebra
of George Boole (1847) is the appropriate formalism for retrieval
system design. This view is as widely and uncritically accepted as it is
wrong.”
The observation of AND vs. OR giving you opposite extremes in a precision/
recall tradeoff, but not the middle ground comes from (Lee and Fox 1988).
Online edition (c) 2009 Cambridge UP
18 1 Boolean retrieval
The book (Witten et al. 1999) is the standard reference for an in-depth comparison
of the space and time efﬁciency of the inverted index versus other
possible data structures; a more succinct and up-to-date presentation appears
in Zobel and Moffat (2006). We further discuss several approaches in
Chapter 5.
Friedl (2006) covers the practical usage of regular expressions for searching.REGULAR EXPRESSIONS
The underlying computer science appears in (Hopcroft et al. 2000).