Cumulated gain-based evaluation of IR techniques.
Modern large retrieval environments tend to overwhelm their users by their large output. Since all documents are not of equal relevance to their users, highly relevant documents should be identified and ranked first for presentation. In order to develop IR techniques in this direction, it is necessary to develop evaluation approaches and methods that credit IR methods for their ability to retrieve highly relevant documents. This can be done by extending traditional evaluation methods, that is, recall and precision based on binary relevance judgments, to graded relevance judgments. Alternatively, novel measures based on graded relevance judgments may be developed. This article proposes several novel measures that compute the cumulative gain the user obtains by examining the retrieval result up to a given ranked position. The first one accumulates the relevance scores of retrieved documents along the ranked result list. The second one is similar but applies a discount factor to the relevance scores in order to devaluate late-retrieved documents. The third one computes the relative-to-the-ideal performance of IR techniques, based on the cumulative gain they are able to yield. These novel measures are defined and discussed and their use is demonstrated in a case study using TREC data: sample system run results for 20 queries in TREC-7. As a relevance base we used novel graded relevance judgments on a four-point scale. The test results indicate that the proposed measures credit IR methods for their ability to retrieve highly relevant documents and allow testing of statistical significance of effectiveness differences. The graphs based on the measures also provide insight into the performance IR techniques and allow interpretation, for example, from the user point of view.
2. CUMULATED GAIN -BASED MEASUREMENTS
2.1 Direct Cumulated Gain
When examining the ranked result list of a query, it is obvious that:
highly relevant documents are more valuable than marginally relevant documents,
and
the greater the ranked position of a relevant document, the less valuable it is for the
user, because the less likely it is that the user will ever examine the document.
The first point leads to comparison of IR techniques through test queries by their cumulated
gain by document rank. In this evaluation, the relevance score of each document is
somehow used as a gained value measure for its ranked position in the result and the gain
1 For a discussion of the degree of relevance and the probability of relevance, see Robertson and Belkin [1978].
is summed progressively from ranked position 1 to n. Thus the ranked document lists (of
some determined length) are turned to gained value lists by replacing document IDs by
their relevance scores. Assume that the relevance scores 0 - 3 are used (3 denoting high
value, 0 no value). Turning 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:
The cumulated gain at ranked position i is computed by summing 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 the vector CG where:
CG[i]=GCG[1[]i,1]+G[i],oifthie=rw1ise (1)
For example, from G' we obtain >. The cumulated
gain at any rank may be read directly, for example, at rank 7 it is 11.
2.2 Discounted Cumulated Gain
The second point above stated that the greater the ranked position of a relevant document,
the less valuable it is for the user, because the less likely it is that the user will ever examine
the document due to time, effort, and cumulated information from documents already
seen. This leads to comparison of IR techniques through test queries by their cumulated
gain based on document rank with a rank-based discount factor. The greater the rank, the
smaller share of the document score is added to the cumulated gain.
A discounting function is needed which progressively reduces the document score 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 score by the log of its rank. For example
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 behavior. Formally, if b denotes the base of the logarithm,
the cumulated gain vector with discount DCG is defined recursively as the vector DCG
where:
Note that we must not apply the logarithm-based discount at rank 1 because blog
Moreover, we do not apply the discount case for ranks less than the logarithm base (it
would give them a boost). This is also realistic, since the higher the base, the lower the
discount and the more likely the searcher is to examine the results at least up to the base
rank (say 10).
For example, let 2. From G' given in the preceding section we obtain
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 both the 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 a particular IR technique can be analyzed.
Averaged vectors have the same length as the individual ones and each component i gives
the average of the ith component in the individual vectors. The averaged vectors can directly
be visualized as gain-by-rank -graphs (Section 3).
To compute the averaged vectors, we need vector sum operation and vector multiplication
by a constant. Let be two vectors.
Their sum is the vector V+ wk>. For a set of vectors
{V1, V2, , Vn}, each of k components, the sum vector is generalised as
Vn. The multiplication of a vector by a constant r is the
vector r*vk>. The average vector AV based on vectors V= {V1,
V2, , Vn}, is given by the function avg-vect(V):
Now the average CG and DCG vectors for vector sets CG and DCG, over a set of test
queries, are computed by avg-vect(CG) and avg-vect(DCG).
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 1, 2 and 3 (respectively) for a given
request. First fill the vector positions 1  m by the values 3, then the positions m+1
m+l by the values 2, then the positions m+l+1  m+l +k by the values 1, and finally the
remaining positions by the values 0. More formally, the theoretically best possible score
vector BV for a request of k, l, and m relevant documents at the relevance levels 1, 2 and
3 is constructed as follows:
0, otherwise
A sample ideal gain vector could be:
The ideal CG and DCG vectors, as well as the average ideal CG and DCG vectors and
curves, are computed as above. Note that the curves turn horizontal when no more relevant
documents (of any level) can be found (Section 3 gives examples). They do not unrealistically
assume as a baseline that all retrieved documents could be maximally rele-
vant. The vertical distance between an actual (average) (D)CG curve and the theoretically
best possible (average) curve shows the effort wasted on less-than-perfect documents due
to a particular IR method. Based on the sample ideal gain vector I', we obtain the ideal
CG and DCG (b = 2) vectors:
Note that the ideal vector is based on the recall base of the search topic rather than on
the result of some IR technique. This is an important difference with respect to some related
measures, e.g. the sliding ratio and satisfaction measure [Korfhage 1997].
2.3. Relative to the Ideal Measure - the Normalized (D)CG-measure
Are two IR techniques significantly different in effectiveness from each other when
evaluated through (D)CG curves? In the case of P-R performance, we may use the average
of interpolated precision figures at standard points of operation, e.g., eleven recall
levels or DCV points, and then perform a statistical significance test. The practical significance
may be judged by the Sparck Jones [1974] criteria, for example, differences
less than 5% are marginal and differences over 10% are essential. P-R performance is
also relative to the ideal performance: 100% precision over all recall levels. The (D)CG
curves are not relative to an ideal. Therefore it is difficult to assess the magnitude of the
difference of two (D)CG curves and there is no obvious significance test for the difference
of two (or more) IR techniques either. One needs to be constructed.
The (D)CG vectors for each IR technique can be normalized by dividing them by the
corresponding ideal (D)CG vectors, component by component. In this way, for any vector
position, the normalized value 1 represents ideal performance, and values in the range [0,
1) the share of ideal performance cumulated by each technique. Given an (average)
(D)CG vector of an IR technique, and the (average) (D)CG vector I =
<i1, i2, , ik> of ideal performance, the normalized performance vector n(D)CG is obtained
by the function:
For example, based on CG' and CGI' from above, we obtain the normalized CG vector
The normalized DCG vector nDCG' is obtained in a similar way from DCG' and
DCGI'. Note that, as a special case, the normalized ideal (D)CG vector is always norm-
I is the ideal vector.
The area between the normalized ideal (D)CG vector and the normalized (D)CG vector
represents the quality of the IR technique. Normalized (D)CG vectors for two or more
techniques also have a normalized difference. These can be compared in the same way
as P-R curves for IR techniques. The average of a (D)CG vector (or its normalized varia-
tion), up to a given ranked position, summarizes the vector (or performance) and is analogous
to the non-interpolated average precision of a DCV curve up to the same given
ranked position. The average of a (n)(D)CG vector V up to the position k is given by:
These vector averages can be used in statistical significance tests in the same way as
average precision over standard points of operation, for example, eleven recall levels or
points.
2.4. Comparison to Earlier Measures
The novel measures have several advantages when compared with several previous and
related measures. The average search length (ASL) measure [Losee 1998] estimates the
average position of a relevant document in the retrieved list. The expected search length
(ESL) measure [Korfhage 1997; Cooper 1968] is the average number of documents that
must be examined to retrieve a given number of relevant documents. Both are dichotomi-
cal, they do not take the degree of document relevance into account. The former also is
heavily dependent on outliers (relevant documents found late in the ranked order).
The normalized recall measure (NR for short; Rocchio [1966] and Salton and McGill
[1983]), the sliding ratio measure (SR for short; Pollack [1968] and Korfhage [1997]),
and the satisfaction - frustration - total measure (SFT for short; Myaeng and Korfhage
[1990] and Korfhage [1997]) all seek to take into account the order in which documents
are presented to the user. The NR measure compares the actual performance of an IR
technique to the ideal one (when all relevant documents are retrieved first). Basically it
measures the area between the ideal and the actual curves. NR does not take the degree of
document relevance into account and is highly sensitive to the last relevant document
found late in the ranked order.
The SR measure takes the degree of document relevance into account and actually
computes the cumulated gain and normalizes this by the ideal cumulated gain for the
same retrieval result. The result thus is quite similar to our nCG vectors. However, SR is
heavily dependent on the retrieved list size: with a longer list the ideal cumulated gain
may change essentially and this affects all normalized SR ratios from rank one onwards.
Because our nCG is based on the recall base of the search topic, the first ranks of the ideal
vector are not affected at all by extension of the evaluation to further ranks. Improving on
normalized recall, SR is not dependent on outliers, but it is too sensitive to the actual retrieved
set size. SR does not have the discount feature of our (n)DCG measure.
The SFT measure consists of three components similar to the SR measure. The satisfaction
measure only considers the retrieved relevant documents, the frustration measure
only the irrelevant documents, and the total measure is a weighted combination of the
two. Like SR, also SFT assumes the same retrieved list of documents, which are obtained
in different orders by the IR techniques to be compared. This is an unrealistic assumption
for comparison since for any retrieved list size n, when n << N (the database size), different
techniques may retrieve quite different documents - that is the whole idea (!). A
strong feature of SFT comes from its capability of punishing an IR technique for retrieving
irrelevant documents while rewarding for the relevant ones. SFT does not have the
discount feature of our nDCG measure.
The relative relevance and ranked half life measures [Borlund and Ingwersen 1998;
Borlund 2000] were developed for interactive IR evaluation. The relative relevance (RR
for short) measure is based on comparing the match between the system-dependent probability
of relevance and the user-assessed degree of relevance, the latter by the real per-
son-in-need or a panel of assessors. The match is computed by the cosine coefficient
[Borlund 2000] when the same ranked IR technique output is considered as vectors of
relevance weights as estimated by the technique, by the user, or by the panel. RR is (in-
tended as) an association measure between types of relevance judgments, and is not directly
a performance measure. Of course, if the cosine between the IR technique scores
and the user relevance judgments is low, the technique cannot perform well from the user
point of view. The ranked order of documents is not taken into account.
The ranked half life (RHL for short) measure gives the median point of accumulated
relevance for a given query result. It thus improves on ASL by taking the degree of
document relevance into account. Like ASL, RHL is dependent on outliers. The RHL
may also be the same for quite differently performing queries. RHL does not have the
discount feature of DCG.
The strengths of the proposed CG, DCG, nCG and nDCG measures can now be
summarized as follows:
They combine the degree of relevance of documents and their rank (affected by their
probability of relevance) in a coherent way.
At any number of retrieved documents examined (rank), CG and DCG give an estimate
of the cumulated gain as a single measure no matter what is the recall base size.
They are not heavily dependent on outliers (relevant documents found late in the
ranked order) since they focus on the gain cumulated from the beginning of the result
up to any point of interest.
They are obvious to interpret, they are more direct than P-R curves by explicitly giving
the number of documents for which each n(D)CG value holds. P-R curves do not
make the number of documents explicit for given performance and may therefore
mask bad performance [Losee 1998].
In addition, the DCG measure has the following further advantages:
It realistically weights down the gain received through documents found later in the
ranked results.
It allows modeling user persistence in examining long ranked result lists by adjusting
the discounting factor.
Furthermore, the normalized nCG and nDCG measures support evaluation:
They represent performance as relative to the ideal based on a known (possibly
large) recall base of graded relevance judgments.
The performance differences between IR techniques are also normalized in relation
to the ideal thereby supporting the analysis of performance differences.
Jrvelin and Keklinen have earlier proposed recall and precision based evaluation
measures to work with graded relevance judgments [Jrvelin and Keklinen 2000;
Keklinen and Jrvelin 2002a]. They first propose the use of each relevance level separately
in recall and precision calculation. Thus different P-R curves are drawn for each
level. Performance differences at different relevance levels between IR techniques may
thus be analyzed. Furthermore, they generalize recall and precision calculation to directly
utilize graded document relevance scores. They consider precision as a function of recall
and demonstrate that the relative effectiveness of IR techniques, and the statistical significance
of their performance differences, may vary according to the relevance scales used.
The proposed measures are similar to standard IR measures while taking document relevance
scores into account. They do not have the discount feature of our (n)DCG measure.
The measures proposed in this article are directly user-oriented in calculating the gain
cumulated by consulting an explicit number of documents. P-R curves tend to hide this
information. The generalized P-R approach extends to DCV (Document Cut-off Value)
based recall and precision as well, however.
The limitations of the measures are considered in Chapter 4.
3. CASE STUDY: COMPARISON OF SOME TREC-7 RESULTS AT DIFFERENT
We demonstrate the use of the proposed measures in a case study testing runs from
TREC-7 ad hoc track with binary and non-binary relevance judgments. We give the results
as CG and DCG curves, which exploit the degrees of relevance. We further show
the results as normalized nCG and nDCG curves, and present the results of a statistical
test based on the averages of n(D)CG vectors.
3.1 TREC-7 Data
The seventh Text Retrieval Conference (TREC-7) had an ad hoc track in which the participants
produced queries from topic statements - altogether 50 - and run those queries
against the TREC text document collection. The collection includes about 528,000
documents, or 1.9 GB data. Participants returned lists of the best 1000 documents retrieved
for each topic. These lists were evaluated against binary relevance judgments
provided by the TREC organizers (National Institute of Standards and Technology,
NIST). Participants were allowed to submit up to three different runs, which could be
based on different queries or different retrieval methods. [Voorhees and Harman 1999.]
Ad hoc task had two subtracks, automatic and manual, with different query construction
techniques. An automatic technique means deriving a query from a topic statement
without manual intervention; manual technique is anything else. [Voorhees and Harman
1999.]
In the case study, we used result lists for 20 topics by five participants from TREC-7
ad hoc manual track. These topics were selected because of the availability of non-binary
relevance judgments for them (see Sormunen [2002]).2
3.2 Relevance Judgments
The non-binary relevance judgments were obtained by re-judging documents judged
relevant by NIST assessors and about 5 % of irrelevant documents for each topic. The
new judgments were made by six Master's students of Information Studies, all of them
fluent in English though not native speakers. The relevant and irrelevant documents were
pooled, and the judges did not know the number of documents previously judged relevant
or irrelevant in the pool. [Sormunen 2002.]
The assumption about relevance in the re-judgment process was topicality. This
agrees with the TREC judgments for the ad hoc track: documents are judged one by one;
general information with limitations given in the topic's narrative is searched, not details
in sense of question answering. New judgments were done on a four-point scale:
1. Irrelevant document. The document does not contain any information about the
topic.
2 The numbers of topics are: 351, 353, 355, 358, 360, 362, 364, 365, 372, 373, 377, 378, 384, 385, 387, 392, 393, 396, 399,
400. For details see http://trec.nist.gov/data/topics_eng/topics.351-400.gz.
2. Marginally relevant document. The document only points to the topic. It does not
contain more or other information than the topic statement.
3. Fairly relevant document. The document contains more information than the topic
statement but the presentation is not exhaustive. In case of multi-faceted topic, only
some of the sub-themes are covered.
4. Highly relevant document. The document discusses the themes of the topic exhaus-
tively. In case of multi-faceted topics, all or most sub-themes are covered.
Altogether 20 topics from TREC-7 and topics from TREC-8 were re-assessed. In

