IR evaluation methods for retrieving highly relevant documents
K a l e r v o J~irvelin & Jaana Kekiil~iinen
University of Tampere
Department of Information Studies
FIN-33014 University of Tampere
FINLAND
Emaih {kalervo.jarvelin, jaana.kekalainen} @uta.fi

Abstract
few tests actually take advantage of different relevance levels(e.g., [6]). More often relevance is conflated into two categories
at the analysis phase because of the calculation of precision andrecall (e.g., [2, 15]).
In modem large database environments, the number of topically relevant documents to a request may easily exceed thenumber of documents a user is willing to examine. It would
therefore be desirable from the user viewpoint to rank highly
relevant documents highest in the retrieval results and to develop and evaluate IR methods accordingly. However, the current practice of liberal binary assessment of topical relevancegives equal credit for a retrieval method for retrieving highly
and fairly relevant documents. Therefore differences between
sloppy and excellent retrieval methods may not become apparent in evaluation. In this paper, we want to examine the effects
of using multiple degree relevance assessments in retrieval
method evaluation and to demonstrate, by virtue of a case, thatsuch assessments indeed may reveal important differences between retrieval methods.
The effects of using multiple degree relevance assessments
may be evaluated through traditional IR evaluation methods
such as P-R curves. In this paper we apply P-R curves in a newway, focusing on retrieval at each relevance level separately.
Moreover, to emphasize the user viewpoint, we develop new
evaluation measures, which seek to estimate the cumulative
relevance gain the user receives by examining the retrieval
result up to a given rank. These measures facilitate evaluation
where IR methods are credited more / only for highly relevant
documents. These novel measures are akin to the average
search length (briefly ASL; [12]), ranked half life and relative
relevance (briefly RHL and RR; [3]) measures but offer several
advantages by taking both the degree of relevance and the rank
position (determined by the probability of relevance) of adocument into account. (For a discussion of the degree of relevance and the probability of relevance, see [ 14].)
The case demonstrating the effects of multiple degree relevance assessments, and the application of traditional / novel
evaluation measures explores query expansion and query structures in probabilistic IR. Kekal~iinen [9], and Kek~ilainen and
Jarvelin [11 ] have earlier observed that the structure of queries
influences retrieval performance when the number of searchThis paper proposes evaluation methods based on the use ofnon-dichotomous relevance judgements in IR experiments. It isargued that evaluation methods should credit IR methods fortheir ability to retrieve highly relevant documents. This is desirable from the user point of view in modem large IR environments. The proposed methods are (1) a novel application of
P-R curves and average precision computations based on separate recall bases for documents of different degrees of relevance, and (2) two novel measures computing the cumulative
gain the user obtains by examining the retrieval result up to agiven ranked position. We then demonstrate the use of theseevaluation methods in a case study on the effectiveness ofquery types, based on combinations of query structures andexpansion, in retrieving documents of various degrees of relevance. The test was run with a best match retrieval system (InQuery I) in a text database consisting of newspaper articles. The
results indicate that the tested strong query structures are mosteffective in retrieving highly relevant documents. The differences between the query types are practically essential andstatistically significant. More generally, the novel evaluation
methods and the case demonstrate that non-dichotomous relevance assessments are applicable in IR experiments, may reveal
interesting phenomena, and allow harder testing of IR methods.

1. Introduction
Fundamental problems of IR experiments are linked to the assessment of relevance. In most laboratory tests documents are
judged relevant or irrelevant with regard to the request. However, binary relevance cannot refect the possibihty that documents may be relevant to a different degree; some documents
contribute more information to the request, some less w~thout
being totally irrelevant. In some studies relevance judgements
are allowed to fall into more than two categones, but only a
Permission to make digital or hard copies of all or part of thin work forpersonal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.
To copy otherwise, to republish, to post on servers or to
redmtnbute to lists, requires prior specific permission and/or a fee.
SIGIR 2 0 0 0 7•00 Athens, Greece@ 2 0 0 0 A C M 1o58113-226-3/0010007...$5.00

IThe InQuery software was provided by the Center for intelhgent Information Remeval, Umverslty of Massachusetts Computer Science Department, Amherst, MA, USA

41

ACM SIGIR Forum

243

Vol. 51 No. 2, July 2017

