Chapter 5

Retrieval Evaluationo PREVIEW

Various automatic retrieval techniques were introduced in the last two chaptersthat have the potential to alter drastically the current operational retrieval en­
vironment. These techniques are not likely to find widespread favor unlesstheir usefulness can be convincingly demonstrated. It is therefore important tounderstand the problems and techniques involved in the evaluation of retrieval
systems and procedures.
This chapter is concerned with the evaluation of retrieval efficiency andeffectiveness.. Various viewpoints can be taken in evaluating a large system.
The text stresses the user viewpoint and examines in detail the various systemcomponents which enter into the evaluation task. On the one hand, the systemshould be able to retrieve a large part of the relevant information contained in
the files, while rejecting a large part of the extraneous information; on the other
hand, the user effort, time, and cost needed for retrieval should be minimized.
The former are characteristics of retrieval effectiveness, often measured by
specific values of the recall and precision of the search output. The latter arecomponents entering into an evaluation of search efficiency.
The generation and computation of the recall and precision measures arecovered in detail in this chapter together with the computation of various alter157

158

CHAPTER 5

native measures of retrieval effectiveness. The best-understood measure ofsystem performance is the cost of using the system. Unfortunately, cost mea­sures are difficult to generate for information retrieval systems. In the end, user
satisfaction will depend on a multiplicity of considerations, including the easewith which the system retrieves wanted information, the cost of the system andamount of user effort required in effecting a search, and various human factors
such as console design and physical location of the search equipment.
1

INTRODUCTION

To understand the retrieval evaluation problem, it is necessary to examine first
the functions of a retrieval system and the various system components. There­
after, the measures that actually reflect system performance can be introduced.
Information retrieval systems give a user population access to a stored col­lection of information items. These systems try to locate and retrieve the items
as rapidly and economically as possible. The value of the information retrieval
system depends on the ability to identify useful information accurately andquickly, the ease of rejecting extraneous items, and the versatility of themethods. Few customers will want a system incapable of retrieving what theywant and of rejecting what they do not want. Nor will they want a system that isdifficult to handle, slow in furnishing responses, or expensive to use. For thesereasons, the evaluation of retrieval systems is of great importance [1-4].
Two kinds of system tests must be distinguished: those concerned withsystems effectiveness, and those concerned with the efficiency of the opera­
tions. The effectiveness of an information system is the ability to furnish infor­
mation services that the users need. On the other hand, efficiency is a measureof the cost or the time necessary to perform a given set of tasks. Ultimately, theviability of a system depends on both the quality and the cost of the operations.
A complete evaluation process is then concerned with both effectiveness andefficiency.
There are many reasons for evaluating retrieval systems. For example, one
might wish to compare one already existing system with another alternative
system. One might also want to determine how system performance changes
when some particular system component changes; for example, one could de­termine the performance changes when the query type is altered or when thesubject area is changed. Still another reason is the evaluation of new systemcomponents that are considered for inclusion in an existing system. In thatcase, the operations of the new system could be simulated before a real systemis actually built.
The following components are needed in a system test: (1) a detailed de­scription of the system and of its components, or alternatively a model of thesystem to be examined; (2) a set of hypotheses to be tested, or a particular pro­totype against which the model is to be measured; (3) a set of criteria reflecting
the performance objectives of the system, and measures permitting a quantifi­
cation of the performance criteria; and finally (4) methods for obtaining andevaluating the data. For example, one might wish to look at the Dialog sys-

RETRIEVAL EVALUATION

159

tem and to determine whether the search speed is fast enough to search the database, the criterion being that maximum allowable response time is 45 seconds,
and the evaluation method consisting in asking each user of that data base tomeasure the response time with a stop watch.
To measure and record system performance, it is desirable to use objec­
tive, quantitative criteria. Objective measurements are relatively easy to inter­
pret and are usually free of bias introduced by the evaluator. Objective mea­
surements are obtainable by recording direct observations using questionnaire
and interview techniques. Alternatively, some mechanical way may be used togather the required data. In either case, parameters (that is, constants whose
value characterizes the usefulness or worth of a system) must be chosen thatare significant for evaluation purposes and are also easily measured and corre­
lated. Some parameters are easily specified— for example, the size of the col­lection and the system response time. Many other important parameters are in­terdependent in complex ways— for example, the ability of the system toretrieve useful materials depends on the representation of the documents, thesearch methods, and the user characteristics. Further, some parameters may
not be defined everywhere in the performance range. For example, the ability
to retrieve useful items cannot be used when dealing with a document collec­
tion that contains no useful documents in a given subject [5-9].
In some circumstances, exact values may be unavailable for certain pa­
rameters, or they may be too laborious to supply. For example, the total num­
ber of documents in a particular subject area may be unknown and may have to
be guessed at using sampling techniques. Probabilistic models are often appli­
cable because many parameters become stable when many observations are
made [10]. For example, the average number of relevant items per query or the
average number of relevant items retrieved by the system can be estimated ei­
ther when many documents are matched against a single request or by treatinga few documents in many different searches.
2

EVALUATION OF RETRIEVAL EFFECTIVENESSA

System Components

Before a detailed examination of the evaluation parameters can be made, it isnecessary to consider briefly the components of an information system and thesystem environment to determine how system performance is affected by thesystem environment and operations. The following system components are ofconcern: acquisitions and input policies, physical form of input, organization of
the search files, indexing language, indexing operation, representation of theinformation items, question analysis, search, and form of presentation of theoutput [11,12].
Parameters related to the input policies include the error rates and timedelays experienced in introducing new items into the collection, the time lag
between receipt of a given item and its appearance in the file; and the collection
coverage, that is, the proportion of potentially relevant information items ac­
tually included in the file. The physical input form , including document format

160

CHAPTER 5

and document length— title, abstract, summary, or full text— immediately af­
fects the indexing and search tasks, as well as the system economics; and theorganization o f the search files impacts the search process, the response time,the effort needed by system operators, and possibly also the system effective­ness.
The indexing language consists of the set of available terms and the rules
used to assign these terms to documents and search requests. During the index­
ing process terms appropriate for the representation of document content arechosen from the indexing language and assigned to the information items in ac­
cordance with established indexing rules. Among the parameters that take on
special significance in this connection are the exhaustivity and specificity of theindexing language. An exhaustive indexing language contains terms covering
all subject areas mentioned in the collection; correspondingly, an exhaustive
indexing product implies that all subject areas are properly reflected in theindex terms assigned to the documents. A specific index language never covers
distinct subjects by using a single term, the terms used being narrow and pre­cise.
Retrieval system performance is often measured by using recall and pre­cision values, where recall measures the ability of the system to retrieve useful
documents, while precision conversely measures the ability to reject uselessmaterials. A high level of indexing exhaustivity tends to ensure high recall bymaking it possible to retrieve most potentially relevant items; at the same time
precision may suffer because some marginally relevant items are likely to be
retrieved also when many different subject areas are covered by the index
terms. When highly specific index terms are used, the precision is expected tobe high, since most retrieved items may be expected to be relevant; the con­verse is true when very broad or general terms are used for indexing purposes
because broad terms will not distinguish the marginal items from the truly rele­vant ones. Thus to obtain high recall an exhaustive indexing is useful in con­junction with an indexing language that provides a variety of approaches tocover the given subject area. To ensure high precision, a highly specific index­
ing language should be used, and the terms should carry additional content indi­
cations such as term weights and relation indications to other terms.
Assuming that the indexing is performed manually by trained persons, thevariables affecting the indexing operation relate not only to the exhaustivity of
the indexing and the specificity of the assigned terms, but also to interindexer
consistency, the influence of indexer experience on performance, and the accu­racy of the assigned terms.
The question analysis and search operations are difficult to characterize.
The assignment of terms from the indexing language to information requests,
the formulation of meaningful Boolean statements, and the comparison of ana­lyzed requests with the stored information are all complicated tasks. In princi­
ple, the content analysis operations are the same for documents and search re­quests, in the sense that the notions of exhaustivity and specificity are equally
as applicable to queries as to documents. Thus, exhaustive query indexing
using highly specific terms should produce maximum search recall and pre-

RETRIEVAL EVALUATION

161

cision. In practice, the query processing is often quite distinct from the docu­
ment indexing because the user is necessarily directly involved in the former
but not the latter. In many systems, the query analysis and search operations
are therefore delegated to trained experts using appropriate input from theusers. Document input, on the other hand, is invariably handled without user
input.
The search operations are also hard to measure using objective parameters
because the role of the user is not well defined in many query formulating en­
vironments. Users are rarely asked to state recall or precision requirements, orto evaluate the output products. Yet search strategies need to be devised that
respond to the users’ specific recall and precision requirements. Among thecharacteristics that should be included in a measurement of search perform­
ance are the type of file organizations used, the type of query-document com­
parison in use, the effect of the search strategy on system response time and on
search performance, and the relevance standards of the system users.
The form o f presentation o f the output is the physical representation of
documents found by the system in response to the user’s query. The appear­
ance of the output affects the amount of user effort needed to look at the search
results and the eventual satisfaction derived from a search. The more complete
the form of the output, the easier is the relevance assessment task for the user.
On the other hand, as the output is expanded from simple document numbers tofull document texts, the time needed to examine the search results also in­creases.
The foregoing discussion makes clear that the components and parametersof the retrieval system affect the system operations and hence the evaluation
results. Each component can be examined separately, or one can compare one
entire system with another. In this case the parameters associated with eachsystem are accepted as constant elements in the evaluation. However, onemust understand that each of the parameters has an effect on the system, andthe importance of each parameter cannot be assessed without taking into ac­
count the purposes for which the system is used. This question is discussed
further in the next few paragraphs.
B Evaluation Viewpoints and the Relevance Problem

Information systems may be examined either from the viewpoint of the users orfrom the viewpoint of system operators and managers. For present purposes,
the system managers may be assumed to include all those who influence thepolicy or the finances of the system, or who are responsible for, or participate
in, the actual system operations. Since it is reasonable to assume that an infor­
mation system exists to meet the needs of its users, the effectiveness criteria ofinterest to the managers are not unlike those of the users. In particular, the sys­
tem should meet the user requirements, and failures in the retrieval of relevantmaterials or in the rejection of nonrelevant items should be minimized. In addi­tion, the managers and to some extent the users are also concerned with thecosts and benefits of the system.

162

CHAPTER 5

Among the many possible evaluation criteria of concern to the user popu­
lation, six have been identified as critical [13,14]:
1 The recall, that is, the ability of the system to present all relevant
items
2 The precision, that is, the ability to present only the relevant items
3 The effort, intellectual or physical, required from the users in formulat­
ing the queries, conducting the search, and screening the output
4 The time interval which elapses between receipt of a user query and thepresentation of system responses
5 The form of presentation of the search output which influences theuser’s ability to utilize the retrieved materials
6 The collection coverage, that is, the extent to which all relevant items
are included in the system
A list of the criteria of interest to the user population is shown together with theprincipal related parameters in Table 5-1.
Table 5-1

User Performance Criteria and Related Parameters

User criteria

Selected related parameters

Recall and precision

Indexing exhaustivity (the more exhaustive, the better the recall)Specificity of indexing language (the more specific, the better the
precision)
Provisions in indexing language for improving recall (synonymrecognition, recognition of term relations, etc.)
Provisions in indexing language for improving precision (use ofterm weights, use of term phrases)
Ability of user population to formulate search requests
Ability to devise adequate search strategies

Response time

Type of storage device and storage organization
Query type
Location of information center
Rate of arrival of customer queries
Collection size

User effort

Characteristics of device permitting access to system
Location of accessing and storage devices
Availability of help from system staff or aids available from system
in nondelegated searches
Amount of retrieved materialType of interaction with system
Ease of formulation of search requests

Form of presentation

Type of accessing and display device
Size of stored information file
Type of output (title, abstract, or full text)

Collection coverage

Type of input device and type and size of storage device
Ease of content analysis (coverage may be more extensive whencontent analysis is simple)
Demand for service (the demand increases with greater coverage)