Table

1 the results of re-judgment are shown with respect to the original TREC judg-
ments. It is obvious that almost all originally irrelevant documents were also assessed
irrelevant in re-judgment (93.8 %). Of the TREC relevant documents 75 % were judged
relevant at some level, and 25 % irrelevant. This seems to indicate that the re-assessors
have been somewhat stricter than the original judges. The great overlap in irrelevant
documents proves the new judgments reliable. However, in the case study we are not interested
to compare the results based on different judgments but to show the effects of
utilizing non-binary relevance judgments in evaluation. Thus we do not use the original
TREC judgments in any phase of the case study.
Levels of
relevance
TREC relevant TREC irrelevant Total
# of
docs
# of
docs
# of
docs
691 25.0% 2780 93.8% 3471 60.5%
1004 36.2% 134 4.5% 1138 19.8%
Total 2772 100.0% 2965 100.0% 5737 100.0%

Table

1. Distribution of new relevance judgments with relation to original TREC judgments.
In the subset of 20 topics, among all relevant documents the share of
highly relevant documents was 20.1%, the share of fairly relevant documents was 30.5%,
and that of marginal documents was 49.4%.
3.3 The Application of the Evaluation Measures
We run the TREC-7 result lists of five participating groups against the new, graded relevance
judgments. For the cumulated gain evaluations we tested logarithm bases and handling
of relevance levels varied as parameters as follows.
1. We tested different relevance weights at different relevance levels. First, we replaced
document relevance levels 0, 1, 2, 3 with binary weights, i.e. we gave documents at
level 0 weight 0, and documents at levels 1-3 weight 1 (weighting scheme 0-1-1-1
for the four point scale). Then, we replaced the relevance levels with weights 0, 0, 0,
1, to test the other extreme where only the highly relevant documents are valued. The
last weighting scheme, 0, 1, 10, 100, is between the extremes; the highly relevant
documents are valued hundred times more than marginally relevant documents, and
ten times more than fairly relevant ones. Different weighting on highly relevant
documents may affect the relative effectiveness of IR techniques as also pointed out
by Voorhees [2001]. The first and last weighting schemes only are shown in graphs
because the 0-0-0-1 scheme is very similar to the last one in appearance.
2. The logarithm bases 2 and 10 were tested for the DCG vectors. The base 2 models
impatient users, base 10 persistent ones. While the differences in results do not vary
markedly with the logarithm base, we show only the results for the logarithm base 2.
We also prefer the stricter test condition the smaller logarithm base provides.
3. The average actual CG and DCG vectors were compared to the ideal average vectors