keys in queries is high, i.e., when queries are expanded. Querystructure refers to the syntactic structure of a query expression,
marked with query operators and parentheses. Kek~ilainen andJ~irvelin classify the structures of best match queries into strong
and weak. In the former, search keys are grouped according toconcepts they represent; in the latter, queries are mere sets ofsearch keys. They reported significant retrieval improvementswith expanded strongly structured queries. However, in theirstudy the relevance assessments were dichotomous.We therefore do not know how different best match query types (basedon expansion and structure) are able to rank documents of varying relevance levels. In the case study we investigate their ability to do this.
Section 2 explains our evaluation methodology: the novel
application of the P-R curves and the cumulated gain-based
evaluation measures. Section 3 presents the case study. The test
environment, relevance assessments, query structures and expansion, and the retrieval results are reported. Section 4 contains discussion and conclusions.

2 Evaluation methods employing multiple degree
relevance assessments
2.1

Precision as a function of recall

Average precision over recall levels and P-R curves are thetypical ways of evaluating IR method performance. They arenormally computed by using dichotomical relevance assessments. Even if the original assessments may have had multiple
degrees, these are generally collapsed into two for evaluation.
In order to see the difference in performance between retrieval
methods, their performance should be evaluated separately ateach relevance level. For example, in case of a four point assessment (say, 0 to 3 points), separate recall bases are needed
for highly relevant documents (relevance level 3), fairly relevant documents (relevance level 2), and marginally relevant
documents (relevance level I). The rest of the database is consldered irrelevant (relevance level 0). In this study, we complied the recall bases for P-R curve computation in this way.

2.2