RETRIEVAL EVALUATION163

Of the six user criteria, all but two are relatively easy to measure. The user
effort can be expressed in part as the time needed for query formulation, theinteraction with the system, and the examination of system outputs. The re­sponse time is directly measurable and the form of presentation of the output iseasy to state. The collection coverage may present some difficulties if thenumber of items of interest in a given subject area is unknown. However, con­sulting published indexes and reference volumes should make it relatively easy
to estimate the total number of items that are in fact available from the data
base.
This leaves the recall and precision measures. These present the greatestdifficulties both conceptually and in practice. An immediate problem in deter­mining the recall and precision is the interpretation of relevance. At least two
definitions of relevance are possible. An objective view takes into account only
a given query and a particular document by stating that
relevance is the correspondence in con text b etw een an information requirement
statem ent (a query) and an article (a docum ent), that is, the exten t to w hich thearticle covers the material that is appropriate to the requirement statem ent [15].

That view makes it possible to consider relevance as a logical property between
a pair of textual items. It is measurable by the degree to which a document
deals with the subject of the user’s information need [16,17]. The objective defi­
nition of relevance does not take into account the particular state of knowledgeof the user during the search operation. A document might be “relevant” eventhough the user might already have been acquainted with the item before theformulation of the search request, or might have become familiar with the doc­
ument through earlier search efforts.
A more subjective view of relevance considers not only the contents of adocument but also the state of knowledge of the user at the time of the search,and the other documents retrieved or available that the user already knows
about. Thus, this notion of relevance depends on the utility of each item to theuser. The pertinent set of items may then be defined as that subset of the stored
items that is appropriate to the user’s information need at the time of retrieval[18,19]. Thus a document may be relevant if it deals with the appropriate topic
classes but it may not be pertinent if the user is already acquainted with its con­tents, or if other documents retrieved earlier already cover the appropriate
topics. All pertinent items are relevant but not vice versa.
Retrieval effectiveness may be easier to measure by using the objective
view of relevance, or topic relatedness, as a criterion for determining relevancethan the subjective notion of pertinence. Even in that case, difficulties may
arise in assessing the relevance of a document to a query. In borderline cases
disagreements may exist among observers about where to place the limit be­
tween various grades of relevance, and how to assess the relevance [20,21],This has led some observers to define relevance in probabilistic terms. In thiscase relevance is a function of the probability that similarities between the

164

CHAPTER 5

query and document vocabularies will lead a user to accept a given item in re­sponse to a particular query [22].
In practice, it is necessary to assume that relevance assessments of docu­
ments to queries are available from an external source to the retrieval system if
an objective system evaluation is to be accomplished. Hence, a system isjudged to be effective if satisfactory evaluation results are obtained using theexternal relevance criteria.
In the next few sections problems relating to the computation and presen­tation of the recall and precision measures are examined and alternative re­trieval evaluation measures are introduced.
*C The Computation of Recall and Precision

Recall is defined as the proportion of relevant material retrieved, while pre­cision is the proportion of retrieved material that is relevant. In an operationalsituation, where information needs may vary from user to user, some custom­ers may require high recall, that is, the retrieval of most everything that is likely
to be of interest, while others may prefer high precision, that is, the rejection of
everything likely to be useless. Everything else being equal, a good system is
one which exhibits both a high recall and a high precision.
If a cut is made through the document collection to distinguish retrieved
items from nonretrieved ones on the one hand as shown in Fig. 5-1, and if pro­cedures are available for separating relevant items from nonrelevant on theother, the standard recall R and standard precision P may be defined as

andnumber of items retrieved and relevant
total relevant in collection( 1)

number of items retrieved and relevant
total retrieved( 2)

RETRELRETNRELNRETRELNRETNREL

Figure 5-1

number relevant and retrieved
number not relevant and retrieved
number relevant and not retrieved
number not relevant and not retrieved

Partition of collection.

RETRIEVAL EVALUATION

165

If relevance judgments are available for each document in the collection withrespect to each search request, and if retrieved and nonretrieved material canbe unambiguously determined, then the computation of these measures isstraightforward [23,24],
In conventional retrieval systems the search requests are presented as
Boolean combinations of search terms. The retrieved document set consists ofall documents exhibiting the exact combination of keywords specified in thequery. That is, each query produces an unordered set of documents that areeither relevant or nonrelevant. Hence for each query a single precision and asingle recall figure can be obtained. Pairs of recall-precision figures can be com­pared for two searches i and j, and whenever RECALL, < RECALL, and PRE­CISION, < PRECISION, the results of search j are judged to be superior tothose for search i. Unfortunately, problems arise when RECALL, < RECALLj
and PRECISION! > PRECISION) or vice versa RECALLi > RECALL, and
PRECISION, < PRECISION) [25]. In these cases, a judgment of superiority
depends on the user’s orientation. That is, the user must determine if the princi­
pal interest is in recall or in precision, and assess the importance of differences
between the recall and precision values. In typical retrieval systems, the recall
will increase as the number of retrieved documents increases; at the same time,
the precision is likely to decrease. Hence users interested in high recall tend to
submit broad queries that retrieve many documents, whereas high-precision
users will submit narrow and specific queries.
Some retrieval systems can produce varying amounts of output. A differ­
ent recall-precision pair can then be obtained for each separate output amount.
The finer the division in quantity of output, the greater the number of available
recall-precision pairs. For example, the retrieval decision can be based on thenumber of matching terms between queries and documents. A partial ranking
can then be defined for the retrieved document set by first retrieving all items
that exhibit at least some arbitrary k matching terms with the query for somejudiciously chosen number k. Next all items with k - 1 matching terms are re­trieved, followed by those with k - 2 matching terms, and so on down to theitems that have no terms in common with the query. In each case the greater
the number of matching query terms the higher the rank of the document in thelist of retrieved documents. In such a system several different pairs of recallprecision values can be computed depending on the number of matching terms
between queries and documents.
In a number of retrieval systems, a ranking is obtained for the retrieved
document set by computing a similarity coefficient for each document-query
pair. This coefficient reflects the similarities between the corresponding index
terms or content representation. The retrieved items are then listed in decreas­
ing order of the query-document similarity coefficients [24]. A pair of recallprecision values can then be computed following the retrieval of each docu­
ment in the ranked order.
The recall measurement requires knowledge of the total number of rele­vant documents in the collection with respect to each query. When the size ofthe document collection is relatively small, it is often possible to obtain rele-

16 6

CHAPTER 5

vance judgments for all documents with respect to each query. When the col­lection sizes are larger, such exhaustive relevance assessments are not nor­mally available. To obtain dependable recall figures, it is then necessary toestimate the total number of relevant documents in the collection. This can bedone by sampling techniques. Thus, relevance assessments are made for only asubset of the items in a collection [26]. Alternatively, a given query could beprocessed using a variety of different search and retrieval methods with the as­
sumption that all relevant documents are probably going to be retrieved by thevarious searches. The results of the searches are then combined into a single

Recall-precision after retrievalof n documents
n
1

2
3
4
5
6
7
8
9
10
11
12
13
14

Document number(x = relevant)
588
589
576
590
986
592
984
988
578
985
103
591
772
990

x
x
x
x

x

RecallPrecision

0.2
0.4
0.4
0.6
0.6
0.8
0.8
0.8
0.8
0.8
0.8
0.8
1.0
1.0

1.0
1.0
0.67
0.75
0.60
0.67
0.57
0.50
0.44
0.40
0.36
0.33
0.38
0.36

(a)

Recall(b)

Figure 5-2 Display of recall and precision results for a sample query. (Collection consists of
200 documents in aerodynamics.) (a) Output ranking of documents in decreasing query-doc­ument similarity order and computation of recall and precision values for a single query,(b) Graph of precision versus recall for sample query of Fig. 5-2a.

RETRIEVAL EVALUATION

167

output list. The list of relevant documents is obtained following a relevance as­
sessment of this single output list.
Consider, as an example of a recall-precision computation, a query which
has a total of five relevant documents included in a collection of two hundred
documents in aerodynamics. The ranks of the relevant items in decreasing
query-document similarity order are shown in Fig. 5-2a as well as the recall andprecision values based on these ranks [27]. The recall-precision values are ob­tained from equations (1) and (2). So if six documents are retrieved including
four of the possible five relevant documents, then this produces a recall of 4/s,
or 0.8. The precision is computed as 4/e (4 relevant out of 6 retrieved), or 0.67.
Given a set of recall-precision value pairs, such as that in Fig. 5-2a, a recall-precision graph can be constructed by plotting the precision against the re­call. The graph for the sample query of Fig. 5-2a is shown in Fig. 5-2b.
Recall-precision graphs, such as that of Fig. 5-2b, have been criticized be­cause a number of parameters are obscured. For example, the size of the re­trieved document set and the collection size are not available from the graph[28]. Furthermore, problems arise when producing a continuous graph from a
discrete set of points. That is, the value of precision is known exactly for a re­call of 0.2 in the example of Fig. 5-2a (1.0), but it is not exactly specified for arecall of 0.4, since the precision varies between 1.0 and 0.67 at that point. Simi­
larly the recall value is specified exactly when the precision is 0.5, but not when
it is 1.0. Another problem arises when a number of curves such as the one ofFig. 5-2b, each valid for a single query, must be processed to obtain average
performance characteristics for many user queries.
Before defining a single composite recall-precision graph reflecting the av­
erage performance of a system for a large number of individual queries, it isconvenient first to replace the sawtooth curves for the individual queries, bysmoother versions that simplify the averaging process. One possibility consists
in using graphs consisting of horizontal line segments such as those shown in
Fig. 5-3 for the example of Fig. 5-2. The curve of Fig. 5-3 is obtained by starting— Interpolated curve— Original curve

1.0

1
0.8

1 ^ 1
0.2

0;

0.2

0.4

0.6
Recall0.8

1.0

Figure 5-3 Interpolated recall-precision
curve fo r sample query of Fig. 5-2. (Ranksof relevant items are 1, 2, 4, 6, 13.)

168

CHAPTER 5

at the highest recall value and drawing a horizontal line leftward from eachpeak point of precision, up to a point where a higher precision point is encoun­
tered. The curve of Fig. 5-3 now exhibits a unique precision value for each re­call point, and it extends along the scale from a recall of 0 to a recall of 1. For
example, at a recall of 0.4 the precision is 1.0 in the graph of Fig. 5-3; however,for any slightly larger value of the recall— say 0.401— the precision has
dropped to 0.75. A similar drop in precision from 0.75 to 0.67 occurs as therecall increases from 0.6 to 0.601. The interpolated curve represents the best
performance a user can achieve [27],Given a set of different performance (recall-precision) curves similar tothat of Fig. 5-3, corresponding to different user queries, average performancevalues can be obtained in several different ways. In particular, if RETREL, isdefined as the number of items retrieved and relevant, RETNRELj is the num­
ber retrieved but not relevant, and NRETREL, is the number relevant but not
retrieved for query i, then following the definitions in (1) and (2), the RECALL,
for query i, and the PRECISION, are defined as

RETRELiRETRELi + NRETREL,RETRELiand PRECISION =RETREL, + RETNREL,
RECALL, =

(3 )
(4 )

A user-oriented recall-level average, reflecting the performance an averageuser can expect to obtain from the system, may then be defined by taking thearithmetic mean, over NUM sample queries, of expressions (3) and (4):
RECALL rl =p r e c i s i o n rl =oRecall

1

NUM
1

NUM

v

i= l
NUM

RETRELiRETRELi + NRETRELi
RETREL,NUM 2i = l RETRELi + RETNRELj

Figure 5-4 Typical average recall-pre­cision graph.

(5)
(6)

169

RETRIEVAL EVALUATION