4. The average actual CG and DCG vectors were normalized by dividing them with the
ideal average vectors.
3.4 Cumulated Gain

Figures

1(a) and 1(b) present the CG vector curves for the five runs at ranks 1 - 100, and
the ideal curves. Figure 1a shows the weighting scheme 0-1-1-1, and 1b the scheme 0-1-
10-100. In the ranked result list, highly relevant documents add either 1 or 100 points to
the cumulated gain; fairly relevant documents add either 1 or 10 points; marginally relevant
documents add 1 point; and irrelevant documents add 0 points to the gain.
a. 0-1-1-150CG200
A
IDEAL
Rank

Figure

1(a). Cumulated gain (CG) curves, binary weighting.
b. 0-1-10-10014001000
CG600200A
IDEAL
Rank

Figure

1(b). Cumulated gain (CG) curves, non-binary weighting.
The different weighting schemes change the position of the curves compared to each
other. For example, in Figure 1(a) - the binary weighting scheme - the performance of
(run) D is close to that of C; when highly relevant documents are given more weight, D is
more similar to B, and C and E are close in performance. Note, that the graphs have different
scales because of the weighting schemes.
In

Figure

1(a) the best possible curve starts to level off at the rank 100 reflecting the
fact that at the rank 100 practically all relevant documents have been found. In Figure
1(b) it can be observed, that the ideal curve has already found the most fairly and highly
relevant documents by the rank 50. This, of course, reflects the sizes of the recall bases -
average number of documents at relevance levels 2 and 3 per topic is 29.9. The best system
hangs below the ideal by 0 - 39 points with binary weights (1(a)), and 70 - 894
points with non-binary weights (1(b)). Note that the differences are not greatest at rank
100 but often earlier. The other runs remain further below by 0 - 6 points with binary
weights (1(a)), and 0 - 197 points with non-binary weights (1(b)). The differences between
the ideal and all actual curves are all bound to diminish when the ideal curve levels
off.
The curves can also be interpreted in another way: In Figure 1(a) one has to retrieve
documents by the best run, and 90 by the worst run in order to gain the benefit that
could theoretically be gained by retrieving only 10 documents (the ideal curve). In this
respect the best run is three times as effective as worst run. In Figure 1(b) one has to retrieve
documents by the best run to get the benefit theoretically obtainable at rank 5;
the worst run does not provide the same benefit even at rank 100.
Discounted cumulated gain

