IR evaluation methods for retrieving highly relevant documents

Kalervo JärvelinJaana Kekäläinen

article2000SIGIR1,441 citationsTest of Time Award

Introduces discounted cumulative gain (DCG) and cumulative gain metrics to evaluate information retrieval systems using graded, non-binary relevance judgments based on how effectively they prioritize highly relevant documents for users.

Listen

In modern text database environments, standard search evaluation methods rely heavily on binary relevance judgments, categorizing retrieved documents simply as either relevant or irrelevant. This traditional approach treats marginally relevant items the same as highly relevant ones, masking crucial differences between weak and high-performing retrieval methods and failing to reflect real-world user behavior where searchers prioritize high-value information at the top of ranked results.

The article establishes new evaluation methodologies that account for multiple degrees of document relevance and demonstrates their practical utility in measuring how query structuring and expansion affect search performance.

To address this challenge, the authors introduced two primary evaluation techniques: precision-recall curves computed across separate recall bases for distinct relevance levels, and two novel metrics termed Cumulative Gain (CG) and Discounted Cumulative Gain (DCG). The CG metric tracks the total accumulated relevance score a user gains as they scan down a ranked list, while DCG applies a logarithmic discount factor to penalize relevant items that appear deeper in the rankings. These metrics were validated using an empirical case study on a newspaper database of 53,893 articles and 30 test requests, evaluated across four relevance grades (irrelevant, marginal, fair, and highly relevant) under the InQuery retrieval system to compare basic unstructured queries against strongly structured queries combining synonyms and facets with query expansion.

The investigation yielded four key findings regarding search effectiveness and evaluation. First, performance differences among query types are negligible for marginally relevant documents but become pronounced and statistically significant for highly relevant documents. Second, strongly structured queries utilizing facet grouping and expanded terms achieved the highest effectiveness, improving average precision for highly relevant documents by 58.3% over unstructured baselines (rising from 25.9% to 41.0%). Third, query expansion actively degraded performance in unstructured queries while consistently enhancing structured ones. Fourth, cumulative gain analysis revealed that to achieve the same gain delivered by the best methods, less effective retrieval methods require users to inspect 50% to 100% more documents (such as reviewing 62 to 70 documents instead of 34 to 35).

These findings demonstrate that conventional binary evaluations are overly permissive and hide critical system flaws. For organizational decision-makers and system designers, implementing structured query processing and evaluating systems via graded relevance directly reduces user effort and search abandonment risk. Highly relevant documents are placed where users will actually see them, improving overall productivity and information retrieval quality.

Organizations developing or procuring search engines should adopt graded relevance assessments and DCG-based metrics as standard evaluation benchmarks instead of relying solely on binary precision and recall. System developers should also implement strong query structuring mechanisms, such as facet- and concept-based operators, whenever deploying automated query expansion to avoid retrieval degradation.

The results carry high confidence given their statistical significance across multiple relevance levels and judges. However, readers should note that the evaluation was conducted on a single text collection of Finnish newspaper articles using the InQuery search engine, and human relevance values were assigned linear scores (0 to 3) which may conservatively underestimate how much real users value top-tier documents over marginal ones.

University of Tampere relevance judgment text document IR evaluation methods document relevance non-dichotomous relevance

Järvelin et al (2000).pdf

Paper: Term-weighting approaches in automatic text retrieval, Gerard Salton et al. (1988). Establishes foundational term-weighting and vector space retrieval evaluation techniques that standard IR benchmarks and the source paper's baseline retrieval comparisons build upon.
Paper: Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval, Stephen Robertson et al. (1994). Introduces classic probabilistic term weighting formulas and BM-series retrieval models used in ranked retrieval systems evaluated throughout IR research.
Paper: Indexing By Latent Semantic Analysis, Scott Deerwester et al. (1990). Introduces standard IR test collections and precision-recall curve evaluation methodologies that the source paper seeks to generalize to graded relevance.