G ' = < 3, 2, 3,0, 0, 1 , 2 , 2 , 3 , 0 . . . . >The cumulated gain at ranked position i is computed bysumming from position 1 to i when i ranges from 1 to 200.
Formally, let us denote position i in the gain vector G by G[i].
Now the cumulated gain vector CG is defined recursively as thevector CG where:
G i l l , if i = 1
CG[i] = I C G [ i -11 + G[i], otherwise(1)
For example, from G' we obtain CG' = < 3, 5, 8, 8, 8, 9, I 1,
13, 16, 16 . . . . >. The cumulated gain at any rank may be readdirectly, e.g., at rank 7 it is 11.
Point two leads to comparison of IR methods through test
queries by their cumulated gain based on document rank with arank-based discount factor: the greater the rank, the smaller
share of the document value is added to the cumulated gain.
The greater the ranked position of a relevant document - of any
relevance level - the less valuable it is for the user, because theless likely it is that the user will examine the document due totime, effort, and cumulated information from documents already seen. A discounting function is needed which progressively reduces the document value as its rank increases but not
too steeply (e.g., as division by rank) to allow for user persistence in examining further documents. A simple way of discounting with this requirement is to divide the document value
by the log of its rank. For example 2log 2 = 1 and 21og1024 =10, thus a document at the position 1024 would still get one
tenth of it face value. By selecting the base of the logarithm,
sharper or smoother discounts can be computed to model varying user behaviour. Formally, if b denotes the base of the logarithm, the cumulated gain vector with discount DCG is definedrecursively as the vector DCG where:

I'G[l],if i= 1
DCGlil. . = /L D C G [ i -l] + G[i] / blog i, otherwise

Cumulated gain -based measurements(2)

When examining the ranked result list of a query, it is obvious
that:
1. highly relevant documents are more valuable than marginally relevant documents, and2. the greater the ranked position of a relevant document(of any relevance level) the less valuable it is for the user,
because the less likely it is that the user will examine thedocument.
Point one leads to comparison of IR methods through test
queries by their cumulated gain by document rank. in thisevaluation, the relevance level of each document is somehow
used as a gamed value measure for its ranked position m theresult and the gain is summed progressively from position 1 ton. Thus the ranked document lists (of some determined length)
are turned to gamed value lists by replacing document IDs by
their relevance values. Assume that the relevance values 0 - 3
are used (3 denoting high value, 0 no value). Turmng document
lists up to rank 200 to corresponding value lists gives vectors of
200 components each having the value 0, 1, 2 or 3. For example:

Note that we must not apply the logarithm-based discountat rank l because blog l = 0.
For example, let b = 2. From (3' we obtain DCG' = < 3, 5,
6.89, 6.89, 6.89, 7.28, 7.99, 8.66, 9.61, 9.61 . . . . >.
The (lack of) ability of a query to rank highly relevant
documents toward the top of the result list should show on boththe cumulated gain by document rank (CG) and the cumulated
gain with discount by document rank (DCG) vectors. By averaging over a set of test queries, the average performance of aparticular IR method can be analysed. Averaged vectors havethe same length as the individual ones and each component igives the average of the ith component in the individual vectors. The averaged vectors can directly be visualised as gainby-rank -graphs.
The actual CG and DCG vectors by a particular IR method
may also be compared to the theoretically best possible. The
latter vectors are constructed as follows. Let there be k, l, and m
relevant documents at the relevance levels l, 2 and 3 (respectively) for a given request. First fill the vector positions I ... mby the values 3, then the positions m+l ... m+l by the values 2,

42

ACM SIGIR Forum

244

Vol. 51 No. 2, July 2017

then the positions m+/+l ... m+l +k by the values 1, and finallythe remaining positions by the values 0. Then compute CG and
DCG as well as the average CG and DCG vectors and curves asabove. Note that the curves turn horizontal when no more relevant documents (of any level) can be found. They do not unrealistically assume as a baseline that all retrieved documents
could be maximally relevant. The vertical distance between an
actual (average) (D)CG curve and the theoretically best possible curve shows the effort wasted on less-than-perfect documents due to a particular IR method.
The CG measure has several advantages when comparedwith the average search length (ASL) measure [12]. or the RR
and RHL measures [3]:1. It combines the degree of relevance of documents andtheir rank (affected by their probability of relevance) in a
coherent way. The RR is based on comparing the match between the system-dependent probability of relevance andthe user-assessed degree of relevance. The ASL measure isdichotomical.
2. At any number of retrieved documents examined(rank), it gives an estimate of the cumulated gain as a single
measure no matter what is the recall base size. The ASL
measure only gives the average position of a relevant
document for a given recall base. The RHL measure gives
the median point of accumulated relevance for a given
query result, which may be the same for quite differently
performing queries.
3. It is not heavily dependent on outliers (relevant documents found late in the ranked order) since it focuses on thegain cumulated from the beginning of the result. The ASL
and RHL are dependent on outliers although RHL is lessSO.

4. It is obvious to interpret, it is more direct than P-R
curves, and it does not mask bad performance. The RHL
alone is not sufficient as a performance measure.
In addition, the DCG measure has the following further advantages not provided by the ASL or RHL measures:
1. It realistically weights down the gain received throughdocuments found later in the ranked results.
2. It allows modelling user persistence in examining longranked result lists by adjusting the discounting factor.

3. Case study: the effectiveness of QE and query
structures at different relevance levels
We demonstrate the use of the proposed measures in a casestudy testing the co-effects of query expansion and structured
queries in a database with non-binary relevance judgements.
Based on the results by Kekid~iinen and Jarvelin [11] we already know that weak query structures are not able to benefit
from query expansion whereas the strong ones are. In the present study we shall test whether the performance of differently
structured queries varies with relation to the degree of relevance. We give the results as traditional P-R curves for eachrelevance level, and as CG and DCG curves which exploit thedegrees of relevance. We hypothesize that expanded quenes
based on strong structures are better able to rank highly relevant documents high in the query results than unexpanded queries or queries based on other structures, whether expanded ornot. Consequently, the performance differences between querytypes among marginally relevant documents should be mar-

ginal and among highly relevant documents essential. Expanded queries based on strong structures should cumulate
higher CG and DCG values than unexpanded queries or queries
based on other structures, whether expanded or not.

3.1

Test environment

The test environment was a text database containing newspaper
articles operated under the InQuery retrieval system (version3.1). The database contains 53,893 articles published in threedifferent newspapers. The database index contains all keys intheir morphological basic forms, and all compound words are
split into their component words in. their morphological basic
forms. For the database there is a collection of requests, whichare 1 - 2 sentences long, in the form of wntten informationneed statements. For these requests there is a recall base of
16,540 articles which fall into four relevance categories (seebelow Relevance assessments). The base was collected by pooling the result sets of hundreds of different queries formulated
from the requests in different studies, using both exact andpartial match retrieval. We thus believe that our recall estimatesare valid. For a set of tests concerning query structures, 30 requests were selected on the basis of their expandability, i.e.,they provided possibilities for studying the interaction of query
structure and expansion. [9, 10, 17.]
The lnQuery system was chosen for the test, because it has
a wide range of operators, including probabilistic interpretations of the Boolean operators, and it allows search key
weighting. InQuery is based on Bayesian inference networks.
For details of the InQuery system, see [1, 13, 18].

3.2 Relevance assessments
For the test requests and test collection of the present experiment, relevance was assessed by four persons, two experienced
journalists and two information specialists. They were given
written information need statements (requests), and were asked
to judge the relevance on a four level scale: (0) irrelevant, thedocument is not about the subject of the request, (1) marginally
relevant, the topic of the request is mentioned, but only in passing, (2) fairly relevant, the topic of request is discussed briefly,(3) highly relevant, the topic is the main theme of the article.
The relevance of 20 requests (of 35) was assessed by two (oneby three) persons, the rest by one person. The assessors agreed
in 73% of the parallel assessments, in 21% of the cases thedifference was one point, and in 6% two or three points. If thedifference was one point, the assessment was chosen from eachjudge in turn. If the difference was two or three points, the article was checked by the researcher to find out if there was a
logical reason for disagreement, and a more plausible alternative was selected. [9, 17.]
The recall bases for the 30 requests of the present study includes 366 highly relevant documents (relevance level 3), 700
fairly relevant documents (relevance level 2), 857 marginally
relevant documents (relevance level 1). The rest of the database, 51,970 documents, is considered irrelevant (relevancelevel 0).

3.3

Query structures and expansion

In text retrieval an information need is typically expressed as aset of search keys. In exact match - or Boolean - retrieval relations between search keys in a query are marked with the AND
operator, the OR operator, or proximity operators which, in

43

ACM SIGIR Forum

245

Vol. 51 No. 2, July 2017

fact, are stricter forms of the AND operator. Thus, the query
has a structure based on conjunctions and disjunctions of searchkeys. [5, 8.] A query constructed with the Boolean block searchstrategy (a query in the conjunctive normal form), is an example of a facet structure. Within a facet, search keys representing
one aspect of a request are connected with the OR operator, andfacets are connected with the AND operator. A facet may consist of one or several concepts.
In best match retrieval, matching is ranking documents according to scores calculated from the weights of search keys
occurring in documents. These weights are typically based on
the frequency of a key in a document and.on the inverse collection frequency of the documents containing the key (tf*idf
weighting). [7.] In best match retrieval, queries may either havea structure similar to Boolean queries, or queues may be 'natural language queries' without differentiated relations between
search keys.
Kek~il~iinen and J~irvelin [ 11 ] tested the co-effects of query
structures and query expansion on retrieval performance, andascertained that the structure of the queries became importantwhen queries were expanded. The best performance overall
was achieved with expanded, facet structured queries. For thepresent study, we selected their best weak structure (SUM) andtwo of their best strong structures, one based on concepts(SSYN-C) and another based on facets (WSYN). SUM queries
may be seen as typical 'best match" queries and therefore suitable as a baseline.
In query formulation, researchers identified search concepts
from requests and elicited corresponding search keys from atest thesaurus containing more than 1000 concepts and morethan 1500 expressions for the domains of the test requests (see[9]). In QE, search keys that were semantically related (synonyms, hierarchies, associations) to the original search concepts
in the test thesaurus were added to queries. This procedure gave
unexpanded (u) and expanded (e) query versions, which bothwere formulated into different query structures.
The structures used to combine the search keys are exemplified in the following. Examples are based on a sample request The processing and storage of radioactive waste. In thefollowing samples queries are expanded, the expressions of theunexpanded queries are in italics.
SUM (average of the weights of keys) queries represent
weak structures. In these queries search keys are single words,
i.e., no phrases are included.
SUM/e#sum(radioactive waste nuclear waste high active waste
low active wastespent fuel fission product storage store
stock repository process refine)
In a SUM-of-synonym-groups-query (SSYN-C) each searchconcept forms a clause with the SYN operator. SYN clauses
were combined with the SUM operator. Phrases were used(marked with #3). All keys within the SYN operator are treatedas instances of one key [131.
SSYN-C/e#sum(#syn(#3(radioactive waste) #3(nuclear waste)#3(high active waste) #3(low active waste)#3(spent fuel) #3(fission product))#syn(storage store stock repository)#syn(process refine))

WSYN queries were similar to SSYN, but based on facets instead of concepts. Facets were divided into major and minor
facets according to their importance for the request. In WSYN
queries, the weight of major facets was 10 and of minor facets
7.
WSYN/e#wsum(l 10 #syn(#3(radioactive waste) #3(nuclear waste)#3(high active waste) #3(low active waste)#3(spent fuel) #3(fission product))
7 #syn(storage store stock repository process
refine))3.4 Test queries and the application of the evaluation
measuresIn the queries for the 30 test requests, the average number offacets was 3.7. The average number of concepts in unexpanded
queries was 4.9, and in expanded queries 26.8. The the numberof search keys of unexpanded queries when no phrases weremarked (i.e., SUM structure) was 6.1 on average, and for expanded queries without phrases, on average, 62.3. The numberof search keys with phrases (i.e., SSYN-C, and WSYN structures) was 5.4 for unexpanded queries, and 52.4 for expanded
queries, on average.
The length of relevant documents at all relevance levels exceeded the average length of documents in the database (233words). However,.the documents at relevance level 3 were, on
average, shorter than documents at relevance levels 2 or 1. The
average document lengths were 334 words at relevance level 1;
314 words at level 2; and 306 words at level 3. Because thediferences in average document lenghts are minor, highly relevant documents did not gain from higher document length.
We present the analysis of the search results in two forms:
First, we apply the conventional measures in the form of P-R
curves. We also calculated precision after each retrieved relevant document and took an average over requests (average noninterpolated precision, AvP for short). We chose AvP rather
than precision based on document cut-off values, because thesizes of recall bases vary at different relevance levels, and thus
one cut-off value will not treat queries equally with relation toprecision. The statistical significance of differences in the effectiveness of query types was established with the Friedman
test (see [4]).
Second, we present the CG and DCG curves. For the cumulative gain evaluations we tested the same query types in separate runs with the logarithm bases and the handling of relevancelevels varied as parameters as follows:
1. The logarithm bases 2, e, and 10 were tested for the
DCG vectors. The base 2 models impatient users, base 10
persistent ones.
2. We used document relevance levels 0 - 3 directly as
gamed value measures. This can be cfiticised, e.g., by asking whether a highly relevant document~is (only) threeumes as valuable as a marginally relevant document. Nevertheless, even this gives a clear difference for document
quality to look at.
3. We first took all documents at relevance levels l - 3
into account, secondly nullified the values of documents atrelevance level 1 (to reflect that they practically have novalue), and finally nullified the values of documents atrelevance levels 1 - 2 in order to focus on the highly relevant documents.