Figures

2(a) and 2(b) show the DCG vector curves for the five runs at ranks 1 - 100, and
the ideal curve. The log2 of the document rank is used as the discounting factor. Discounting
alone seems to narrow the differences between the systems (1(a) compared to
2(a), and 1(b) to 2(b)). Discounting and non-binary weighting changes the performance
order of the systems: in Figure 2(b), run A seems to lose and run C to benefit.
In

Figure

2(a), the ideal curve levels off upon the rank 100. The best run hangs below
by points. The other runs remain further below by 0.25 - 1 points. Thus, with discounting
factor and binary weighting, the runs seem to perform equally. In Figure 2(b),
the ideal curve levels off upon the rank 50. The best run hangs below by 71 - 408 points.
The other runs remain further below by 13 - 40 points. All the actual curves still grow at
the rank 100, but beyond that the differences between the best possible and the other
curves gradually become stable.
a. 0-1-1-11410
IDEAL
Rank

Figure

2(a). Discounted cumulated gain (DCG) curves, binary weighting.
b. 0-1-10-100500DCG2000
A
IDEAL
Rank

Figure

2(b). Discounted cumulated gain (DCG) curves, non-binary weighting.
These graphs can also be interpreted in another way: In Figure 2(a) one has to expect
the user to examine 40 documents by the best run in order to gain the (discounted) benefit
that could theoretically be gained by retrieving only 5 documents. The worst run reaches
that gain round rank 95. In Figure 2b, none of the runs gives the gain that would theoretically
7be obtainable at rank 5. Given the worst run the user has to examine 50 documents
in order to get the (discounted) benefit that is obtained with the best run at rank 10. In that
respect the difference in the effectiveness of runs is essential.
One might argue that if the user goes down to, say, 50 documents, she gets the real
value, not the discounted one and therefore the DCG data should not be used for effectiveness
comparison. Although this may hold for the user situation, the DCG-based comparison
is valuable for the system designer. The user is less and less likely to scan further
and thus documents placed there do not have their real relevance value, a retrieval technique
placing relevant documents later in the ranked results should not be credited as
much as another technique ranking them earlier.
3.6 Normalized (D)CG Vectors and Statistical Testing

Figures

3(a) and 3(b) show the curves for CG vectors normalized by the ideal vectors.
The curve for the normalized ideal CG vector has value 1 at all ranks. The actual normalized
CG vectors reach it in due course when all relevant documents have been found.
Differences at early ranks are easier to observe than in Figure 1. The nCG curves readily
show the differences between methods to be compared because of the same scale but they
lack the straightforward interpretation of the gain at each rank given by CG curves. In

Figure

3(b) the curves start lower than in Figure 3(a); it is obvious that highly relevant
documents are more difficult to retrieve.
a. 0-1-1-1
0,6
0,4
0,3
0,1A
Rank

Figure

3(a). Normalized cumulated gain (nCG) curves, binary weighting.
0,6
0,4
0,3
0,1A
Rank

Figure

3(b). Normalized cumulated gain (nCG) curves, non-binary weighting.

Figures

4(a) and 4(b) display the normalized curves for DCG vectors. The curve for
the normalized ideal DCG vector has value 1 at all ranks. The actual normalized DCG
vectors never reach it, they start to level off upon the rank 100. The effect of discounting
can be seen by comparing Figures 3 and 4, e.g. the order of the runs changes. The effect
of normalization can be detected by comparing Figure 2 and Figure 4: the differences
between the IR techniques are easier to detect and comparable.
a. 0-1-1-1
0,6
0,4
0,3
0,1A
Rank

Figure

4(a). Normalized discounted cumulated gain (nDCG) curves, binary weighting.
0,6
0,4
0,3
0,1A
Rank

Figure