Since the recall and precision values RECALL; and PRECISION; for the indi­vidual user queries are unambiguously defined as shown in Fig. 5-3, the aver­ages of equations (5) and (6) are also uniquely determined. This makes it possi­
ble to compute average precision values at fixed recall intervals, say for recall
equal to 0, 0.1, 0.2, . . . , 1.0. In particular, for each query the precision
values are computed for the specified 11 values of the recall from 0 to 1.0 insteps 0.1, and equation (6) is used to obtain average precision values overall
queries at each of the 11 recall values. The average curve which results has ashape similar to that shown in Fig. 5-4, where the left-hand end corresponds tonarrow, specific query formulations where few documents are retrieved and theprecision may be expected to be high, while the recall is fairly low. The righthand end of the curve represents broad, rather general query formulations andhence a large number of retrieved documents.
An alternative systems-oriented document-level average is obtained byusing the total number of relevant items retrieved by the system over the NUM
queries, as well as the total number of nonrelevant items that are rejected. Thatis, from the NUM original queries, a single hypothetical combined query isbuilt, whose relevant items are defined as the sum of the relevant of all compo­
nent queries. The document level averages are then defined as
NUM£

RECALL dl =£RETREL;: ■ !
(RETREL; + NRETREL;)

(7)

i= l

NUM

£ RETREL;
and PRECISION^ = ^ ------- *=*--------------------------2) (RETREL; + RETNREL;)

(8)

i= l