Paper: Cumulated gain-based evaluation of IR techniques, Kalervo Järvelin et al. (2002). Formally expands the source paper's initial proposal of cumulated gain into the widely adopted Discounted Cumulated Gain (DCG) and Normalized DCG (nDCG) metrics.
Paper: Learning to rank using gradient descent, Chris Burges et al. (2005). Employs the multi-graded relevance and NDCG evaluation metrics originating from the source paper to optimize machine-learned ranking functions.
Paper: Learning to rank: from pairwise approach to listwise approach, Zhe Cao et al. (2007). Develops listwise learning-to-rank algorithms directly evaluated against graded relevance metrics such as NDCG.
Paper: From RankNet to LambdaRank to LambdaMART: An Overview, Christopher J. C. Burges (2010). Extends gradient-based ranking optimization to directly maximize the non-smooth Discounted Cumulative Gain metric introduced in cumulated gain evaluation.
Paper: Optimizing search engines using clickthrough data, Thorsten Joachims (2002). Introduces ranking support vector machines designed to optimize relative document preferences and graded ranking quality in search engines.
Paper: Recommendations as Treatments: Debiasing Learning and Evaluation, Tobias Schnabel et al. (2016). Adapts discounted cumulative gain evaluation and learning objectives to handle missing-not-at-random implicit user feedback through inverse propensity scoring.
Paper: Unbiased Learning-to-Rank with Biased Feedback, Thorsten Joachims et al. (2017). Applies counterfactual learning-to-rank principles to debias user feedback when optimizing standard ranking utility and cumulative gain metrics.
Paper: The relationship between Precision-Recall and ROC curves, Jesse Davis et al. (2006). Provides a formal analysis of precision-recall dynamics and ranking trade-offs in highly skewed evaluation settings.
Paper: BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models, Nandan Thakur et al. (2021). Adopts nDCG@10 as a central evaluation benchmark across heterogeneous information retrieval datasets to measure zero-shot neural ranking.

Cover for IR evaluation methods for retrieving highly relevant documents

Abstract

This paper proposes evaluation methods based on the use of non-dichotomous relevance judgements in IR experiments. It is argued that evaluation methods should credit IR methods for their ability to retrieve highly relevant documents. This is desirable from the user point of view in modern large IR enviroments. 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 a given ranked position. We then demonstrate the use of these evaluation methods in a case study on the effectiveness of query types, based on combinations of query structures and expansion, in retrieving documents of various degrees of relevance. The test was run with a best match retrieval system (InQuery¹) in a text database consisting of newspaper articles. The results indicate that the tested strong query structures are most effective in retrieving highly relevant documents. The differences between the query types are practically essential and statistically 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.

Topics

relevance judgment text document

Keywords

IR evaluation methods document relevance non-dichotomous relevance multiple degree relevance relevance assessments best match retrieval query expansion retrieval performance

1. Introduction
2. Evaluation methods employing multiple degree relevance assessments
2.1. Precision as a function of recall
2.2. Cumulated gain-based measurements
3. Case study: the effectiveness of QE and query structures at different relevance levels
3.1. Test environment
3.2. Relevance assessments
3.3. Query structures and expansion
3.4. Test queries and the application of the evaluation measures
3.5. P-R curves and average precision
3.6. Cumulative gain
3.7. Discounted cumulative gain
4. Discussion and conclusions
Acknowledgements.
References

Knowls

Knowl 1 — Discounted Cumulated Gain (DCG) Metric
equation
Discounted Cumulated Gain ( $\mathrm{DCG}$ ) measures the cumulative graded relevance value a user obtains from a ranked retrieval list up to rank position $i$ , applying a progressive logarithmic penalty to down-weight documents retrieved at lower ranks. Let $G[i] \in \mathbb{R}_{\ge 0}$ denote the relevance gain value of the document ranked at position $i$ (where $i \in \{1, \dots, n\}$ ). Given a logarithmic base $b > 1$ , the discounted cumulative gain at rank $i$ , $\mathrm{DCG}[i]$ , is defined recursively as:

$\mathrm{DCG}[i] = \begin{cases} G[1], & \text{if } i = 1 \\[6pt] \mathrm{DCG}[i - 1] + \dfrac{G[i]}{\log_b i}, & \text{if } i > 1 \end{cases}$

Equivalently, it can be written non-recursively as:

$\mathrm{DCG}[i] = G[1] + \sum_{j=2}^i \dfrac{G[j]}{\log_b j}$

The first position is unadjusted because $\log_b 1 = 0$ . The parameter $b$ modulates the modeled user persistence: smaller bases (e.g., $b = 2$ ) model impatient users who rarely examine documents deep in the ranking, while larger bases (e.g., $b = 10$ ) model more persistent users.
Knowl 2 — Cumulated Gain (CG) Metric
equation
Cumulated Gain ( $\mathrm{CG}$ ) evaluates the total relevance value accumulated by a user by examining a ranked document list up to rank position $i$ , without applying any rank discounting. Given a gain vector $G$ where $G[i] \in \mathbb{R}_{\ge 0}$ is the graded relevance score of the document at rank $i$ (for $i \in \{1, \dots, n\}$ ), the cumulated gain vector $\mathrm{CG}$ is defined recursively as:

$\mathrm{CG}[i] = \begin{cases} G[1], & \text{if } i = 1 \\[6pt] \mathrm{CG}[i - 1] + G[i], & \text{if } i > 1 \end{cases}$

Equivalently, the cumulated gain at rank $i$ is the prefix sum:

$\mathrm{CG}[i] = \sum_{j=1}^i G[j]$

Unlike traditional binary precision-recall metrics, $\mathrm{CG}$ directly reflects the total quantity of relevant information delivered up to position $i$ without collapsing distinct relevance degrees into binary categories.
Knowl 3 — Theoretically Best Possible (Ideal) Cumulative Gain Benchmark
model/method
To establish an upper bound against which actual $\mathrm{CG}$ and $\mathrm{DCG}$ performance curves can be evaluated, an ideal ranking vector is constructed from the query's recall base.

For a given request with graded relevance judgments across discrete levels (for instance, relevance scores $3, 2, 1, 0$ representing highly relevant, fairly relevant, marginally relevant, and irrelevant documents respectively), let there be $m$ documents at relevance level 3, $l$ documents at relevance level 2, and $k$ documents at relevance level 1.

The ideal gain vector $G_{\text{ideal}}$ of length $n$ is constructed by sorting all known relevant documents in descending order of their relevance grades:
1. Positions $1$ to $m$ are assigned the value $3$ .
2. Positions $m + 1$ to $m + l$ are assigned the value $2$ .
3. Positions $m + l + 1$ to $m + l + k$ are assigned the value $1$ .
4. All subsequent positions up to $n$ are assigned the value $0$ .
Computing $\mathrm{CG}$ and $\mathrm{DCG}$ on $G_{\text{ideal}}$ produces benchmark curves that turn horizontal once all relevant documents are exhausted. The vertical distance between an actual retrieval method's curve and the ideal curve quantifies the search effort wasted on irrelevant or sub-maximally relevant documents.
Knowl 4 — Multi-Grade Stratified Precision-Recall and Average Precision Evaluation
model/method
When non-binary relevance judgments are available (e.g., four levels: 0 = irrelevant, 1 = marginally relevant, 2 = fairly relevant, 3 = highly relevant), traditional evaluation metrics can be stratified rather than collapsing all non-zero levels into a single binary category.

Separate recall bases are formed for each individual relevance level $r \in \{1, 2, 3\}$ . Precision-Recall (P-R) curves and average non-interpolated precision ( $\mathrm{AvP}$ ) are then computed independently for each recall base:

$\mathrm{AvP}_r = \frac{1}{|R_r|} \sum_{d \in R_r} P(\text{rank}(d))$

where $R_r$ is the set of all documents judged at relevance level $r$ for the request, and $P(\text{rank}(d))$ is the precision measured at the cut-off rank where relevant document $d$ appears.

Evaluating performance separately across distinct relevance strata reveals whether an information retrieval strategy selectively promotes highly relevant documents to the top ranks or merely retrieves marginally relevant documents.

Knowl 5 — Average Non-Interpolated Precision Across Query Structures and Relevance Levels

data/table

Average non-interpolated precision (AvP, in %) across 30 test requests demonstrates that query expansion (QE) coupled with strong query structures specifically enhances the retrieval of highly relevant documents, whereas weak query structures degrade or fail to benefit from expansion.

Relevance Level	Expansion	SUM	SSYN-C	WSYN
1 (Marginally relevant)	Unexpanded ( $u$ )	12.8	12.4	13.8
	Expanded ( $e$ )	10.1	13.3	14.3
2 (Fairly relevant)	Unexpanded ( $u$ )	22.4	21.5	22.9
	Expanded ( $e$ )	21.1	27.4	29.3
3 (Highly relevant)	Unexpanded ( $u$ )	25.9	23.5	25.7
	Expanded ( $e$ )	22.2	39.1	41.0

At relevance level 1, differences between query types are negligible. At relevance level 3, expanded strong queries ( $ext{WSYN}/e$ and $ext{SSYN-C}/e$ ) substantially outperform the unexpanded and weak baselines. For example, $ext{WSYN}/e$ achieves 41.0% AvP at level 3 compared to 25.9% for unexpanded $ext{SUM}/u$ (a 58.3% relative improvement), whereas expansion degrades the weak structure $ext{SUM}$ from 25.9% to 22.2%. Differences are statistically significant under the Friedman test, with the strongest significance observed at relevance level 3.

Knowl 6 — Search Efficiency and User Effort Under CG and DCG
empirical result
Analysis of cumulative gain ( $\mathrm{CG}$ ) and discounted cumulative gain ( $\mathrm{DCG}$ ) curves over ranks 1–100 reveals substantial differences in the user effort required to obtain relevant information across query types:
1. Document inspection requirements ( $\mathrm{CG}$ ): To achieve the cumulative gain at relevance level 3 that is theoretically attainable by retrieving 10 ideal documents, a user must examine 34 documents using expanded strong queries ( $\text{SSYN-C}/e$ , $\text{WSYN}/e$ ) versus 62 documents using weak or unexpanded queries. For combined relevance levels 2 and 3, the corresponding requirements are 20 documents versus 26 documents.
2. Discounted user effort ( $\mathrm{DCG}$ , $b=2$ ): To collect the discounted gain theoretically obtainable in the top 10 positions for levels 2 and 3, a user must inspect 35 documents with expanded strong queries versus 70 documents with the other query structures (requiring 100% more scanning effort).
3. Effect of discount logarithm base: At rank 50, the performance advantage of expanded strong queries over weak queries increases from 4 points with $\log_2$ (modeling impatient users) to 13 points (a 27% advantage) with $\log_{10}$ (modeling persistent users).
Knowl 7 — Testbed for Multi-Grade Relevance and Query Structure Experiments
experimental setup
The experimental evaluation was conducted using the InQuery retrieval system (version 3.1) based on Bayesian inference networks over a newspaper database of 53,893 articles (average length 233 words; compound words split into morphological basic forms).