4(b). Normalized discounted cumulated gain (nDCG) curves, non-binary weighting.
nDCG (0-0-0-1) Statistical testing of differences between query types was based on normalized average
n(D)CG vectors. These vector averages can be used in statistical significance tests in
the same way as average precision over document cut-off values. The classification we
used to label the relevance levels through numbers 0 - 3 is on an ordinal scale. Holding to
the ordinal scale suggests non-parametric statistical tests, such as the Friedman test (see
Conover [1980]). However, we have based our calculations on class weights to represent
their relative differences. The weights 0, 1, 10 and 100 denote differences on a ratio scale.
This suggests the use of parametric tests such as ANOVA provided that its assumptions
on sampling and measurement distributions are met. Next we give the grand averages of
the vectors of length 200, and the results of the Friedman test; ANOVA did not prove any
differences significant.

Table

2. n(D)CG averages over topics and statistical significance the results for five TREC-7 runs (legend:
Friedman test).
In

Table

2, the average is first calculated for each topic, then an average is taken over
the topics. If the average would have been taken of vectors of different length, the results
of the statistical tests might have changed. Also, the number of topics (20) is rather small
to provide reliable results. However, even these data illuminate the behavior of the
(n)(D)CG measures.
4. DISCUSSION
The proposed measures are based on several parameters: the last rank considered, the
gain values to employ, and discounting factors to apply. An experimenter needs to know
which parameter values and combinations to use. In practice, the evaluation context and
scenario should suggest these values. Alternatively, several values and/or combinations
may be used to obtain a richer picture on IR system effectiveness under different condi-
tions. Below we consider the effects of the parameters. Thereafter we discuss statistical
testing, relevance judgments and limitations of the measures.
Last Rank Considered
Gain vectors of various length from 1 to n may be used for computing the proposed
measures and curves. If one analyzes the curves alone, the last rank does not matter.
Eventual differences between the IR methods are observable for any rank region. The
gain difference for any point (or region) of the curves may be measured directly.
If one is interested in differences in average gain up to a given last rank, then the last
rank matters, particularly for nCG measurements. Suppose IR method A is somewhat
better than the method B in early ranks (say, down to rank 10) but beyond them the methods
starts catching up so that they are en par at rank 50 with all relevant documents
found. If one now evaluates the methods by nCG, they might be statistically significantly
different for the ranks 1 - 10, but there probably would be no significant difference for
the ranks 1 - 100 (or down to lower positions).
If one uses nDCG in the previous case the difference earned by the method A would
be preserved due to discounting low ranked relevant documents. In this case the difference
between the methods may be statistically significant also for the ranks 1 - 100 (or
down to lower positions).
The measures themselves cannot tell how they should be applied - down to which
rank? This depends on the evaluation scenario and the sizes of recall bases. It makes
sense to produce the n(D)CG curves liberally, i.e., down to quite low ranks. The significance
of differences between IR methods, when present, can be tested for selected regions
(top n) when justified by the scenario. Also our test data demonstrate that one run may be
significantly better than another, if just top ranks are considered, while being similarly
effective as another, if low ranks are included also (say up to 100; see e.g. runs C and D
in

Figure

3).
Gain Values
Justifying different gain values for documents relevant to different degrees is inherently
quite arbitrary. It is often easy to say that one document is more relevant than another, but
the quantification of this difference still remains arbitrary. However, determining such
documents as equally relevant is another arbitrary decision, and less justified in the light
of the evidence from relevance studies [Tang, Shaw and Vevea 1999; Sormunen 2002].
Since graded relevance judgments can be provided reliably, the sensitivity of the
evaluation results to different gain quantifications can easily be tested. Sensitivity testing
is also typical in cost-benefit studies, so this is no new idea. Even if the evaluation scenario
would not advice us on the gain quantifications, evaluation through several flat to
steep quantifications informs us on the relative performance of IR methods better than a
single one. Voorhees [2001] used this approach in the TREC Web Track evaluation, when
she weighted highly relevant documents by factors 1-1000 in relation to marginal docu-
ments. Varying weighting affected relative effectiveness order of IR systems in her test.
Our present illustrative findings based on TREC data also show that weighting affects the
relative effectiveness order of IR systems. We can observe in Figures 4(a) and (b) (Sec-
tion 3.6) that by changing from weighting 0-1-1-1, that is, flat TREC-type weights, to
weights 0-1-10-100 for the irrelevant to highly relevant documents, run D appears more
effective than the others.
Tang, Shaw and Vevea [1999] proposed seven as the optimal number of relevance
levels in relevance judgments. Although our findings are for four levels the proposed
measures are not tightly coupled with any particular number of levels.
Discounting Factor
The choice between (n)CG and (n)DCG measures in evaluation is essential: discounting
the gain of documents retrieved late affects the order of effectiveness of runs as we saw in
Sections 3.4. and 3.5 (Figures 1(b) and 2(b)). It is however again somewhat arbitrary to
apply any specific form of discounting. Consider the discounting case of the DCG function