44

ACM SIGIR Forum

246

Vol. 51 No. 2, July 2017

A
100

.

.

B
.

.

.

.

.

.

.

.

.

100

C

. . . .

,

,

.

.

.

.

O0

• wsyn/e
O wsyn/u

80,

-

80

60.~

• ssyn-c/e
O ssyn-c/u=.~ 60,
.U

i

[ 60
.~
.E

~ - 4 0 ]'Ilsum/e~.o 4 0

= 80
o

20.
0.
0

~

;

~~
, 40

i

20

2

0
20

40
60
Recall80

100

0. . . . . . . . .
20 40
60
80
Recall

100

0

20

40
60
Recall80

100

F i g u r e l . P-R curves of SUM, SSYN-C, and WSYN queries at relevance levels 1 (A), 2 (B), and 3 (C).

4. The average actual CG and DCG vectors were compared to the theoretically best possible average vectors.
3.5

most often expanded weak queries, but also unexpanded weak
and unexpanded strong queries.
3.6

P-R curves and average precision

Figure 1 presents the P-R curves of the six query types at different relevance levels. At the relevance level 1, the curves arealmost inseparable. At the relevance level 2, expanded WSYN
and SSYN-C queries are more effective than the other querytypes. At the relevance level 3, the difference is even more
accentuated. The higher the relevance level is, the greater are
the differences between the best and the worst query types.
In Table 1 the average precision (AvP) figures are given, it
can be seen that QE never enhances the average precision of
SUM queries. In contrast, QE always improves the average
precision of strongly structured queries. When queries are unexpanded the differences in precision are negligible within eachrelevance level. The best effectiveness over all relevance levels
is obtained with expanded WSYN queries. At the best, the difference in average precision between unexpanded SUM andexpanded WSYN queries is at the relevance level 3 (AvP: achange of 15.1 percentage units or an improvement of 58.3 %).
In other words, expanded queries with strong structure are mosteffective in retrieving the most relevant documents.
Rel.
level