Key characteristics of the testbed:
- Relevance scale: Assessed by four judges on a four-point scale: (0) Irrelevant, (1) Marginally relevant (topic mentioned in passing, mean document length 334 words), (2) Fairly relevant (topic discussed briefly, mean length 314 words), (3) Highly relevant (topic is the main theme, mean length 306 words).
- Recall base: Across 30 selected expandable requests, the recall base consists of 366 highly relevant, 700 fairly relevant, 857 marginally relevant, and 51,970 irrelevant documents.
- Query structures: Evaluated in unexpanded ( $u$ ) and thesaurus-expanded ( $e$ ) forms across three structures: weak bag-of-words baseline ( $\text{SUM}$ ), concept-based synonym groups ( $\text{SSYN-C}$ using #sum(#syn(...))), and facet-based weighted synonym groups ( $\text{WSYN}$ using #wsum with major facet weight 10 and minor facet weight 7).

Coverage note — None was omitted; all key contributions—including the formal definitions of CG, DCG, ideal baseline curves, stratified multi-grade P-R evaluation, the empirical testbed, AvP tables, and cumulative gain findings—have been captured.

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. Harman (Eds.), Information technology: The Fifth Text Retrieval Conference (TREC-5). Gaithersburg, MD: National Institute of Standards and Technology, 119–132, 1997.
2.D.C. Blair, & M.E. Maron. An evaluation of retrieval effectiveness for a full-text document-retrieval system. Communications of the ACM, 28(3): 289–299, 1985.
3.P. Borlund & P. Ingwersen. Measures of relative relevance and 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 and 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, 45(): 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äläinen. 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. Kekäläinen & K. Järvelin. 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 structure and query expansion on retrieval performance. 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 and Development in Information Retrieval. New York: ACM, 130–137, 1998.
12.R.M. Losee. Text retrieval and filtering: Analytic models of performance. Kluwer Academic Publishers: Boston, 1998.
13.T.B. Rajashekar & W.B. Croft. Combining automatic and manual index representations in probabilistic 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. Trivison. A study of information seeking and retrieving. I. Background and methodology. 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 Wide Range Performance of Boolean Queries in Full-Text Databases. Ph.D. dissertation. 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.

Citation

MLA

Järvelin, K., and J. Kekäläinen. “IR Evaluation Methods for Retrieving Highly Relevant Documents”. Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2000, pp. 41–48, https://doi.org/10.1145/345508.345545.

APA

Järvelin, K., & Kekäläinen, J. (2000). IR evaluation methods for retrieving highly relevant documents. Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 41–48. https://doi.org/10.1145/345508.345545

Chicago

Järvelin, K., and J. Kekäläinen. 2000. “IR Evaluation Methods for Retrieving Highly Relevant Documents”. Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 41–48. https://doi.org/10.1145/345508.345545.

Harvard

Järvelin, K. and Kekäläinen, J. (2000) “IR evaluation methods for retrieving highly relevant documents”, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval. ACM, pp. 41–48. Available at: https://doi.org/10.1145/345508.345545.

Vancouver

1. Järvelin K, Kekäläinen J (2000) IR evaluation methods for retrieving highly relevant documents. In: Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval. ACM, pp 41–48

BibTeX

@inproceedings{J_rvelin_2000, series={SIGIR00}, title={IR evaluation methods for retrieving highly relevant documents}, url={http://dx.doi.org/10.1145/345508.345545}, DOI={10.1145/345508.345545}, booktitle={Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval}, publisher={ACM}, author={Järvelin, Kalervo and Kekäläinen, Jaana}, year={2000}, month=July, pages={41–48}, collection={SIGIR00} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

IR evaluation methods for retrieving highly relevant documents

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Discounted Cumulated Gain (DCG) Metric

Knowl 2 — Cumulated Gain (CG) Metric

Knowl 3 — Theoretically Best Possible (Ideal) Cumulative Gain Benchmark

Knowl 4 — Multi-Grade Stratified Precision-Recall and Average Precision Evaluation

Knowl 5 — Average Non-Interpolated Precision Across Query Structures and Relevance Levels

Knowl 6 — Search Efficiency and User Effort Under CG and DCG

Knowl 7 — Testbed for Multi-Grade Relevance and Query Structure Experiments

References

Citation

BibTeX

Access the Paper