The averages of equations (5) and (6) give equal importance to each query,while in formulas (7) and (8) the averages depend more on queries with many
relevant documents than on those with few relevant items. Consider by analogy
a computation of average class size in a university. If there are 10 classes, in­cluding 5 with 1 student each and 5 with 99 students each, the class-level aver­age size is 50[ reflecting the fact that 10 professors teach a total of 500 students,
or 50 on average. The student-level average size, on the other hand, is 98.02,
reflecting the fact that almost all students are in classes with 98 other students.
In information retrieval the choice of averaging method depends on whether it
is more important to display the average user’s result [equations (5) and (6)] or
to reflect what happens to the average relevant document [equations (7) and(8)]. If query performance does not depend on the number of relevant docu­
ments, the two averages give similar results.
Recall-precision curves may be used to evaluate the performance of infor­
mation retrieval systems— typically, by computing recall and precision values
for two or more systems, or for the same system operating under different con-

170

Recall

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

CHAPTER 5

Average precision for 35 queries
Improvement, %Word stem

Thesaurus

0.79630.63500.52830.46030.40510.36990.33830.29960.25680.20180.87880.75670.64640.55770.49120.44700.38930.32870.27260.2093

10.4
19.2
22.4
21.2
21.3
20.8
15.1
9.7
6.2
3.7

(a)

Recall(b)

Figure 5-5 Average recall-precision results for two indexing methods (82 documents, 35
queries), (a) Recall-precision average, (b) Recall-precision graph.

ditions. In these circumstances, the curves produced for systems A and B canbe superimposed on the same graph to determine which system is superior, andby how much. In general, the curve closest to the upper right-hand corner ofthe graph (where recall and precision are maximized) indicates the best per­formance. A typical example is shown in Fig. 5-5, where the performance of
two different indexing systems is shown for a collection of documents in libraryscience averaged over 35 user queries. The “ stem” run refers to an indexing
process where word stems extracted from the document abstracts are used asindex terms to represent document content. In the “thesaurus” run word stems
are replaced by “ concepts” extracted from a thesaurus representing classes ofterms related or synonymous to the original stems. It may be seen from theoutput of Fig. 5-5 that the average precision of the thesaurus run is between 4
and 22 percent better at the fixed recall points than the word stem run.
Since it is difficult to judge the significance of the differences between two
performance curves by citing percentage improvements as in Fig. 5-5, it is help-

RETRIEVAL EVALUATION

171

ful to furnish statistical evidence indicating whether a given difference between
two averages is in fact significant. Most standard statistical significance tests
based on paired comparisons will produce statistical evidence giving the proba­
bility that differences between the two sets of sample values as great as, orgreater than, those observed would occur by chance. When the computed
probability is small enough— for example, less than or equal to 0.05— one con­cludes that the two sets of sample values are significantly different. If, on theother hand, the computed probability is greater than 0.05, the presumption isthat the observed differences could have been obtained by chance— that theoriginal pairs of values might in fact have been derived from the same distribu­
tion.
The pairs of measurements being compared may typically represent the
precision values at some fixed recall level— say, at a recall of 0.1, or at a recallof 0.5— for a set of queries processed by using methods A and B, respectively.
The two middle columns of Fig. 5-5a represent an example of this case. Alter­
natively, the pairs of measurements may represent combined values for several
points representing the complete recall-precision curves. Such combined mea­
surements are obtained from the single-valued evaluation measures introduced
later in this chapter.
The following assumptions are made for three of the best-known signifi­
cance testing procedures [29]. The measurements must be obtained indepen­dently of each other;
1 For the t-test it is assumed in addition that the differences between thetwo sets of sample values to be compared are normally distributed.
2 The sign test makes no normality assumptions, and uses only the sign
(not the magnitude) of the differences in sample values; thus the computed
probability values depend on whether the differences in sample values aremostly positive or negative.
3 The Wilcoxon signed rank test postulates that as differences between
pairs increase, significance also increases, but only as these numbers affect the
ranking; thus, differences of - 1,2, - 3,4, and 20 are equivalent to differences of- 1, 2, - 3 ,4 , and 5, since only the rank of the ordered differences is important.
Since many sets of recall or precision differences are probably not nor­mally distributed, the less stringent assumptions inherent in the use of the sign
test or the Wilcoxon signed rank test may be preferable over those of the better
known t-test. A typical set of output data from a sign test process is shown for
two search methods A and B in Table 5-2. The table is based on 11 statistics(differences in precision at each of 11 recall values from 0 to 1 in steps of 0.1).
For each statistic this table shows the number of queries favoring methods A
and B, respectively, and the one-sided probabilities for the test (ignoring ties).
The one-sided probabilities represent the probabilities that the sample values
could have originated by chance. On the bottom line of Table 5-2 the 11 one­sided tests are combined into a single overall measure. In this case the probabil­ities measure the chance that method B is not significantly different (better)

172

CHAPTER 5

Table 5-2

Sign Test for Typical Search Methods A and B(A ve ra g e fo r 42 Q u e rie s ; T e s tin g fo r C o lle c tio n B B e tte r th a n
fo r C o lle c tio n A)

Favoring method

Precision averageat recall of

A

B

Tied

One-sided
probabilities

0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Combined

1
1
1
1
1
2
3
8
9
8
8
43

7
7
8
13
15
17
20
16
17
18
18
156

34
34
33
28
26
23
19
18
16
16
16
263

0.03850.03850.02260.00180.00060.00070.00040.07670.08510.03870.03870.0000Adapted from reference 29.

than A. This is seen to be zero to four decimal places; that is, method B is sta­tistically better than method A.
A majority of the studies undertaken to evaluate the effectiveness of infor­
mation retrieval systems have used recall and precision measurements to show
system performance. Misgivings have been voiced about some of the charac­
teristics of these measures. As a result a variety of alternative methodologies
have been proposed. A few developments in this area are examined in the next
section.
3

MEASURES OF RETRIEVAL EFFECTIVENESSA

Measurement Problems

The recall and precision measures introduced earlier are advantageous to theuser because they reflect the relative success of the system in meeting various
kinds of user needs. Furthermore a particular measurement can be directly in­terpreted in terms of user experiences. Thus, a precision performance of 0.2 atrecall equal to 0.5 implies that the user has obtained one-half of the relevant
items in the collection, and that four nonrelevant items have had to be exam­
ined for every relevant item that was obtained.
Some qualifying remarks are nevertheless in order in connection with thestandard recall and precision measurements. First, it is clear from the basic def­
initions that recall and precision measurements are normally tied to a given col­lection of documents and to a given query set. Within such a fixed environ­ment, it is possible to vary the indexing policy or the indexing language or the
search methodology and to determine subsequently how these changes may af­
fect the performance of the system in terms of recall and precision. On theother hand, recall and precision must be used with caution in comparing the

RETRIEVAL EVALUATION

173

performance of two entirely different systems based on different document col­lections, different query sets, and different user populations [30,31].
Consider in particular the changes to be expected in the value of the recall
and precision measures when the collection size increases or when the average
number of relevant items per query diminishes from one collection to another.
In both cases recall and precision can be expected to deteriorate because thenumber of relevant and retrieved items is not likely to increase in proportion to
the size of the collection. Care must then be taken to equate collection andquery relevance properties before applying recall and precision measures to theevaluation of different collections.
Another problem arises in connection with the relevance assessments of
documents with respect to user queries. Such assessments are needed if therelevant items are to be distinguished from the nonrelevant ones. Some observ­
ers maintain that recall and precision measurements apply only to the user en­
vironment within which the relevance judgments were first obtained. This isbecause of the inherent subjectivity of relevance assessments [32]. Fortu­
nately, there exists a good deal of experimental evidence to show that for manyof the documents that appear to be most similar to a particular query, andhence are normally retrievable by the search process, very close agreement
may be expected from different assessors as to the relevance in each case. Thisaccounts for the fact that while the relevance assessments obtainable from dif­fering evaluators are different for randomly chosen documents, the effect on
the resulting recall and precision measurements is relatively small [33], Fur­thermore, it is possible to replace the individual opinions about the usefulnessof a given document with respect to a given query by global judgments repre­
senting a consensus of ideas by several independent judges [34,35].
A third question of interest in using recall and precision measurements isthe effect of the query type on the evaluation outcome. In this respect one candistinguish the short subject-heading queries in which the topic is expressed asa single short descriptive word string (e.g., “thermal control,” “turbulence
studies” ) from title-length queries, where a single sentence or title adequately
describes the subject area, and from full-text queries where a complete para­graph is used to formulate a search request [34]. Different query types may be
produced notably in systems where the final query formulations are delegatedby the users to trained search intermediaries. Although the short, subject-head­ing queries will often deal with general topics, whereas the larger full-text
queries are sometimes more specific, it is not always true that query length isdirectly correlated with query specificity. In any case, a system should betested using a realistic query mix reflecting the query types actually submitted
in operational situations.
A last consideration relating to recall and precision computations is the as­signment of relevance grades to the documents of a given collection, and the
choice of a document rank for output purposes. Under normal circumstances,
two relevance assessments are customary: either a document is relevant or it isnonrelevant. In these circumstances, the computation of recall and precision isunambiguous using expressions (1) and (2). If a system uses grades of relevance174

CHAPTER 5

and the retrieved documents are ranked, several documents may be equallysimilar to a given query and placed in consecutive location on the output list.
However, since the order affects the precision-recall evaluation, techniques are
required to compensate for the arbitrary ordering of the equally similar items.
One technique is to assign to all these documents a relevance grade equal to theaverage grade of this set of documents.
In practice, it appears to be a great deal more difficult for the relevanceassessors to use many relevance grades than to simply decide between the rele­vant or partly relevant documents on the one hand and the nonrelevant docu­
ments on the other. Furthermore, errors and uncertainties crop up withmultiple-category relevance assessments where users are forced to make nar­row distinctions between documents that are absolutely relevant, possibly rele­vant, marginally relevant, or nonrelevant as the case may be. These in fact may
outweigh the greater accuracy sought by using the many relevance grades.
Nevertheless, various evaluation procedures and parameters have been pro­
posed for use with variable relevance weights and for systems allowing ties in
the ranks of the retrieved items. These measures are introduced with additional
evaluation criteria in the next section.
*B

Recall, Precision, and Fallout

It was pointed out earlier that recall and precision measurements are directlyinterpretable by users in terms of search satisfaction. On the other hand, they
are sometimes difficult to compute. For example, recall may not be defined be­cause no relevant documents exist in a collection with respect to some query[28,36]. Similarly, precision is undefined when no items are retrieved (the re­spective measures are computed as 0/0 in each case, which is undefined).
Another deficiency in the use of precision and recall is a lack of parallelism
in the properties of the two measures. Assuming that retrieval effectiveness in­creases with the number of relevant items obtained in answer to a query, anddecreases with the number of nonrelevant items retrieved, a measure appears
to be needed which reflects the performance for the nonrelevant documents inthe same way as recall measures the performance of the relevant. This mea­sure, known as fallout, is formally defined using the terminology of Table 5-3 as
FALLOUT =RETNRELRE TN R EL+ NRETNREL
number of nonrelevant items retrieved
total number of nonrelevant in collection(9)

If the recall is expressed in probabilistic terms as the probability of a document
being retrieved given that it is relevant, the fallout is the probability of an item
being retrieved given that it is nonrelevant. An effective retrieval system will
therefore exhibit maximum recall and minimum fallout.
In a normal retrieval environment, recall, precision, and fallout are not in­dependent of the generality factor, defined as the average number of relevant

RETRIEVAL EVALUATION

Table 5-3

175

Contingency Table
Relevant

Retrieved
Not retrieved

Nonrelevant

RETRELNRETRELRETNRELNRETNRELRETREL + RETNRELNRETREL + NRETNRELRETREL+ NRETRELRETNREL+ NRETNRELRETREL + RETNREL +NRETREL + NRETNREL

items per query included in the collection. Referring to Tables 5-3 and 5-4, one
sees that any three of the measures R, P, F, and G automatically determine thefourth. As an example, precision may be determined in terms of recall, fallout,and generality as(R • G) + F(1 - G)v 'However, because the total number of nonrelevant items (RETNREL +NRETNREL) is much larger in practice than the number of relevant(RETREL + NRETREL), any changes in the generality of a collection arelikely to affect the fallout less than the precision. In particular, as the generality
decreases either because the number of relevant items decreases or because thetotal collection size increases, the number of relevant retrieved (RETREL) is
likely to decrease, but the total number of items retrieved (RETREL +RETNREL) as well as the number of nonrelevant items (RETNREL +NRETNREL) may remain fairly constant. Hence precision will be subject tolarger variations than fallout [31]. Furthermore, fallout is unequivocally defined
to be zero when no items are retrieved (RETREL + RETNREL = 0), because
the number of nonrelevant items in the collection (RETNREL + NRETNREL)
may safely be assumed to be nonzero.
These arguments have been used to suggest the replacement of the recall
and precision measures by recall-fallout computations. A typical recall-fallout
display is shown in Fig. 5-6 for the query previously used as an example in Figs.
Table 5-4
SymbolTypical Retrieval Evaluation M easures
Evaluation
measureR

RecallP

Precision

F

Fallout

G

Generality

FormulaExplanation

RETRELRETREL + NRETRELRETRELRETREL + RETNRELRETNRELRETNREL + NRETNRELRETREL + NRETRELRETREL + RETNREL +NRETREL + NRETNREL

Proportion of relevant
actually retrieved
Proportion of retrieved
actually relevant
Proportion of nonrelevant
actually retrieved
Proportion of relevant
per query

176

CHAPTER 5

Relevant

RecallFallout

1

X

2
3
4
5
6
7
8
9
10
11
12
13
14
20
50
100
200

X

0.2
0.4
0.4
0.6
0.6
0.8
0.8
0.8
0.8
0.8
0.8
0.8
1.0
1.0
1.0
1.0
1.0
1.0

0
0
0.005
0.005
0.010
0.010
0.015
0.020
0.025
0.030
0.035
0.040
0.040
0.045
0.075
0.225
0.475
0.975

n

X
X

X

(a)

=

1.0 ■
0.8 ■

S 0.6tr 0.4 ■

0.2
_ i_

0.001

0.01
Fallout
(b)

0.10

0.975

Figure 5-6 Display of recall and fallout
results for sample query of Fig. 5-2. (Col­lection consists of 200 documents inaerodynamics.) (a) Recall-fallout after re­trieval of n documents, (b) Recall-fallout
plot.

5-2 and 5-3. The graph of Fig. 5-6 indicates that the fallout is not as easily inter­
preted by the user as precision. In fact, the two types of effectiveness pairs(recall-precision and recall-fallout, respectively) may well respond to different
needs in actual retrieval situations. Since the recall provides an indication of
the proportion of relevant actually obtained as a result of a search, while pre­cision is a measure of the efficiency with which these relevant are retrieved, arecall-precision output is user-oriented, because the user is normally iriterested
in optimizing the retrieval of relevant items. On the other hand, fallout is a mea­
sure of the efficiency of rejecting the nonrelevant in the collection (which inmany cases is approximately equivalent to the collection size). For this reason,a recall-fallout display may be considered to be systems-oriented, since it indi­cates how well the nonrelevant are rejected as a function of collection size [37].
The foregoing measures are all based on objective relevance judgmentsthat are independent of the user’s prior knowledge of the subject area. Addi­
tional measures which depend on the subjective relevance are [27]:
1 The novelty ratio, that is, the proportion of items retrieved and judged
relevant by users of which they had not been aware prior to receiving thesearch output

RETRIEVAL EVALUATION

177

2 The coverage ratio, that is, the proportion of relevant items retrieved
out of the total relevant known to users prior to the search
3 The sought recall, defined as the total relevant examined by users fol­lowing a search, divided by the total relevant which users would have liked to
examineMany other evaluation measures based on the contingency table display of
Table 5-3 have been proposed over the years [19,28,38,39]. Some of these mea­sures use the full information incorporated in the contingency table, as opposed
to recall, precision, and fallout that are based on a single column or a single rowof the table only. However, most of these measures are not easily interpretable,
and it is not likely in these circumstances that they will quickly supplant recall
and precision.
"j/^ ^ iin g le -V a lu e d Measures

Some observers completely reject the contingency table as a basis for the con­struction of parameters capable of reflecting retrieval effectiveness. Instead a
number of desirable properties are postulated for an ideal effectiveness mea­sure, including in particular the following [40]:1 The measure should be able to reflect retrieval effectiveness alone, sep­arately of the criteria such as cost.
2 The measure should be independent of any particular retrieval cutoff,that is, of the number of documents retrieved in a particular search.
3 The measure should be expressible as a single number (instead of twovalues such as recall and precision) which can be put on a scale to give absoluteand relative values.
The best known of these single-valued measures is the E measure introduced
by Swets [40-43].
To construct the E measure, two distinguishable populations of objects
POP, and POP2 are associated with the relevant and the nonrelevant documentswith respect to some query. If a parameter r is used to represent some measur­
able characteristic such as the query-document similarity for each document,
the “probability density functions” FUNC,(r) and FUNC2(r) with means
MEAN, and MEAN2 and variances VAR, and VAR2 will then indicate how theparameter r behaves for the two populations. That is, FUNC,(r) represents theprobability that a document in POP, has value r, and FUNC2(r) applies simi­
larly to POP2. A typical graph of these probability density functions is shown in
Fig. 5-7.
By choosing a particular value of r— for example, the point r = C— it be­comes possible to compute the fraction of each population for which r has avalue greater than or equal to C. This is the portion of the area under the proba­
bility density curve lying to the right of line r = C. C is in fact a cutoff value
such that any item for which FUNC(r) > C is retrieved. Since FUNC,(r) and
FUNC2(r) are associated with the relevant and nonrelevant document popula-

178

CHAPTER 5r

Figure 5-7 Probability density functions
for populations POPj and POP2 compris­
ing the relevant and nonrelevant documents, respectively. (Adapted from refer­ence 41.)

tions, respectively, the areas under the density curves to the right of r = C rep­resent, respectively, the proportion of relevant and of nonrelevant documents
for which FUNC(r) > C. The first measure is equal to the recall, while the sec­
ond is equal to the fallout. By plotting the percentages of the populations POP!
and POP2 to the right of the cut C against each other, while varying C, one ob­tains an operating characteristic (OC) curve similar to that shown in Fig. 5-8. If
populations POPj and POP2 are identical with respect to the characteristic r,
the operating characteristic is a line running diagonally across the graph. The
more different the two populations are from one another the more closely the
OC curve will approach the upper left-hand corner of the figure (the 0-100 pointof the graph).
Swets plotted the operating characteristics for a large number of retrieval
systems using normal probability scales for recall and for fallout. In these cir­
cumstances, straight lines are obtained if recall and fallout both show normal
distributions with respect to r. Within the limits of experimental error, the lines
were all found to be straight, leading to the conclusion that the probability den­sity functions of recall and fallout with respect to parameter r are normal. It
follows that recall-fallout performance can be represented by specifying the po-

Figure 5-8

Operating characteristic curve. (Adapted from reference 41.)

RETRIEVAL EVALUATION

179

sition of the corresponding straight line. Two typical operating characteristiclines are shown in Fig. 5-9, labeled A and B respectively. Swets’ E measure isdefined specifically as
E = \ f l • DIST

(11)

where DIST is the distance from 0 (see Fig. 5-9) to the operating characteristic
curve along the line from point 0 to point R. If the angle of the operating charac­
teristic curve is the same as the diagonal, as it is for line A of Fig. 5-9, that is,
the slope of the curve is equal to 1, then the value of E does represent the per­formance effectiveness. If the angle of the operating characteristic curve, is not
the same as the diagonal as in line B, then it is necessary to present the slopeof the operating characteristic curve as well as the E value.
The main advantage of the (E, SLOPE) measures is that they are derived
using a well-known and accepted statistical theory. The disadvantage is that
unlike recall and precision, the E and SLOPE measures cannot be translated
into a performance characterization as readily by the user population. In prac­
tice it is found that values of SLOPE range from 0.5 to 2.0, so that the twovalues (E, SLOPE) are necessary to express the performance, just as is thecase for recall and precision. It should be noted also that the determination of
the E measure is based on information equivalent to that contained in a full re­call-precision graph. That is, the E value cannot be obtained by using a single
retrieval threshold that distinguishes the retrieved from the nonretrieved itemsof the kind normally available in conventional retrieval situation; a single pairof recall-precision values is, however, computable in that situation.

Probability o f r given nonrelevant documents

Figure 5-9 Operating characteristics on normal probability scales. (Adapted from refer­ence 40.)

180

CHAPTER 5

Various additional global measures based on established theories— espe­
cially probability theory and information theory— have been described in theliterature but have not received consideration in practice [44-49]. These mea­sures generally combine aspects of precision and recall in a single expression.
One function, based on considerations of measurement theory, uses a special
parameter (a) which makes it possible to attach degrees of importance to therecall and precision components [25]:E = 1-1a(l/PRECISION) + (1 - a)(l/RECALL)( 12)

Large values of the recall and precision measure correspond to small values ofthe evaluation measure E. For example, assume an a value of 0.50 and recall
and precision values equal to 0.50. These parameters produce an E value of0.50. When the recall remains at 0.50 but precision drops to 0.25, the E value
increases to 0.67. On the other hand, if recall remains at 0.50 and precision in­creases to 0.90, the E value is 0.36.
One composite evaluation measure is independent of the retrieval thresh­
old used to distinguish the retrieved from the nonretrieved items and is applica­
ble to systems that rank the retrieved documents. It is based on considerations
similar to those used by Swets, in that the area is computed under a particularform of the recall and precision graph [50,51]. Consider a graph in which therecall of a system is represented along the ordinate and the rank orders of theretrieved documents are plotted along the abscissa. The graph starts at zeroand maintains a zero value until a rank is reached corresponding to a retrieved
relevant document, at which point the recall jumps to 1/REL (for REL relevant
documents included in the system). The recall then stays at 1/REL until thenext relevant document is reached, at which point the recall increases to
2/REL, and so on, until the last relevant document rank is reached when therecall reaches its final value of REL/REL or 1.
If this recall step function is plotted on the same graph with a similar func­tion for an ideal system for which the REL relevant documents are ranked 1,2,
. . . ,REL, the area between the two step functions can be used as a measureof the recall performance of the system. A typical case is shown in Fig. 5-10 for
the query used as an example in Figs. 5-2, 5-3, and 5-6. The ranks of the rele­vant documents in decreasing similarity order are assumed to be 1, 2, 3, 4, 6,
and 13. The difference in area between the ideal retrieval situation and the ac­tual recall curves designated by the tinted area in the example in Fig. 5-10 isgiven by
REL

2

REL

RANK, - 2 i
REL

(13)

181

RETRIEVAL EVALUATION

Ideal ranks 11,2,3,4,5)