Exp.
typ

Structure type

1

u
e

SUM
12.8
10.1

SSYN-C
12.4
13.3

WSYN
13.8
14.3

2

u
e

22.4
21.1

21.5
27.4

22.9
29.3

3

u
e

25.9
22.2

23.5
39.1

25.7
41.0

Figure 2 presents the CG vector curves for ranks 1 - 100, thesix query types studied above and the theoretically best possible (average) query. Figure 2A shows the curves when documents at both relevance levels 2 and 3 are taken into account(i.e., they earn 2 and 3 points, respectively). The best possible
curve almost becomes a horizontal line at the rank 100 reflectmg the fact that at rank 100 practically all relevant documents
have been found. The two best (synonym structured) querytypes hang below by 18 - 27 points (35 - 39 %) from the rank
20 to 100. The difference is the greatest in the middle range.
The other four query types remain further below by 5 - 15
points (about 16 - 24 %) from rank 20 to 100. The difference tothe best possible curve is 23 - 38 points (50 %). Beyond therank 100 the differences between the best possible and all actual curves are all bound to diminish. Figure 2B shows thecurves when documents only at the relevance level 3 considered. The precise figures are different and the absolute differences smaller. However, the proportional differences are larger.
The curves can be interpreted also in another way: at therelevance level 3 one has to retrieve 34 documents by the bestquery types, and 62 by the other query types, in order to gain
the benefit that could theoretically be gained by retrieving only
10 documents. In this respect the best query types are nearly
twice as effective as the others. At the relevance levels 2&3 thecorresponding figures are 20 and 26 documents. At the greatest,
the difference between the best and the remaining query types
is 6 - 8 points (or two documents, relevance level 3) at ranks 40- 60. At relevance levels 2&3 the greatest differences are 5 - 15
points (or 2 - 7 documents) at ranks 40 - 100.
3.7