where df is the discounting factor and i the current ranked position. There are three cases
of interest:
If no discounting is performed - all documents, at whatever
rank retrieved, retain their relevance score.
If we have a very sharp discount - only the first documents would really
matter, which hardly is desirable and realistic for evaluation.
If then we have a smooth discounting factor, the smoothness of which can
be adjusted by the choice of the base b. A relatively small base (b = 2) models an
impatient searcher for whom the value of late documents drops rapidly. A relatively
high base (b > 10) models a patient searcher for whom even late documents are valu-
able. A very high base (b >100) yields a very marginal discount from the practical IR
evaluation point of view.
We propose the use of the logarithmic discounting factor. However, the choice of the
base is again somewhat arbitrary. Either the evaluation scenario should advice the evaluator
on the base or a range of bases could be tried out. Note that in the DCG function case
the choice of the base would not affect the order of
effectiveness of IR methods because blog any pair of bases a and b
since blog a is a constant. This is the reason for applying the discounting case for DCG
only after the rank indicated by the logarithm base. This is also the point where discounting
begins because blog 1. In the rank region 2 to b discounting would be replaced by
boosting.
There are two borderline cases for the logarithm base. When the base b (b  1) approaches
discounting becomes very aggressive and finally only the first document
would matter - hardly realistic. On the other hand, if b approaches infinity, then DCG
approaches CG - neither realistic. We believe that the base range 2 to 10 serves most
evaluation scenarios well.
Practical Methodological Problems
The discussion above leaves open the proper parameter combinations to use in evalua-
tion. This is unfortunate but also unavoidable. The mathematics work for whatever parameter
combinations and cannot advice us on which to choose. Such advice must come
from the evaluation context in the form of realistic evaluation scenarios. In research campaigns
such as TREC, the scenario(s) should be selected.
If one is evaluating IR methods for very busy users who are only willing to examine a
few best answers for their queries, it makes sense to evaluate down to shallow ranks only
(say, 30), use fairly sharp gain quantifications (say, 0-1-10-100) and a low base for the
discounting factor (say, 2). On the other hand, if one is evaluating IR methods for patient
users who are willing to dig down in the low ranked and marginal answers for their que-
ries, it makes sense to evaluate down to deep ranks (say, 200), use moderate gain quantifications
(say, 0-1-2-3) and a high base for the discounting factor (say, 10). It makes
sense to try out both scenarios in order to see whether some IR methods are superior in
one scenario only.
When such scenarios are argued out, they can be critically assessed and defended for
the choices involved. If this is not done, an arbitrary choice is committed, perhaps uncon-
sciously. For example, precision averages over 11 recall points with binary relevance
gains models well only very patient users willing to dig deep down the low ranked an-
swers, no matter how relevant vs. marginal the answers are. Clearly this is not the only
scenario one should look at.
The normalized measures nCG and nDCG we propose are normalized by the best possible
behavior for each query on a rank-by-rank basis. Therefore the averages of the normalized
vectors are also less prone to the problems of recall base size variation which
plague the precision-recall measurements, whether they are based on DCVs or precision
as function of recall.
The cumulated gain curves illustrate the value the user actually gets, but discounted
cumulative gain curves can be used to forecast the system performance with regard to a
user's patience in examining the result list. For example, if the CG and DCG curves are
analyzed horizontally in the case study, we may conclude that a system designer would
have to expect the users to examine by 100 to 500 % 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 a system requiring such a behavior is, in practice, much worse
than a system yielding the gain within a 50 % of the documents.
Relevance Judgments
Keklinen and Jrvelin [2002a] argue on the basis of several theoretical, laboratory and
field studies that the degree of document relevance varies and document users can distinguish
between them. Some documents are far more relevant than others are. Furthermore,
in many studies on information seeking and retrieval, multiple degree relevance scales
have been found pertinent, while the number of degrees employed varies. It is difficult to
determine, how many degrees there should be, in general. This depends on the study setting
and the user scenarios. When multiple degree approaches are justified, evaluation
methods should utilize / support them.
TREC has been based on binary relevance judgments with a very low threshold for
accepting a document as relevant for a topical request - the document needs to have at
least one sentence pertaining to the request to count as relevant [TREC 2001]. This is a
very special evaluation scenario and there are obvious alternatives. In many scenarios, at
that level of contribution one would count the document at most as marginal unless the
request is factual - in which case a short factual response should be regarded highly relevant
and another not giving the facts marginal if not irrelevant. This is completely compatible
with the proposed measures. If the share of marginal documents were high in the
test collection, then by utilizing TREC-like liberal binary relevance judgments would lead
to difficulties in identifying the better techniques as such. In our data sample, about 50%
of the relevant documents were marginally relevant. Possible differences between IR
techniques in retrieving highly relevant documents might be evened up by their possible
indifference in retrieving marginal documents. The net differences might seem practically
marginal and statistically insignificant.
Statistical Testing
Holding to the ordinal scale of relevance judgments suggests non-parametric statistical
tests, such as the Wilcoxon test or the Friedman test. However, when weights are used,
the scale of measurement becomes one of interval or ratio scale. This suggests the use of
parametric tests such as ANOVA or t-test provided that their assumptions on sampling
and measurement distributions are met. For example, Zobel [1998] used parametric tests
when analyzing the reliability of IR experiment results. Also Hull [1993] argues that with
sufficient data parametric tests may be used. In our test case ANOVA gave a result different
from Friedman - an effect of the magnitude of the differences between the IR runs
considered. However, the data set used in the demonstration was fairly small.
Empirical Findings Based on the Proposed Measures
The DCG measure has been applied in the TREC Web Track 2001 [Voorhees 2001] and
in a text summarization experiment by Sakai and Sparck Jones [2001]. Voorhees' findings
are based on a three-point relevance scale. She examined the effect of incorporating
highly relevant documents (HRDs) into IR system evaluation and weighting them more
or less sharply in a DCG-based evaluation. She found out that the relative effectiveness
of IR systems is affected when evaluated by HRDs. Voorhees pointed out that moderately
sharp weighting of HRDs in DCG measurement supports evaluation for HRDs but avoids
problems caused by instability due to small recall bases of HRDs in test collections. Sakai
and Sparck Jones first assigned the weight 2 to each highly relevant document, and
the weight 1 to each partially relevant document. They also experimented with other
valuations, e.g., zero for the partially relevant documents. Sakai and Sparck Jones used
log base 2 as the discounting factor to model user's (lack of) persistence. The DCG
measure served to test the hypotheses in the summarization study. Our present demonstrative
findings based on TREC-7 data also show that weighting affects the relative effectiveness
order of IR systems. These results exemplify the usability of the cumulated
gain-based approach to IR evaluation.
Limitations
The measures considered in this paper, both the old and the new ones, have weaknesses
in three areas. Firstly, none of them take into account order effects on relevance judg-
ments, or document overlap (or redundancy). In the TREC interactive track [Over 1999],
instance recall is employed to handle this. The user-system pairs are rewarded for retrieving
distinct instances of answers rather than multiple overlapping documents. In princi-
ple, the n(D)CG measures may be used for such evaluation. Secondly, the measures considered
in Section 2.4 all deal with relevance as a single dimension while it really is multidimensional
[Vakkari and Hakala 2000]. In principle, such multidimensionality may be
accounted for in the construction of recall bases for search topics but leads to complexity
in the recall bases and in the evaluation measures. Nevertheless, such added complexity
may be worth pursuing because so much effort is invested in IR evaluation.
Thirdly, any measure based on static relevance judgments is unable to handle dynamic
changes in real relevance judgments. However, when changes in user's relevance criteria
lead to a reformulated query, an IR system should retrieve the best documents for the re-formulated
query. Keklinen and Jrvelin [2002b] argue that complex dynamic interaction
is a sequence of simple topical interactions and thus good one-shot performance by a
retrieval system should be rewarded in evaluation. Changes in the user's information need
and relevance criteria affect consequent requests and queries. While this is likely happen,
it has not been shown that this should affect the design of the retrieval techniques. Neither
has it been shown that this would invalidate the proposed or the traditional evaluation
measures.
It may be argued that IR systems should not rank just highly relevant documents to
top ranks. Consequently, they should not be rewarded in evaluation for doing so. Spink,
Greisdorf and Bateman [1998] have argued that partially relevant documents are important
for users at the early stages of their information seeking process. Therefore one might
require that IR systems be rewarded for retrieving partially relevant documents in the top
ranks.
For about 40 years IR systems have been compared on the basis of their ability to provide
relevant - or useful - documents for their users. To us it seems plausible, that highly
relevant documents are those people find useful. The findings by Spink, Greisdorf and
Bateman do not really disqualify this belief, they rather state that students in the early
states of their information seeking tend to change their relevance criteria and problem
definition and that the number of partially relevant documents correlate with these
changes.
However, if it should turn out that for some purposes, IR systems should rank partially
relevant documents higher than, say, highly relevant documents, our measures suit perfectly
comparisons on such basis: the documents should just be weighted accordingly. We
do not intend to say how or on what criteria the relevance judgments should be made, we
only propose measures that take into account differences in relevance.
The limitations of the proposed measures being similar to those of traditional meas-
ures, the proposed measures offer benefits taking the degree of document relevance into
account and modeling user persistence.
5. CONCLUSIONS
We have argued that in modern large database environments, the development and
evaluation of IR methods should be based on their ability to retrieve highly relevant
documents. This is often desirable from the user viewpoint and presents a not too liberal
test for IR techniques.
We then developed novel methods for IR technique evaluation, which aim at taking
the document relevance degrees into account. These are the CG and the DCG measures,
which give the (discounted) cumulated gain up to any given document rank in the retrieval
results, and their normalized variants nCG and nDCG, based on the ideal retrieval
performance. They are related to some traditional measures like average search length
(ASL; Losee [1998]), expected search length (ESL; Cooper [1968]), normalized recall
(NR; Rocchio [1966] and Salton and McGill [1983]), sliding ratio (SR; Pollack [1968]
and Korfhage [1997]), and satisfaction - frustration - total measure (SFT; Myaeng and
Korfhage [1990]), and ranked half-life (RHL; Borlund and Ingwersen[1998]).
The benefits of the proposed novel measures are many: They systematically combine
document rank and degree of relevance. At any number of retrieved documents examined
(rank), CG and DCG give an estimate of the cumulated gain as a single measure no matter
what is the recall base size. Performance is determined on the basis of recall bases for
search topics and thus does not vary in an uncontrollable way, which is true of measures
based on the retrieved lists only. The novel measures are not heavily dependent on outliers
since they focus on the gain cumulated from the beginning of the result up to any
point of interest. They are obvious to interpret, and do not mask bad performance. They
are directly user-oriented in calculating the gain cumulated by consulting an explicit
number of documents. P-R curves tend to hide this information. In addition, the DCG
measure realistically down weights the gain received through documents found later in
the ranked results and allows modeling user persistence in examining long ranked result
lists by adjusting the discounting factor. Furthermore, the normalized nCG and nDCG
measures support evaluation by representing performance as relative to the ideal based on
a known (possibly large) recall base of graded relevance judgments. The performance
differences between IR techniques are also normalized in relation to the ideal thereby
supporting the analysis of performance differences.
An essential feature of the proposed measures is the weighting of documents at different
levels of relevance. What is the value of a highly relevant document compared to the
value of fairly and marginally relevant documents? There can be no absolute value because
this is a subjective matter that also depends on the information seeking situation. It
may be difficult to justify any particular weighting scheme. If the evaluation scenario
does not suggest otherwise, several weight values may be used to obtain a richer picture
on IR system effectiveness under different conditions. Regarding all at least somewhat
relevant documents as equally relevant is also an arbitrary (albeit traditional) decision,
and also counter-intuitive.
It may be argued that IR systems should not rank just highly relevant documents to
top ranks. One might require that IR systems be rewarded for retrieving partially relevant
documents in the top ranks. However, our measures suit perfectly comparisons on such
basis: the documents should just be weighted accordingly. The traditional measures do
not allow this.
The CG and DCG measures complement P-R based measures [Jrvelin and
Keklinen 2000; Keklinen and Jrvelin 2002a]. Precision over fixed recall levels hides
the user's effort up to a given recall level. The DCV-based precision - recall graphs are
better but still do not make the value gained by ranked position explicit. The CG and
DCG graphs provide this directly. The distance to the theoretically best possible curve
shows the effort wasted on less-than-perfect or useless documents. The normalized CG
and DCG graphs show explicitly the share of ideal performance given by an IR technique
and make statistical comparisons possible. The advantage of the P-R based measures is
that they treat requests with different number of relevant documents equally, and from the
system's point of view the precision at each 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 is nothing
to be gained by retrieving or examining further documents.
Generally, the proposed evaluation measures and the case further demonstrate that
graded relevance judgments are applicable in IR experiments. The dichotomous and liberal
relevance judgments generally applied may be too permissive, and, consequently, too
easily give credit to IR system performance. We believe that, in modern large environ-
9ments, the proposed novel measures should be used whenever possible, because they provide
richer information for evaluation.