1

5

10

15

Ranks o f
retrieved documents

Figure 5-10 Construction of normalized recall measure.

where REL is the number of relevant documents and RANKj represents the
document ranks of the relevant items.
The values for expression (13) range from 0 for the case of perfect retrieval
to N - REL for the worst possible case. That is, if the REL relevant documents
are ranked 1, 2, 3, . . . , REL, then the value of expression (13) is equal to 0.
On the other hand, if the relevant document ranks are N - REL + 1, N REL + 2, . . . , N where N is the number of documents in the collection,then the value of expression (13) is equal to N - REL. Hence expression (13)can be normalized by dividing by N - REL. Finally, subtraction from 1 ensuresthat the measure equals 1 for the best case and 0 for the worst instead of viceversa. The resulting measure, known as the normalized recall, is then given by
REL£
RECALLnorm — 1 —

RANKi

i= l

S i
i= l

(14)

REL(N - REL)

For the case shown in Fig. 5-10, RECALLnorm equals 0.989. This reflects thefact that the ranks of the relevant documents deviate very little from the ideal
case.
The tinted area in Fig. 5-10 reflects the number of nonrelevant doc­
uments that have to be retrieved in order to reach a recall value of 1. Since thelatter measure is akin to the fallout, the normalized recall value of expression(14) may in fact be shown to be equivalent to the area under the recall-fallout
curve of Fig. 5-6b [42],An equivalent development for the computation of the normalized area be­
tween actual and ideal precision curves leads to a normalized precision mea­
sure defined as
REL

REL

2
PRECISIONnorm = 1 -log RANKi

S

^

i= l

log N!/(N - REL) !REL!

(15)

182

CHAPTER 5

Just like ordinary recall and precision, the normalized recall is sensitive tothe rank assigned to the last relevant document in the retrieval order, and thenormalized precision is sensitive to the rank of the first relevant document in
the retrieval order. The normalized measures constitute a summary of the fullrecall-precision curve; as such they cannot be computed for a single retrieval
point corresponding to a single recall-precision pair.
A number of additional single-valued measures also use the differences be­
tween the actual ranks of the relevant items retrieved, and either the ideal ranks
where all the relevant items are retrieved ahead of any nonrelevant item, or arandom system where the relevant items are randomly sprinkled among thenonrelevant. The expected search length [52] and the sliding ratio [53] are two
measures of this kind.
Consider first the expected search length. Here one assumes that docu­
ments are presented to the user in a weakly ordered sequence following an in­formation search— for example, all documents exhibiting NMATCH matchingterms with the query would be retrieved before the set with NMATCH - 1
matching terms, and those in turn would precede the set with NMATCH - 2
matching terms, and so on. The search length may then be defined as the aver­
age number of nonrelevant items that must be scanned by the user before thetotal number of wanted items is reached.
Consider as an example the case of Fig. 5-11 which includes 3 items in set 1

Set 1
3 items|
I
I_____ I

Set 2
5 items

Kset3

5 items

V /v Ai.

I
I|_____|i m|_____ |

V//A

p a n
relevant(a)Number o f
relevant
wantedNumber o f
sets to be
searched

SearchlengthAverage search length110, 1, or 2

1/3-0 + 1/3-1 + 1/3-2 = 1

6

3

3, 4, 5, or 6

4 /1 0-3 + 3/1 0-4 + 2/10-5+ 1/10-6 = 4(b)Figure 5-11 Average search length illustration, (a) Partly ordered retrieval output, (b) Average
search length computation. (Adapted from reference 52.)

183

RETRIEVAL EVALUATION

and 5 items in each of sets 2 and 3. Set 1 is retrieved before set 2 and set 2 isretrieved before set 3. Within each of the sets the documents are not ranked orordered. That is, there is no obvious way to order the documents having
NMATCH terms in common with the query. The average search length neces­sary to retrieve 6 relevant items is 4. That is, the searcher will have to examine
4 nonrelevant documents on the average in order to find 6 relevant ones. In
particular, since only one relevant item is retrievable from set 1, and 4 morefrom set 2, it is always necessary to look into set 3 for one additional relevant
item to make up the total of 6. The first relevant item in set 3 may be located inposition 1, producing a total search length of 3; or in positions 2, 3, or 4, pro­ducing search lengths of 4, 5, or 6, respectively. Of the 10 possible ways of dis­tributing two relevant items among 5 positions in set 3, 4 have a relevant item inposition 1, 3 more in position 2, 2 more in position 3, and 1 in position 4. This
results in the search length computation shown in Fig. 5-11.
Now consider a QUERY and let PREVNREL be the number of nonrele­vant documents in all sets preceding the one where the search terminates. If
there are REL relevant items in the final set, and if they are put at equal inter­vals among the NREL nonrelevant documents in that set, then REL + 1 subse­
quences of nonrelevant documents will normally be created containing
NREL/REL + 1 nonrelevant documents each. If one assumes that the request
is satisfied at the NUMth relevant item on the last level, the expected searchlength EXP for QUERY will be
NREL • NUM
EXP(QUERY) = PREVNREL + —L ~+ 1—(16)

The expected random search length is obtained by scattering the ALLREL
documents relevant to QUERY randomly through the IRREL irrelevant items.
It is defined as DESIRED • IRREL/(ALLREL + 1), where DESIRED is thetotal desired number of relevant. A useful measure is specified as the improve­
ment obtained by the actual case EXP over the random case REXP [51] asfollows:
REXP(QUERY) - EXP(QUERY)REXP(QUERY)NREL NUM
PREVNREL +REL + 1
= 1DESIRED • IRREL
ALLREL + 1

EXP(QUERY) REDUCTION =(17)

The sliding ratio measure is based on the comparison of two ranked lists ofitems. One list is the output of an actual retrieval system, and the other repre­
sents an ideal system in which the items are ranked in decreasing relevanceorder [53]. This model is more complex than the ones previously described be­cause it allows the assignment of numeric relevance weights to the documents.

184

CHAPTER 5

Table 5-5

Sample Computation for Sliding Ratio Measure
Retrieval rank

1

2

3

4

5

Document number
Relevance weight W E IG H T S

3
10

4
0

5
8

1
5

2
2

10

10

18

23

25

3
10

5
8

1
5

2
2

4
0

10

18

23

25

25

1

0.55

0.78

0.92

1

•

NUM

SWEIGHT REAL(NUM) = £ W EIGHT**1

Actualsystemoutputi=1Document number
Relevance weight WE!GHT|DEAL
NUM

SWEIGHT IDEAL(NUM) = ]T WEIGHTjDEAL

Ideal
systemoutputi= 1

SWEIGHT REAL(NUM)
IDEAL; NUM;s l id e (n u m ) = SWEIGHT

Adapted from reference 53.

These replace the usual binary relevance assessments. In an ideal retrieval situ­
ation, the documents would be ranked in decreasing order of their relevanceweights rather than by a simple precedence of the relevant set ahead of the setof nonrelevant items. Ties in rank and in relevance values between items can beeliminated, for example by assigning to all items in each set the average rank of
the items in the set.
The sliding ratio measure SLIDE(NUM) for retrieval cutoff SLIDE may
be defined as
SLIDE(NUM) =SWEIGHT REAL(NUM)
SWEIGHT IDEAL(NUM)(18)

where SWEIGHT REAL(NUM) and SWEIGHT IDEAL(NUM) are the sum of
the relevance weights of all items retrieved up to rank NUM in the actual andideal systems, respectively. A sample calculation is shown in Table 5-5 for five
documents which do not exhibit any ties in rank. The value of SLIDE(NUM) at
any particular value of NUM shows the ability of the actual system to approxi­
mate the retrieval capability of the ideal system. In the limit, as NUM ap­
proaches the total number of documents in the collection, WEIGHTREAL(NUM) becomes equal to WEIGHT IDEAL(NUM) and SLIDE(NUM)
becomes equal to 1.
The sliding ratio can of course also be used for systems where the rele­vance weights are restricted to 1 for relevant items and 0 for the nonrelevant. In
that case, the ratio approximates the normalized recall and the expected searchlength.
**D

Utility Measure

A property shared by all the measures described in the preceding sections is thefact that only system effectiveness is taken into account. The cost or value of aparticular retrieval action has not been considered. Assuming that cost and/or

185

RETRIEVAL EVALUATION

value parameters are available, it is possible to devise retrieval evaluation strat­egies based on an extension of the standard contingency table as shown in
Table 5-6 [54,55]. The data in Table 5-6 show the usual four-way split of the
document collection into the number of items relevant and retrieved RETREL,
the number of items retrieved and nonrelevant RETNREL, the number of
items not retrieved but relevant NRETREL and the number of items not re­trieved and not relevant NRETNREL. A value of VALUE! is assigned to eachrelevant item that is retrieved, and VALUE, is assigned to each nonrelevant
item that is rejected. Similarly, costs of COST, and COST, are associated withnonrelevant items retrieved and with relevant items that are missed.
If the value of the similarity measure between a document DOC and aquery QUERY can be expressed as a variable VAR = FUNC(QUERY,DOC),
then the utility of a given relevant document set DOCSET with respect to somequery QUERY at retrieval threshold VAR = THRESHOLD can be expressedas

UTIL(DOCSET,QUERY, THRESHOLD) = VALUE! • RETREL- COSTi • RETNREL - COST, • NRETREL+ VALUE, • NRETNREL(19)

Or alternatively as
UTIL(DOCSET,QUERY,THRESHOLD) =VALUEi • N Prob{DOC is relevant and VAR 5= THRESHOLD}- COSTi • N Prob{DOC is not relevant and VAR s= THRESHOLD}- COST, • N Prob{DOC is relevant and VAR < THRESHOLD}+ VALUE, • N Prob{DOC is not relevant and VAR < THRESHOLD}(20)

where N is the total number of documents in the system. Expression (20) canbe transformed using the probability density functions FUNCj(VAR) and
FUNC,(VAR) previously introduced in Fig. 5-7. In fact, the area under thedensity curves to the right of a given threshold represent the probabilities thatvariable VAR has a value greater than the threshold, given that the documents
are relevant and nonrelevant, respectively. By substitution of integrals into ex­pression (20) a useful retrieval threshold is obtained for which the utility of thesystem is positive.
Table 5-6

Retrieved
Not retrieved

Contingency Table with Cost and Value Parameters
Relevant

Nonrelevantv, (RETREL)
C2 (NRETREL)

c, (RETNREL)
v2 (NRETNREL)RETREL + RETNRELNRETREL + NRETNRELRETNREL + NRETNRELNRETREL + NRETRELv, = V A L U E ,; v, = VALUE,c, = C O S T ,; c , = COST,

CHAPTER 5

186

A substantial literature exists relating to the use of the utility measure for re­trieval system evaluation [54-57]. However, until simple methods become
available for estimating the cost and value parameters for the individual docu­
ments in a collection, the theoretical appeal of this method may outweigh its
practical usefulness.
4

EVALUATION OF SYSTEM COST AND EFFICIENCY

A

System Tradeoffs