Table 1. Average non-interpolated precision figures for different query types.

The Friedman test corroborates that the differences in precision
figures are more significant at relevance level 3 than at theother relevance levels. Expanded strong queries outperform

Cumulative gain

Discounted cumulative gain

Figure 3 shows the DCG vector curves for ranks 1 - 50, the six
query types studied above and the theoretically best possible(average) query. The log2 of the document rank is used as thediscounting factor. Figure 3A shows the curves when documents both at the relevance levels 2 and 3 are taken into account. The best possible curve still grows at the rank 50 (itlevels off at the rank 90). The two best (synonym structured)45

ACM SIGIR Forum

247

Vol. 51 No. 2, July 2017

A

B

i

80~ ~ best possible• wsyrVe7£ o ws~u• ssyn-c/e

6o:
so:
,o:

6~ 0 ssyn-c/u~50

I I surrVe
13 sum/u

40

0

20

40

60

80

100

0

20

40

DCV

60

80

100

DCV

Figure 2. Cumulative gain curves at ranks l-I00, relevance levels 2&3 (A), and 3 (B).

query types hang below by 5 - 9 points (35 - 36 %) from therank 10 to 50. The difference is growing. The other four querytypes remain further below by 2 - 4 points (15 - 27 %) fromrank 10 to 50. The difference to the best possible curve is 7 - 13
points (47 - 50 %). Beyond the rank 50 the differences between
the best possible and all actual curves gradually become stable.
Figure 3B shows the curves when documents only at the relevance level 3 considered. The precise figures are different andthe absolute diferences smaller. However, the proportional
differences are larger. At the greatest, the difference between
the best and the remaining query types is 3 points (or one level- 3 document) at the rank 40 and further. It is a consistent andstatistically significant difference but are the users able to nottce it?
Also these curves can be interpreted in another way: at therelevance level 2&3 one has to expect the user to examine 35
documents by the best query types, and 70 by the other querytypes, in order to gain the (discounted) benefit that could theo-

reticaUy be gained by retrieving only l0 documents. User persistence up to 35 documents is not unrealistic whereas up to 70
it must be rare. The difference in query type effectiveness isessential. At the relevance level 3 the discounted gains of thebest query types never reach the gain theoretically possible atthe rank I0. The theoretically possible gain at the rank 5 isachieved at the rank 50 and only by the best query types.
One might argue that if the user goes down to 70 documents, she gets the real value, not the discounted one and therefore the DCG data should not be used for effectiveness comparison. While this may hold for the user situation, the DCGbased comparison is valuable for the system designer. The user
is less likely to scan that far and thus documents placed there
do not have their real relevance value; a retrieval system or
method placing relevant documents later in the ranked results
should not be credited as much as another system or method
ranking them earlier.