ACKNOWLEDGEMENTS

We thank the FIRE group at University of Tampere for helpful comments, and the IR Lab
for programming.


--R

An evaluation of retrieval effectiveness for a full-text document-retrieval system
Evaluation of Interactive Information Retrieval Systems.
Measures of relative relevance and ranked half-life: Performance indicators for interactive IR
WILKINSON AND
Practical Nonparametric Statistics (2nd
Expected search length: A single measure of retrieval effectiveness based on weak ordering action of retrieval systems.
An evaluation of interactive Boolean and natural language searching with an online medical textbook.
Using statistical testing in the evaluation of retrieval experiments.




Journal of the American Society for Information Science and Technology 53

Libraries Unlimited: Greenwood Village
Information storage and retrieval.
Text retrieval and filtering: Analytic models of performance.
Integration of user profiles: Models and experiments in information retrieval.
Measures for the comparison of information retrieval systems.

Ranking in principle.
Document retrieval systems - Optimization and evaluation

Introduction to modern information retrieval.

A Method for Measuring Wide Range Performance of Boolean Queries in Full-Text Databases [On-line]
Extensions to the STAIRS Study - Empirical Evidence for the Hypothesised Ineffectiveness of Boolean Queries in Large Full-Text Databases
Liberal relevance criteria of TREC - Counting on negligible documents? <Proceedings>In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval</Proceedings>
Automatic indexing.
From highly relevant to non relevant: examining different regions of relevance.

Changes in relevance criteria and problem stages in task performance.
Evaluation by highly relevant documents.

Overview of the Seventh Text REtrieval Conference (TREC-7) [On-line]
How reliable are the results of large-scale information retrieval experiments? <Proceedings>In Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Re- trieval</Proceedings>
revised July
--TR
An evaluation of retrieval effectiveness for a full-text document-retrieval system
Integration of user profiles: models and experiments in information retrieval
Using statistical testing in the evaluation of retrieval experiments
An evaluation of interactive Boolean and natural language searching with an online medical textbook
Information storage and retrieval
The impact of query structure and query expansion on retrieval performance
How reliable are the results of large-scale information retrieval experiments?
Measures of relative relevance and ranked half-life
Text retrieval and filtering
Towards the identification of the optimal number of relevance categories
From highly relevant to not relevant
evaluation methods for retrieving highly relevant documents
Evaluation by highly relevant documents
Generic summaries for indexing in information retrieval
Liberal relevance criteria of TREC -
Introduction to Modern Information Retrieval
The Co-Effects of Query Structure and Expansion on Retrieval Performance in Probabilistic Text Retrieval
Extensions to the STAIRS StudyMYAMPERSANDmdash;Empirical Evidence for the Hypothesised Ineffectiveness of Boolean Queries in Large Full-Text Databases
Using graded relevance assessments in IR evaluation

--CTR
Mounia Lalmas , Gabriella Kazai, Report on the ad-hoc track of the INEX 2005 workshop, ACM SIGIR Forum, v.40 n.1, June 2006
Paul Ogilvie , Mounia Lalmas, Investigating the exhaustivity dimension in content-oriented XML element retrieval evaluation, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Mette Skov , Birger Larsen , Peter Ingwersen, Inter and intra-document contexts applied in polyrepresentation, Proceedings of the 1st international conference on Information interaction in context, October 18-20, 2006, Copenhagen, Denmark
Tetsuya Sakai, On the reliability of factoid question answering evaluation, ACM Transactions on Asian Language Information Processing (TALIP), v.6 n.1, p.3-es, April 2007
Crestan , Claude de Loupy, Natural language processing for browse help, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Tetsuya Sakai, Evaluating evaluation metrics based on the bootstrap, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Crestan , Claude de Loupy, Browsing help for faster document retrieval, Proceedings of the 20th international conference on Computational Linguistics, p.576-es, August 23-27, 2004, Geneva, Switzerland
Tetsuya Sakai, On the reliability of information retrieval metrics based on graded relevance, Information Processing and Management: an International Journal, v.43 n.2, p.531-548, March 2007
Egidio Terra , Robert Warren, Poison pills: harmful relevant documents in feedback, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Gabriella Kazai , Mounia Lalmas , Arjen P. de Vries, The overlap problem in content-oriented XML retrieval evaluation, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Robert M. Losee, Percent perfect performance (PPP), Information Processing and Management: an International Journal, v.43 n.4, p.1020-1029, July, 2007
Charles L. A. Clarke, Controlling overlap in content-oriented XML retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
Mounia Lalmas , Anastasios Tombros, Evaluating XML retrieval effectiveness at INEX, ACM SIGIR Forum, v.41 n.1, p.40-57, June 2007
Jaana Keklinen, Binary and graded relevance in IR evaluations: comparison of the effects on ranking of IR systems, Information Processing and Management: an International Journal, v.41 n.5, p.1019-1033, September 2005
Per Ahlgren , Jaana Keklinen, Indexing strategies for Swedish full text retrieval under different user scenarios, Information Processing and Management: an International Journal, v.43 n.1, p.81-102, January 2007
Jorge R. Herskovic , M. Sriram Iyengar , Elmer V. Bernstam, Using hit curves to compare search algorithm performance, Journal of Biomedical Informatics, v.40 n.2, p.93-99, April, 2007
Yu-Ting Liu , Tie-Yan Liu , Tao Qin , Zhi-Ming Ma , Hang Li, Supervised rank aggregation, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Thanh Tin Tang , Nick Craswell , David Hawking , Kathy Griffiths , Helen Christensen, Quality and relevance of domain-specific search: A case study in mental health, Information Retrieval, v.9 n.2, p.207-225, March     2006
Ryen W. White, Using searcher simulations to redesign a polyrepresentative implicit feedback interface, Information Processing and Management: an International Journal, v.42 n.5, p.1185-1202, September 2006
Hongyuan Zha , Zhaohui Zheng , Haoying Fu , Gordon Sun, Incorporating query difference for learning retrieval functions in world wide web search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Vincenzo Della Mea , Stefano Mizzaro, Measuring retrieval effectiveness: a new proposal and a first experimental validation, Journal of the American Society for Information Science and Technology, v.55 n.6, p.530-543, April 2004
Gabriella Kazai , Mounia Lalmas, eXtended cumulated gain measures for the evaluation of content-oriented XML retrieval, ACM Transactions on Information Systems (TOIS), v.24 n.4, p.503-542, October 2006
cumulated gain;graded relevance judgments