The art of efficiency analysis is not as far advanced as the analysis of systemeffectiveness. This is because accurate cost data in terms of time, effort, andmoney spent are difficult to obtain, and because the value of improved informa­tion services and the benefits derivable from them is impossible to ascertain inmost environments. Furthermore, when identifying information system costs,
invariably one is forced to look at noncomparable situations. The cost differ­ences between two systems, such as an automated and a manual one, may notaccurately reflect the value of either system. The automated system might, forexample, be used for purposes other than information storage and retrieval, or
it might be usable on a 24-hour per day basis, whereas a manual system mightnot. Thus an efficiency evaluation involves a great many intangible factors
which may hamper a concrete analysis and render the results unreliable ormeaningless.
Nevertheless, it is necessary to consider the cost analysis question. Infor­
mation systems are not likely to be constructed or installed without some at­
tempt at evaluating their potential efficiency. It is customary to distinguish be­
tween cost-effectiveness analysis and cost-benefit analysis. The former isdesigned to find the least expensive means for carrying out a given set of opera­
tions or to obtain the maximum value from a given expenditure. Cost-benefit
analysis requires a systematic comparison between the costs of individual oper­
ations and the benefits derivable from them [58-60].
The costs of a system can be divided into the initial development costs
necessary for design, testing, and evaluation; the operating costs which arevariable and depend on the tasks performed, the personnel used, and theamount of equipment required; and finally, the fixed costs for rent, taxes, andother standard items. The benefits obtainable from the information system may
be related to decreased costs or increased productivity. Costlsavings are diffi­
cult to document when manual operations are replaced by automatic ones. It iseven harder to measure the benefits of sophisticated information systems which
may consist of improved decision making capabilities, increased productivity,
stimulation of research capacity, and the like, and the value of these somewhat
serendipitous factors is normally impossible to ascertain.
In an information retrieval situation in which the volume of operations—such as number of documents, size and cost of the documents, and average
number of queries— is given, the basic alternatives and system tradeoffs relate
to the input and document indexing operations on the one hand, and to the in-

RETRIEVAL EVALUATION

187

formation search and output transactions on the other. A particular perform­
ance criterion— for example, a given precision level— can normally be attainedin many different ways, each of them involving different cost levels. Thus, pre­cision may be raised by using a highly specific indexing vocabulary requiringhigh indexer proficiency and large indexing costs. Alternatively, the indexing
may be performed more casually, but the output might be screened by trained
subject experts before presentation to the users, thereby decreasing indexing
costs but lengthening search time. Finally, the burden might be shifted to theuser, by having customers conduct an interactive search and letting themrephrase the query formulation in the hope of generating better output.
In some cases, it is possible to obtain quantifiable information which re­lates various system alternatives to the effectiveness or quality of the output
product. The following relationships may be cited as examples [7,58,59]:
1 Collection coverage versus expected number of retrievals; normally, avery small proportion of items accounts for a large proportion of all relevant
items retrieved; the cost of adding to the collection a large number of the lessproductive items may thus be difficult to justify in terms of improvements in the
output product.
2 Indexing time versus search effectiveness; there is a direct relation be­
tween indexing time and indexing exhaustivity and the corresponding expected
recall; unfortunately, at high recall, the required indexing time increases much
more rapidly than the recall performance, so that diminishing returns set inwhen the indexing time or exhaustivity exceed a given limit.
3 Specificity of the indexing language and recall-precision balance; nor­mally, a more specific indexing language costs more to develop and produces
better precision but may cause losses in recall; obviously, the desirable level ofprecision and thus the importance of language specificity varies with collection
size, high precision being most crucial for very large collections.
4 Equipment complexity versus processing limitations; in general, moresophisticated equipment can produce a greater variety of output products— forexample, ranked output consisting of document abstracts, instead of unranked
document numbers or titles; on the other hand, more sophisticated processing
devices cost more to acquire and to operate and put a greater burden on thesystem operators, and sometimes on the users.
Even if the various system alternatives are quantifiable in a reliable way, it
may be difficult to reach operational decisions because the large fixed costs as­sociated with an implementation may not be easily recoverable by instituting
fees for service provided. Until agreement is reached concerning the value andbenefits of information services, a cost analysis is not likely to produce the an­swers by management.
**B

Cost Analysis

There exist two basically distinct approaches to the analysis of the costs of an
information system. The first one consists in carefully analyzing the various
steps included in an actual processing chain, and in performing direct measure-

188

CHAPTER 5

ments of the various quantities which enter into the cost picture for a given op­
eration environment. The second consists in generating an abstract model ofthe system being investigated, and in ascertaining system efficiency by carryingout appropriate simulation studies. In either case, all actual as well as hidden
costs ought to be taken into account, including development costs, operating
costs, and fixed costs.
Consider first the approach which starts with actual system measurements.
As might be expected, volumes of published cost figures may be found in theliterature presenting a wide array of measure data [61-64]. In general, the pub­lished data are unrelatable to each other, because of differences in the respec­tive environments and in the assumptions made when performing the measure­ments. However, the published values do make it possible to obtain an idea ofthe relative expense arising from various processing steps, and occasionally theabsolute magnitude of some item— for example, a stated manual cataloging
cost of over $10 per item obtained for five large university libraries in 1969—
may in itself furnish cause for concern. A unit cost figure is, however, not as
useful as an indicator of system efficiency as a calculated cost related to someeffectiveness measurement, such as, for example, the cost per citation re­trieved by the system or, better still, the cost per relevant citation retrieved[65,66],
A typical efficiency analysis based on initial measurements of costs, time,and volume of operations would start with a formal system description, includ­ing a specification of the interrelationships between processes, and the genera­tion of basic parameter values relating file sizes, input and output rates, andother operating characteristics. Several functional models of this type exist forlibraries and information centers, normally including information acquisition,
data encoding or indexing, storage organization, query preparation, informa­tion search, output operations, and in some instances also user appraisal andfeedback operations leading to query reformulations [67,68].
The statement of time and cost data for equipment, personnel, materials,
and procedures, and a specification of the interdependencies between various
system parameters then lead to the generation of performance measurements
which relate system performance to user requirements. The user requirements
may be specified in terms of output volume, response time, recall and precision
requirements, and the like. If a computer program is used for the computationof the functions, it may be possible to perform measurements for various as­
sumed levels of the parameter values—for example, using different input rates
for new materials, and different monthly search volumes. This leads to thegeneration of different figures of merit for different assumed operating
conditions, and to decisions concerning a possible expansion of services or totransformations in the current operating practices.
The cost-time-volume model is valuable in situations where exact system
specifications and parameter values are available. In practice these values areusually not available, and when they are, a computation of performance mea­
surements closely tied to current operating characteristics is usually notneeded, since the system operations may already be well in hand. In such

189

RETRIEVAL EVALUATION

cases, a more ambitious system simulation might be undertaken leading to atheoretical analysis of new concepts and ideas, including system growth stud­ies, error and reliability studies, and comparative evaluations of new system
configurations [69,70],
Consider now the specification of actual cost functions. A variety of for­mulations have been used for this purpose, including some based on cost-bene­
fit comparisons and on the dual use of both efficiency as well as effectivenesscriteria [71-74], One possibility consists, for example, in assuming that costs
may be subdivided into four types, including initial costs for development,
operating costs for personnel and materials, fixed costs such as rent and taxes,
and finally operating returns derived from the sale of products [75], If the re­turns are disregarded, development costs are broken down into designing, test­
ing, operating, and reporting, and operating costs are separated into three parts,
including clerical, machine, and technical and professional costs, the resulting
cost function may be expressed as
COST = C(TIME,UNITS)
FIXED

= ^

FIXi(TIME) + DVLP(TIME) + OPER(TIME,UNITS)

(21)

i= l

where

TIME = unit time
UNITS = the number of unit operations to be considered
FlXj = ith subdivision of the fixed costs in dollars per unit of time
FIXED = number of subdivisions of fixed cost
DVLP = development cost in dollars per unit time, amortized as
current cost
OPER = operating cost in dollars per unit time per unit operation
C(TIME,UNITS) = general cost function varying with time and number of op­
erations
The various factors of equation (21) can be further broken down into indi­vidual components. Thus, the operating costs can be expressed as" CLERICAL

OPER(TIME,UNITS) = UNITS

2
L

CLERjCTIMEJTIMclrkj

j= l

MACH

+ ±

MCHk(TIME)TIMMAC,k

k=l
TECH

+ 2 TCHq(TIME)TIMTNCH,q
Q=1
where

( 22)

CLERj = jth subdivision of the clerical costs indollars per unit, and time per unit op­
eration (for example, the salary rate of
the typists in a certain category)
CLERICAL = number of subdivisions of clerical cost

190

CHAPTER 5

MCHk= kth subdivision of machine costs
MACH = number of subdivisions of machine
costs
TCH„ = qth subdivision of technical cost
TECH = number of subdivisions of technicalcost
TIMclrkj, TIMMAC,kJ and TIMtnch,q = increments of time used for clerical,
machine, and technical operations, re­spectively
Relationships may also be used between some of the cost components inorder to obtain optimum allocations for some of the subunits. Thus the operat­
ing cost of individual operations often decreases as the response time is allowed
to increase; at the same time the user’s “delay cost” increases with time. An
optimal response time must then exist, where the operating costs are no longer
maximal (as they would be if instantaneous responses were demanded), while
the output delay cost is still reasonable [76].
Analogously, search cost could be compared with collection size, where
the cost first decreases with increasing file size to some optimal value as the
proportion of items that can be stored in internal machine memory increases.
Then as the file size increases further, all added items are stored in external,
slow access memory, thereby increasing access and search costs. A typicalcost curve of this type derivable by appropriate efficiency evaluation methods
is shown in Fig. 5-12 [77].
A final cost model to be mentioned is based on a comparison between costs
and benefits [78]. Two parameters are defined first, known, respectively, as thebenefit to cost ratio BENEFIT/COST, and the PROFIT, equal to BENEFIT COST. One assumes that the cost COST varies with respect to three parame­
ters: the number of documents NDOCF in the file, the number of SEARCHES
conducted per year, and the number of documents DOCPERSEARCH retrieved
per search. All other costs are assumed fixed. A typical annual cost function
might then be

Figure 5-12 Typical cost curve reflecting
search cost. (Adapted from reference 77.)

RETRIEVAL EVALUATIONCOST = FIXED + MARGE • NDOCF + (FIXEDSEARCH+ VARYSEARCH • DOCPERSEARCH) • SEARCHES

191

(23)

where

FIXED = fixed costs
MARGE = marginal costs Of storing an additional item
FIXEDSEARCH = fixed search cost
VARYSEARCH = search cost that varies as a function of the number of out­
put items examined
If one postulates that the benefit derived by a user from a search varies as
the fraction of relevant items identified by the search from 0 to 1, then the bene­
fit from a given imperfect search is BENEFIT • VALUE, where VALUE is thefractional user benefit derived from a given search, and BENEFIT is the maxi­
mal obtainable user benefit (in dollars). For NUM searches, the yearly benefit
is then BENEFIT t = BENEFIT • VALUE • NUM. In these circumstances
the annual net benefit PROFITt = BENEFITX - COSTt will be
PROFITt = (BENEFIT • VALUE - FIXEDSEARCH- VARYSEARCH • DOCPERSEARCH)SEARCHES- MARGE • NDOC - FIXED(24)

The simple net benefit model of equation (24) serves only as an approxima­tion to a much more complicated real situation. However when reasonably ac­
curate sample values are used for the various parameters, useful indications
may be obtainable from efficiency and effectiveness evaluations reflecting the
behavior of the system in the real-life environments that are being investigated.

5 SUMMARY

It should be clear that the most dominant form of evaluation remains the pre­cision-recall curve defined early in this chapter. However, it is also obviousthat a great deal of effort has been invested to develop other means of evaluat­
ing information retrieval systems. Some of these are reasonably practical even
if seldom used, such as fallout, and others are theoretically interesting but al­most never used, such as Swets’ E.
Difficulties arise in acquiring much of the data required for evaluation. Pre­cision and recall seem to present relatively few conceptual problems, althoughboth depend on the availability of objective relevance assessments of docu­
ments with respect to queries. Precision and recall are also readily interpretablein terms of the actual performance of the system, and they may be relatable tocost evaluation by using composite measures such as, for example, the cost per
relevant document retrieved.
Since many decisions eventually revolve around system cost, it would be
convenient if one could easily measure either the cost or the benefit of a sys­tem. Unfortunately, costs and values vary from environment to environment,

192

CHAPTER 5