A

B

30

best posstble
25.

ws~/e
~ ws~/u25$ ssyn-c/e
20, O ssyn-cJu• sum/e¢3

Elsum/u

.

_

.

-

.

10
5
0

. . . . .

.

,

i0

.

,

.

20

30

.

,,,

•

40

-

,

50

0

DCV

10

20

DCV

30

40

50

Figure 3. Discounted (log2) cumulative gain curves ranks 1-50, relevance levels 2&3 (A), and 3 (B).

46

ACM SIGIR Forum

248

Vol. 51 No. 2, July 2017

The main findings are similar with the other logarithm bases wetested. However, the magnitude of the differences between thebest and worst query types grows from 4 points for log2 to 13
points for log~0 at the rank 50 (obviously). This means that for a
persistent user the best methods are 13 points (or 27 %) better
than the remaining ones. For an impatient one, they are only 4
points better.

4

Discussion and conclusions

We have argued that in modern large database environments,
the development and evaluation of IR methods should be basedon their ability to retrieve highly relevant documents. This is
desirable from the user viewpoint and presents a not too liberal
test for IR methods. We then developed two methods for 1R
method evaluation, which aim at taking the document relevancedegrees into account. One is based on a novel application of the
traditional P-R curves and separate recall bases for each relevance level of documents. The other is based on two novel
evaluation measures, the CG and the DCG measures, whichgive the (discounted) cumulative gain up to any given document rank in the retrieval results. Both measures systematicallycombine document rank (based on its probability of relevance)and degree of relevance.
In the case study we demonstrated the use of these evaluation methods in the evaluation of the effectiveness of various
query types which were varied in structure and expansion. Our
hypotheses were that:• the performance differences between query types
among marginally relevant documents should be marginal
and among highly relevant documents essential when measured by the P-R curves,• strongly structured expanded queries present better effectiveness than unexpanded queries or queries based onother structures, whether expanded or not, and• expanded queries based on strong structures cumulate
higher CG and DCG values than unexpanded queries or
queries based on other structures, whether expanded or not.
These hypotheses were confirmed. The differences between
the performance figures of the best and worst query types are
consistent and statistically very significant. We valued the
documents at different relevance levels rather equably, however, the user might value documents at relevance level 3 muchhigher than documents at other relevance levels. Thus, ouranalysis perhaps led to rather conservative, although significant
results.
The P-R curves demonstrate that the good performance ofthe expanded structured query types is due to, in particular,
their ability to rank the highly relevant documents toward the
top of retrieval results. The cumulative gain curves illustrate thevalue the user actually gets, but discounted cumulative gain
curves can be used to forecast the system performance withregard to a user's patience in examining the result list. With asmall log base, the value of a relevant document decreases
quickly along the ranked hst and a DCG curve turns horizontal.
This assumes an impatient user for whom late coming reformation is not useful because it will never be read. If the CG and
DCG curves are analysed horizontally, we may conclude that asystem designer would have to expect the users to examine by
50 to 100 % more documents by the worse query types to collect the same gain collected by the best query types. While it Is

possible that persistent users go way down. the result list, e.g.,
from 30 to 60 documents, it often is unlikely to happen, and asystem requiring such a behaviour is, in practice, much worse
than a system yielding the gain within a 50 % of the documents.
The novel CG and DCG measures complement the modified P-R measure. Precision over fixed recall levels hides theuser's effort up to a given recall level. The DCV-based precision - recall curves are better but still do not make the value
gained by ranked position explicit. The CG and DCG curves
provide this directly. The distance to the theoretically best possible curve shows the effort wasted on less-than-perfect or useless documents. The advantage of the P-R measure is that ittreats requests with different number of relevant documents
equally, and from the system's point of view the precision ateach recall level is comparable. In contrast, CG and DCG
curves show the user's point of view as the number of documents needed to achieve a certain gain. Together with the theoretically best possible curve they also provide a stopping rule,that is, when the best possible curve turns horizontal, there isnothing to be gained by retrieving or examining further documents.
Generally, the evaluation methods and the case demonstratethat non-dichotomous relevance assessments are applicableeven in IR experiments, and may reveal interesting phenomena.
The dichotomous relevance assessments generally applied may
be too permissive, and, consequently, too easily give credit toIR system performance. We believe that, in modern large environments, the proposed modified P-R measure and the novel(D)CG measures should be used whenever possible, because
they provide richer information for evaluation.