and the expense associated with a particular system function or operation isoften impossible to isolate from the surrounding context. Thus, while somecost evaluation methods have been presented, it must be recognized that thecollection of cost data is very difficult. Furthermore, the comparison of costs
pertaining to different environments is particularly dangerous.
In the remainder of this book, the evaluation results are based on recall
and precision, because these measures remain the standard. In operational re­trieval environments, many other factors may, however, prove more important
than recall and precision, especially to uninitiated users of the system. Whereasa small improvement in either recall or precision may be completely invisible tothe average user, human factor considerations such as ease of use and training
required for query submission, output formats, console noise, system reliabil­ity, and response time may take on overwhelming importance.
The evaluation measures examined in this chapter make it possible to dis­tinguish well-designed methods from other less effective ones. In the end, ac­
ceptable retrieval systems must be easy to use, reliable, effective and inexpen­
sive. All system users look forward to the day when such systems will actually
become available for use.
REFERENCES[1] D .W . K ing and E .C . Bryant, The E valuation o f Information S ervices and Products,
Inform ation R esou rces P ress, W ashington, 1971.
[2] A . K ent, O .E . T aulbee, J. B elzer, and G .D . G oldstein, editors, E lectronic Handlingo f Information: Testing and E valuation, T hom pson B ook C o ., W ashington, 1967.
[3] S. Treu, T esting and E valu ation — Literature R ev iew , in E lectronic H andling o f In ­formation: Testing and E valuation, A . K ent, O .E . T aulbee, J. B elzer, and G .D .
G oldstein, editors, T hom pson B ook C o ., W ashington, 1967, pp. 7 1 -8 8 .
[4] F .W . L ancaster, E valuating the E ffectiven ess o f Inform ation R etrieval S y stem s, inInform ation Retrieval S y ste m s— C haracteristics, T esting and E valuation, 2nd E di­tion, Chapter 9, John W iley and S on s, N e w Y ork, 1979.
[5] C.J. W essel, Criteria for Evaluating Technical Library E ffectiv en ess, A slib Pro­
ceed in gs, V ol. 20, N o . 11, N ovem b er 1968, pp. 4 5 5 -4 8 1 .
[6] H . B ornstein, A Paradigm for a Retrieval E ffectiv en ess Experim ent, American
D ocum entation, V ol. 12, N o . 4, O ctober 1961, pp. 2 5 4 -4 8 1 .
[7] F .W . L ancaster and W .D . C lim enson, Evaluating the E conom ic E fficiency o f a
D ocum ent Retrieval S y stem , Journal o f D ocum entation, V ol. 24, N o . 1, March
1968, pp. 1 6 -4 0
[8] C .P. B ourne, R eview o f the Criteria and T echniques U sed or Suggested for the
E valuation o f R eference R etrieval S y stem s, R eport, Stanford R esearch Institute,
M enlo Park, California, Septem ber 1964.
[9] M .B . Snyder, A .W . Schum acher, S .E . M ayer, and M .D . H avron, M ethodology for
T est and Evaluation o f D ocu m en t Retrieval System s: A Critical R ev iew and R ec­
om m endations, R eport to the N ational S cien ce F oundation, Hum an S cien ces R e­
search In c., M cL ean, Virginia, January 1966.
[10] D .W . K ing and E .C . Bryant, A D iagnostic M odel for Evaluating R etrospective

RETRIEVAL EVALUATION

193

Search S ystem s, Inform ation Storage and R etrieval, V ol. 6, N o . 3, July 1970, pp.
2 6 1 -2 7 2 .
[11] T. Saracevic, Linking R esearch and Teaching, A m erican D ocum entation, V ol. 19,
N o . 4. O ctober 1968, pp. 3 9 8 -4 0 3 .
[12] F .W . L ancaster, The F unctions o f Information Retrieval S y stem s, in Information
R etrieval S y stem s— C haracteristics, Testing and E valuation, 2nd E dition, Chapter
1, John W iley and S o n s, N e w Y ork, 1979.
[13] C .W . C leverdon, J. M ills, and E .M . K een , F actors Determining the Perform ance ofIndexing System s, V ol. 1— D esign , A slib Cranfield R esearch Project, Cranfield,
England, 1966.
[14] F.W . L ancaster, Criteria by w hich Information Retrieval S ystem s M ay B e E valu ­ated, in Information R etrieval S y stem s— Characteristics, Testing and E valuation,
2nd E dition, Chapter 8, John W iley and S o n s, N e w Y ork, 1979.
[15] C .A . Cuadra and R .V . K atter, Experim ental Studies o f R elevance Judgm ents R e­
port TM -3520, Final R eport, V ol. 1, System D evelop m en t Corporation, Santa M on­
ica, California, June 1967.
[16] T- Saracevic, R elevance: A R eview o f and a Fram ework for the Thinking on the
N otion in Information S cien ce, Journal o f the A S IS , V ol. 26, N o . 6, N o v e m b e r D ecem ber 1975, pp. 3 2 1 -3 4 3 .
[17] W .S . C ooper, A D efinition o f R elevance for Information R etrieval, Information
Storage and R etrieval, V ol. 7, N o . 1, June 1971, pp. 19 -3 7 .
[18] W . G offm an, On R elevan ce as a M easure, Inform ation Storage and R etrieval, V ol.
2, N o . 3, D ecem ber 1964, pp. 20 1 -2 0 3 .
[19] W . Goffm an and V .A . N ew ill, M ethodology for T est and E valuation o f Information
R etrieval S ystem s, Com parative S ystem s L aboratory, R eport CSL: TR-2, W estern
R eserve U niversity, C leveland, O hio, July 1964.
[20] D .A . K em p, R elevan ce, Pertinence and Inform ation S ystem D evelop m en t, Infor­
m ation Storage and R etrieval, V ol. 10, 1974, pp. 3 7 -4 7 .
[21] S .E . R obertson, T he Probabilistic Character o f R elevan ce, Information Processingand M anagem ent, V ol. 13, N o . 4, 1977, pp. 2 4 7 -2 5 1 .
[22] M .E . Maron and J.L . K u h n s, On R elevan ce, Probabilistic Indexing and Informa­tion R etrieval, Journal o f the A CM , V ol. 7, N o . 3, July 1960, pp. 2 1 6 -2 4 4 .
[23] C .W . C leverdon and J. M ills, The Testing o f In d ex Language D e v ic e s, A slib Pro­
ceed in gs, V ol. 15, N o . 4, April 1963, pp. 106-130.
[24] G. Salton, editor, The SM A RT Retrieval S y stem — Experim ents in A utom atic D o c ­um ent P rocessing, Prentice-H all, In c., E n glew ood C liffs, N e w Jersey, 1971, Part 3.
[25] C.J. van Rijsbergen, Inform ation R etrieval, 2nd E dition, Chapter 7, Butterw orths,
L ondon, 1979.
[26] H . Gilbert and K . Sparck Jon es, Statistical B ases o f R elevan ce A ssessm en ts for the
Ideal Information R etrieval T est C ollection, C om puter Laboratory, U n iversity ofCambridge, B L R and D R eport 5481, Cambridge, England, M arch 1979.
[27] E ;M . K een , E valuation Param eters, in T he SM A R T Retrieval S y ste m — E xperi­
m ents in A utom atic D ocu m en t P rocessing, G. Salton, editor, Prentice-H all, In c.,
E nglew ood C liffs, N e w Jersey, 1971, Chapter 5.
[28] R .A . Fairthorne, B asic Parameters o f Retrieval T ests, Proceedings o f 1964 Annual
M eeting o f the A m erican D ocum entation Institute, Spartan B o o k s, W ashington,
1964, pp. 343-347.
[29] D . W illiam son, R. W illiam son, and M .E . L esk , The Cornell Im plem entation o f the194

CHAPTER 5

SM A RT S ystem , in T he SM ART Retrieval S y stem — E xperim ents in A utom atic
D ocum ent P rocessing, G. Salton, editor, P rentice-H all, In c ., E n glew ood C liffs,
N e w Jersey, 1971, Chapter 2.
[30] F .W . L ancaster, E valuating the Performance o f a Large Operating Inform ation R e­trieval S ystem , in E lectronic Handling o f Information: Testing and E valuation, A .
K ent, O .E . T aulbee, J. B elzer, and G .D . G oldstein, editors, T hom pson B o o k C o.,
W ashington, 1967, pp. 1 99-216.
[31] G. Salton, T he “ G enerality” E ffect and the R etrieval Evaluation for Large C ollec­
tion s, Journal o f the A S IS , V ol. 23, N o . 1, January-F ebruary 1972, pp. 1 1 -2 2 .
[32] M. T aube, A N o te on the Pseudom athem atics o f R elevan ce, A m erican D ocum enta­
tion, V ol. 16, N o . 2, April 1965, pp. 6 9 -7 2 .
[33] M .E . L esk and G. Salton, R elevan ce A ssessm en ts and Retrieval S ystem E valua­tion, Information Storage and R etrieval, V ol. 4, N o . 4, D ecem ber 1968, pp. 343—
359.
[34] V .E . Giuliano and P .E . Jo n es, Study and T est o f a M ethodology for Laboratory
E valuation o f M essage R etrieval S ystem s, R eport N o . E SD-TR -66-405, Arthur D.
L ittle, In c., Cambridge, A ugust 1966.
[35] R. A . Fairthorne, Im plications o f T est Procedures, in Information R etrieval in A c­tion, W estern R eserve U n iversity P ress, C leveland, O hio, 1963, pp. 1 09-113.
[36] S .E . R obertson, The Parametric D escription o f R etrieval T ests, Part I: The B asic
Param eters, Journal o f D ocum entation, V ol. 25, N o . 1, M arch 1969, pp. 1 -2 7 .
[37] C .W . C leverdon, Progress in D ocum entation: Evaluation T ests o f Information R e­trieval System s, Journal o f D ocum entation, V ol. 26, N o . 1, M arch 1970, pp. 5 5 -6 7 .
[38] T. Saracevic, A n Inquiry into Testing o f Inform ation Retrieval S y stem s, Part I: Ob­
je c tiv e s, M ethodology, D esign and C ontrols, C om parative S ystem s Laboratory,
R eport N o . CSL: T R -F IN A L -1, C ase W estern R eserve U n iversity, C leveland,
O hio, 1968.
[39] G .F . R om erio and L. Cavara, A ssessm en t Studies o f D ocum entation S y stem s, In­form ation Storage and R etrieval, V ol. 4, N o . 3, A ugust 1968, pp. 3 0 9 -3 2 5 .
[40] J.A . S w ets, E ffectiv en ess o f Information R etrieval M ethods, A m erican D ocum en­tation, V ol. 20, N o . 1, January 1969, pp. 7 2 -8 9 .
[41] B .C . B rook es, The M easure o f Information R etrieval E ffectiven ess P roposed by
S w ets, Journal o f D ocum entation, V ol. 24, N o . 1, March 1968, pp. 4 1 -5 4 .
[42] S .E . R obertson, The Parametric D escription o f Retrieval T ests, Part 1: T he B asic
Param eters, Journal o f D ocum entation, V ol. 25, N o . 1, M arch 1969, pp. 1 -2 7 ; Part
2: O verall M easures, Journal o f D ocum entation, V o l. 25, N o . 2, June 1969, pp. 9 3 107.
[43] M .H . H ein e, D esign E quations for Retrieval S y stem s B ased on the S w ets M odel,
Journal o f the A S IS , V ol. 25, N o . 3, M a y -J u n e 1974, pp. 183-198.
[44] R .R . V . W iederkehr, Search Characteristics C urves, in Evaluation o f D ocu m en t R e­trieval System s: Literature P erspective, M easurem ent, Technical Papers, W estat
R esearch Report PB 182710, B ethesda, M aryland, D ecem ber 1968.
[45] D .W . K ing and E .C . B ryant, T he E valuation o f Inform ation S ervices and Products,
Inform ation R esources P ress, W ashington, 1971, Chapter 9.
[46] A .R . M eetham , C om m unication Theory and the Evaluation o f Inform ation R e­trieval S ystem s, Inform ation Storage and R etrieval, V ol. 5, N o . 5, O ctober 1969,
pp. 129-134.
[47] R .H . Shum w ay, C ontingency Tables in Inform ation Retrieval: A n Information
T heoretic A n alysis, in E valuation o f D ocum ent R etrieval System s: Literature Per-RETRIEVAL EVALUATION

195

sp ective, M easurem ent, Technical Papers, W estat R esearch R eport PB 182710, Bethesda, M aryland, D ecem ber 1968.
[48] M . G uazzo, Retrieval Perform ance and Inform ation T heory, Inform ation Pro­
cessin g and M anagem ent, V ol. 13, N o . 3, 1977, pp. 155-165.
[49] A .E . C aw kell, A M easure o f Efficiency F actor— Com m unication T heory Applied
to D ocum ent Selection S y stem s, Information P rocessing and M anagem ent, V ol. 11,
N o . 8 -1 2 , 1975, pp. 2 4 3 -2 4 8 .
[50] J.J. R occhio, Jr., D ocu m en t Retrieval S y ste m s— Optimization and E valuation,
Harvard U niversity D octoral T h esis, Report N o . ISR-10 to the N ational Science
F oundation, Harvard Com putation Laboratory, M arch 1966.
[51] G. Salton, A utom atic Information Organization and R etrieval, M cGraw-Hill B ook
C o ., N e w Y ork, 1968, Chapter 8.
[52] W .S . C ooper, E xp ected Search Length: A Single M easure o f R etrieval E ffective­n ess B ased on the W eak Ordering A ction o f R etrieval S ystem s, A m erican D o cu ­m entation, V ol. 19, N o . 1, January 1968, pp. 3 0 -4 1 .
[53] S.M . P ollock, M easures for the Comparison o f Information Retrieval System s,
A m erican D ocum entation, V ol. 19, N o . 4, O ctober 1968, pp. 38 7 -3 9 7 .
[54] W .S . C ooper, On Selectin g a M easure o f Retrieval E ffectiv en ess, Part I: The Sub­
jectiv e P hilosophy o f E valuation; Part II: Im plem entation o f the P h ilosop h y, Jour­nal o f the A S IS , V ol. 24, 1973, pp. 8 7 -1 0 0 , 4 1 3 -4 2 4 .
[55] D .H . Kraft and A . B ook stein , E valuation o f Inform ation Retrieval S ystem s: A D e­
cision T heory A pproach, Journal o f the A S IS , V ol. 29, N o . 1, January 1978, pp.
3 1 -4 0 .
[56] W .S . C ooper, Indexing D ocum ents by Gedanken Experim entation, Journal o f theA S IS , V ol. 29, N o . 3, M a y -J u n e 1978, pp. 1 07-119.
[57] W .S . C ooper and M .E . M aron, Foundations o f Probabilistic and U tility Theoretic
Indexing, Journal o f the A C M , V ol. 25, N o . 1, January 1978, pp. 6 7 -8 0 .
[58] F .W . L ancaster, The C ost-E ffectiven ess A n alysis o f Information R etrieval andD issem ination S ystem s, Journal o f the A S IS , V ol. 22, N o . 1, January 1971, pp. 1 227.
[59] F .W . L ancaster, C ost-E ffectiven ess and C ost-B enefit Evaluation, in Information
R etrieval S y stem s— C haracteristics, Testing and E valuation, 2nd E dition, John
W iley and S on s, N e w Y ork, 1979, Chapter 16.
[60] A . G ilchrist, C ost-E ffectiv en ess, A slib P roceedings, V ol. 23, N o . 9, Septem ber
1971, pp. 4 5 5 -464.
[61] F . A louche, N . B ely , R .C . C ros, J.C. Gardin, F . L e v y , and J. Perreault, E con om ic
G6n6rale d ’une Chaine D ocum entaire M ecanis6e, Gauthier V illars, Paris, 1967.
[62] K .W . W ebb, W .C . Suhler, G .G . H eller, and S.P . T odd, Jr., Evaluation M odels for
inform ation Retrieval and Command and Control S ystem s (EM IR), IBM Corpora­tion Report, Federal S y stem s D ivision , W ashington, June 1964.
[63] A T im e/C ost Study o f Processing B ook s via U n it Orders and Blanket Orders, F ive •A ssociated U niversity Libraries, N ew sletter, V ol. 3, N o . 4, July 1972.
[64] G. W illiam s, E .C . Bryant, R .R .V . W iederkehr, V .E . Palmour, and C .J. Siehler, L i­brary C ost M odels: Ow ning versus Borrowing Serial Publications, C enter for R e­
search Libraries, W ashington, N ovem b er 1968.
[65] M .M . Cummings, N eed s o f the H ealth S cien ces, in Electronic Handling o f Informa­tion: T esting and E valuation, A . K ent, O .E . T aulbee, J. B elzer and G .D . G oldstein,
editors, T hom pson B o o k C o ., W ashington, 1967.
[66] C .W . C leverdon, The M ethodology o f E valuation o f Operational Inform ation Re-

196

CHAPTER 5

trieval System s B ased on the T est o f M edlars, Cranfield Institute o f T ech n ology R e­port, Cranfield, England, 1968.
[67] C .P. B ourne, G .D . P eterson , B . L efkow itz, and D . Ford, R equirem ents, Criteria
and M easure o f Perform ance o f Information Storage and Retrieval S y stem s, Final
R eport to N ational S cien ce Foundation, R eport A D 270 942, Stanford R esearch In­
stitute, D ecem ber 1961.
[68] Arthur A ndersen and C o ., R esearch Study o f Criteria and Procedures for Evaluat­
ing Scientific Information R etrieval S ystem s, Final Report to the N ational Science
F oundation, N e w Y ork, M arch 1962.
[69] C .P. Bourne and D .F . F ord, C ost A nalysis and Sim ulation Procedures for the E val­uation o f Large Inform ation S y stem s, A m erican D ocum entation, V ol. 15, N o . 2,
April 1964, pp. 142-149.
[70] N .R . Baker and R .E . N a n ce, T he U se o f Sim ulation in Studying Inform ation Stor­
age and Retrieval S y stem s, Am erican D ocum entation, V ol. 19, N o . 4, O ctober
1968, pp. 36 3 -3 7 0 .
[71] M .D . C ooper, A C ost M odel for Evaluating Inform ation Retrieval S y stem s, Journal
o f the A S IS , V ol. 23, N o . 5, S ep tem b er-O ctob er 1972, pp. 30 6 -3 1 2 .
[72] B .V . T ell, Auditing Procedures for Information Retrieval S ystem s, Proceedings
1965 F ID C ongress, Spartan B o o k s, W ashington, 1966, pp. 119-124.
[73] I.J. G ood, The D ecision -T h eory A pproach to the E valuation o f Inform ation R e­trieval S ystem , Inform ation Storage and R etrieval, V ol. 3, N o . 2, April 1967, pp.
3 1 -3 4 .
[74] J. Martyn and B .C . V ick ery, The C om plexity o f the M odelling o f Inform ation S y s­
tem s, Journal o f D ocum entation, V ol. 26, N o . 3, Septem ber 1970, pp. 2 0 4 -2 2 0 .
[75] D .H . R othenberg, A n E fficiency M odel and a Perform ance Function for an Infor­
m ation Retrieval S ystem , Information Storage and R etrieval, V ol. 5, N o . 3, O cto­
ber 1969, pp. 109-122.
[76] N .R . K eith, Jr., A General E valuation M odel for an Information Storage and R e­trieval System , Journal o f the A S IS , V ol. 21, N o . 4, J u ly -A u g u st 1970, pp. 2 3 7 239.
[77] E .C . Bryant, M odeling in D ocum ent Handling, in E lectronic Handling o f Informa­tion: T esting and E valuation, A . K ent, O .E . T aulbee, J. B elzer, and G .D . G old­
stein, editors, T hom pson B o o k C o ., W ashington, 1967, pp. 163-173.
[78] R .R .V . W iederkehr, A N e t B enefit M odel for Evaluating E lem entary D ocum ent
R etrieval Sy stem s, in E valuation o f D ocum ent R etrieval S y stem s, W estat R esearch
R eport, PB 182710, B eth esd a, M aryland, D ecem ber 1968.

BIBLIOGRAPHIC REMARKS

Many materials covering the evaluation of information retrieval operations andsystems appear in the report literature that may not be easy to obtain. Two of
the best known of these reports cover the well-known Aslib-Cranfield study
and the evaluation of the MEDLARS retrieval service:
C .W . C leverdon, J. M ills, and E .M . K een , F actors D eterm ining the Perform ance o f In­
dexing System s, V ol. 1— D esign , Aslib-Cranfield R esearch Project, Cranfield, E n­gland, 1966.
F .W . L ancaster, E valuation o f the M edlars D em and Search Service, N ational Library ofM edicine, B ethesda, M aryland, January 1968.

RETRIEVAL EVALUATION

197

The following references contain discussions dealing with theoretical as­
pects of retrieval system evaluation:
T. Saracevic, R elevance-A R ev iew o f and a Fram ew ork for the Thinking on the N otion
in Information S cien ce, Journal o f the Am erican S ociety for Inform ation Scien ce,
V ol. 26, N o . 6, N o v e m b e r -D e c e m b e r 1975, pp. 32 1 -3 4 3 .
M .E . M aron, editor, T heory and Foundations o f Inform ation R etrieval, D rexel Library
Quarterly, V ol. 14, N o . 2, April 1978.
C . J. van R ijsbergen, Inform ation R etrieval, 2nd E dition, Chapter 7, B utterw orths, L on ­don, 1979.

The following texts all deal extensively with various aspects of retrieval
system evaluation:iF.W . L ancaster, Information R etrieval S y stem s— Characteristics, T esting and E valua­tion, 2nd E dition, John W iley and S on s, N e w Y ork, 1979.
A . K ent, O .E . T aulbee, J. B elzer, and G .D . G oldstein, editors, E lectronic Handling of- Information: Testing and E valuation, T hom pson B ook Com pany, W ashington,
D C ., 1967.
D . W . K ing and E .C . Bryant, T he E valuation o f Inform ation S ervices and Products, In­form ation R esources P ress, W ashington, D C ., 1971.

EXERCISES
5-1

5-2

5-3

5-4

C onsider a retrieval system capable o f presenting the output item s to the user popu­
lation in a ranked seq u en ce in decreasing order o f presum ed u sefu ln ess. Consider
tw o particular queries each having 10 relevant docum ents in a collection . The rankso fth e relevant docum ents for query 1 are 1, 3, 5, . . . ,19, and for query 2 the ranks
are 2, 4, 6, . . . ,20.
a Prepare recall-precision tables and graphs for the tw o queries similar to thoseshow n in Fig. 5-2 for a sam ple query.
b W hat is the m ost o b viou s difference in the evaluation results obtained for thetw o queries? D o you ex p ect this difference to affect a system s evaluation in
w hich results are averaged over several queries? W hy?
c Prepare recall-precision tables and graphs show ing recall-level and docum entlev el averages for the recall and precision results obtained for the tw o queries.
T he fallout evaluation m easure has been called superior to precision for a numbero f reasons. W hat are th ey? U nder what circum stances w ould you prefer to deal
w ith a recall-fallout evaluation instead o f a recall-precision output?
Prepare probability d en sity output and operating characteristic curves similar toth ose show n in F igs. 5-7 and 5-8 reflecting the perform ance o f the set o f relevant
item s and the set o f nonrelevant item s, resp ectively, with respect to som e query forthe follow ing cases:a A ll relevant item s are retrieved ahead o f all nonrelevant ones,b A ll nonrelevant item s are retrieved ahead o f all relevant ones,c The relevant item s are randomly sprinkled am ong the nonrelevant on es,
d The retrieval output fo llo w s the pattern specified for queries 1 and 2 o f E xercise
5-1.
D erive the equation for the norm alized precision m easure given in exp ression (15).

198

5-5

CHAPTER 5

Furnish a construction for the normalized precision similar to the on e given in Fig.
5-10 for the norm alized recall.
A ssu m e that the tw o queries o f E xercise 5-1 are retrieved in groups o f three item seach , that is, the first three item s are retrieved together, follow ed by the n ext three
item s, and so on, until the last item s are retrieved. Com pute the average searchlengths obtained for the tw o queries, assum ing the users w ish to retrieve 10 docu­
m ents in all, 15 docum ents in all, or 20 docum ents in all.