Acknowledgements.
This study was funded in part by Academy of Finland under the
grant number 44703. We thank the FIRE group at University of
Tampere, especially Heikki Keskustalo and Eero Sormunen, for
helpful comments, and Heikki Keskustalo and Timo Tervola
for programming efforts for data analysis.

References[1] J. Allan, J. Callan, B. Croft, L. Ballesteros, J. Broglio, J. Xu& H. Shu. INQUERY at TREC 5. In E.M. Voorhees &D.K. Harrnan (Eds.), Information technology: The Fifth
Text Retrieval Conference (TREC-5). Gaithersburg, MD:
National Institute of Standards and Technology, 119-132,! 997.
[2] D.C. Blair, & M.E. Maron. An evaluation of retrieval effecuveness for a full-text document-retrieval system. Communications of the A CM, 28(3): 289-299, 1985.
[3] P. Borlund & P. Ingwersen. Measures of relative relevanceand ranked half-life: Performance indicators for interactive
IR. In W.B. Croft, A. Moffat, C.J. van Rijsbergen, R. Wilkinson & J. Zobel (Eds.), Proceedings of the 21st Annual

International ACM SIGIR Conference on Research and47

ACM SIGIR Forum

249

Vol. 51 No. 2, July 2017

Development in Information Retrieval. New York: ACM,
324-.-331, 1998.
[4] W.J. Conover. Practical nonparametric statistics (2nd ed.).
New York: John Wiley & Sons, 1980.
[5] R. Green. The expression of conceptual syntagmatic relationships: A comparative survey. Journal of Documentation, 51(4): 315-338, 1995.
[6] W.R. Hersh & D.H. Hickam. An evaluation of interactive
Boolean and natural language searching with an online
medical textbook. Journal of the American Society for Information Science, 46(7): 478.--489, 1995.
[7] P. Ingwersen & P. Willett. An introduction to algorithmic
and cognitive approaches for information retrieval. Libri,
450: 160-177, 1995.
[8] E.M. Keen. The use of term position devices in ranked output experiments. Journal of Documentation, 47(1): 1-22,
1991.
[9] J. Kek~il~iinen. The effects of query complexity, expansion
and structure on retrieval performance in probabilistic text
retrieval. Ph.D. dissertation. Department of Information
Studies, University of Tampere, 1999.
[10] J. Kekalainen & K. Jarvelin. The co-effects of query structure and expansion on retrieval performance in probabilistic
text retrieval. Information Retrieval, 1(4): 329-344, 2000.
[ 11 ] J. Kek~l~inen & K. J~rvelin. The impact of query structureand query expansion on retrieval performance. In W.B.
Croft, A. Moffat, C.J. van Rijsbergen, R. Wilkinson & J.
Zobei (Eds.), Proceedings of the 21st Annual International
ACM SIGIR Conference on Research and Development inInformation Retrieval. New York: ACM, 130-137, 1998.
[12] R.M. Losee. Text retrieval and filtering: Analytic models
of performance. Kluwer Acadermc Publishers: Boston,
1998.
[13] T.B. Rajashekar & W.B. Croft. Combining automatic andmanual index representatzons m probabilist~c retrieval.
Journal of the American Society for Information Science,
46(4): 272-283, 1995.
[14] S.E. Robertson & N.J. Belkin. Ranking in principle. Journal of Documentation, 34(2): 93-100, 1978.
[15] T. Saracevic, P. Kantor, A. Chamis & D. Tnvison. A studyof information seeking and retrieving. I. Background andmethodology. Journal of the American Society for Information Science, 39(3): 161-176, 1988.
[16] S. Smithson. Information retrieval evaluation in practice:
A case study approach. Information Processing & Management, 30(2): 205-221, 1994.
[17] E. Sormunen. A Method for Measuring Wtde Range Performance of Boolean Queries in Full-Text Databases.
Ph.D. d~ssertation. Department of Information Studies,
University of Tampere, 2000.
[18] H.R. Turtle. Inference networks for document retrieval.
Ph.D. dissertation. Computer and information Science Department, University of Massachusetts, 1990.

48

ACM SIGIR Forum

250

Vol. 51 No. 2, July 2017