DEPARTMENT OF COMPUTER SCIENCECORNELL UNIVERSITYINFORMATION STORAGE AND RETRIEVALScientific Report No. IRS-13
to
The National Science Foundation
Reports on Evaluation Procedures and Results 1965-1967

Ithaca, New York
December 1967

Gerard Saltoo
Project Director

Department of Computer Science
Cornell University
Ithaca, New York 14850

Scientific Report No. ISR-13
INFORMATION STORAGE AND RETRIEVALtoThe National Science Foundation
Reports on Evaluation Procedure and Results 1965-1967

Ithaca, New York

Gerard Salton•

January 1968

Project Director

oCopyright 1968
by Cornell University

Use, reproduction, or publication, in whole or in part, is permitted
for any purpose of the United States Government,

11

REPORTS ON EVALUATION PROCEDURE AND RESULTS 196 5-1967
TABLE OF CONTENTS
Page
SUMMARY

I.

.

.

.

.

.

.

.

.

.

.

KEEN, E. M.
M

Test Environment"

1.

Introduction

1-1

2.

Document Collections and Search Requests

3.

Relevance Decisions

1-5

4.

Text Experiments

1-11

.

A)
B)

Experimental Procedures
Variables Tested

C)

Vocabularies and Index Language Devices

.

.

.

1-1

.

5.

Relevance Grade Test Results

6.

Request and Collection Comparisons

1-11
1-13
•

.

.

1-17
1-24

•

•

•

•

'

•

1-28

A)
B)

Request Preparation
Specific and General Requests

1-28
1-31

C)

Collection Comparisons

1-41

References

II.

xi

1-48

KEEN, E. M.
"Evaluation Parameters"
1.

Introduction

II-l

2.

Purposes, Viewpoints and Properties of Performance
Measures

II-l

Measures for Ranking Systems

II-6

3.

iv

Staff of the Department of Computer Science
Cornell University

Kenneth M. Brown
Richard W. Conway
Patrick C. Fischer
Sally Grove
Juris Hartmanis
John E. Hopcroft
Eleanor R. Ide
E. Michael Keen
Joann Newman
Gerard Salton
Gerald Siegel
Roland A. Sweet
Robert J. Walker
Peter Wegner
Burton Weiss
Donna Williamson
Robert E. Williamson

Staff in the Division of Engineering and Applied Physics
Harvard University

Jeffrey Bean
Sally Hobbs
Michael Lesk
E. Ricardo Quinonesiii

TABLL OF CONTENTS (continued)
Page
II.

continued
A)

Single Number Measures

B) Varying Cut-off Performance Curves

II-6
.

.

.

.

C) Comparison of Single Number and Curve Measures
4.

II-7
.

11-13

The Construction of Average Precision Versus
Recall Curves

11-18A) Averaging Techniques

11-18

B) Cut-off Techniques

11-21C) Extrapolation Techniques for Request
Generality Variations

11-31

D) Extrapolation Techniques for Evaluation ofCluster Searching

11-40

5. Measures for Varying Relevance Evaluation

.

.

.

11-43

6.

.

.

.

II-M-6

Measures for Varying Generality Comparisons7.

Techniques for Dissimilar System Comparisons andOperational Testing
8. The Comparison of Specific and General Requests andthe Viewpoints of the "higher precision'1 and"high recall" user
9.

III.

11-53

The Presentation of Data as Individual Request Merit .

References

.

.

11-51

.

11-63
11-67

KEEN, E. M.
"Search Matching Functions"1.

Introduction

III-l

2.

Matching Procedures used in Manual, Mechanized
and Automated Systems

III-l

v

TABLE OF CONTENTS (continued)

continuedA) Manual Systems

III-lB) Mechanized Systems

3.

.

III-5

C) Automated Systems

III-8

SMART Test Results — Matching Functions ,III-9A) Description of Functions

III-9B) Retrieval Performance Results

III-llC) Analysis of Performance

111-17«f. SMART Test Results — Weighting Scheme

111-29A) Description of Weighting Scheme .

111-29B) Retrieval Performance Results.

,

111-30111-32C) Analysis of Performance
5. Conclusions and Suggested Further Studies

111-48References

111-58REITSMA, K. AND SAGALYN, J.
"Correlation Measures'1
Abstract

IV-1

1.

Introduction

.

.

.

.

.

.

.

IV-1

2.

Weighted versus Logical Description Vectors

IV-2

3. The Correlation Coefficients

IV-5A) The Inner Product

IV-6B) The Cosine Coeffieient

IV-7C) The Hypersine Coefficient

IV-7D) The Overlap Coefficient

IV-8

vi

TABLE OF CONTENTS (continued)
Page
continued
E)

The Maron-Kuhns Coefficient

IV-9

F)

The Parker-Rhodes-Needham Coefficient .

G)

The Stiles Coefficient

IV-13

H)

The Average Coefficient

IV-15

I)

The Reitsma-Sagalyn Coefficient

.

.

.

.

.

.

IV-11

IV-16

4.

Method of Evaluation

IV-17

5.

Experimental Results

IV-19

6.

Discussion

IV-22

References

IV-26

Tables

IV-27

KEEN, E. M.
"Document Length"1.

Introduction

V-l

2.

SMART Test Comparisons

V-3

3.

Effect of Changes in Document Length

4.. Test Results

.

.

.

.

.

.

.
.

V-M.

.

.

V-13

A)
B)

Abstracts versus Titles
Abstracts versus Full Text

V-JJ+
V-28

C)

Abstracts versus Indexing

V-40

5.

Individual Requests and Discussion of Results

6.

Conclusions

.

•

V-48
V-58

References

V-60

vii

TABLE OF CONTENTS (continued)
Page
KEEN, E. M.
"Suffix Dictionaries"
1.

Introduction

VI-1

2.

Description of Suffix Dictionaries

VI-1

3.

Retrieval Performance Results

VI-4

4.

Performance Analyses

VI-9

5.

Conclusions

VI-20

References

VI-22

KEEN, E. M.
"Thesaurus, Phrase and Hierarchy Dictionaries"
1.

Introduction

VII-1

2.

Description of Thesaurus Dictionaries

3.

Description of Phrase Dictionaries

M-.

Description of Hierarchy Dictionaries

5.

Retrieval Performance Results

VII-10A)

Thesaurus Dictionaries

VII-10B)

Phrase and Hierarchy Dictionaries

.

.

.

.

VII-1
VII-3

.

.

.

.

.

.

.

.

VII-8

VII-27

6.

Summary of Results

VII-37

7.

Performance Analyses

VII-438.

Further Studies Required

VII-55

References

VII-58viii

TABLE OF CONTENTS (continued)
Page
VIII.

DATTOLA, R. T. AND MURRAY, D. M.
M

An Experiment in Automatic Thesaurus Construction"

Abstract

VIII-1

1.

Introduction

VIII-1

2.

The Construction Algorithm

VIII-2

3.

4.

A)

Clustering the Document Collection

B)

Formation of Initial Classes

VIII-3C)

Formation of Merged Classes

VIII-6

D)

Formation of Final Classes

VIII-9Evaluation .

.

.

.

VIII-3

VIII-11A)

Evaluation of the Classes

B)

Retrieval Evaluation

Analysis of Results.

VIII-11
,

.

.

A)

Overlap

B)

Unique Concepts

C)

Homogeneous Concept Classes

D)

Dividing Weights•

E)

Cranfield Collection.

F)

Comparison of Other Methods

.

.

.

.

VIII-15•

VIII-17
VIII-22•

VIII-22.

.

.

.

VIII-23
VIII-24

.

.

.

.

•

References

IX.

,

.

VIII-2MVIII-25
VIII-26

LESK, M. E.
"Word-Word Associations in Document Retrieval Systems"
1.

Introduction

.

.

IX-1

2.

Method •IX-1

3.

Results

IX-5

4.

Retrieval Experiments

IX-18

ix

TABLE OF CONTENTS (continued)

Page
IX.

continued
5.

Conclusions

IX-50

References

X.

IX-52

KEEN, E. M.
"An Analysis of the Documentation Requests"
1.

Introduction

X-l

2.

Request Preparation

X-l

3.

Characteristics of the Requests

X-2

A)

LengthX-2

B)

Important Request Words

X-3

C)

Multiple Need Requests

X-3

D)

Unclear Requests

X-5

E)

Difficult Requests

X-6

^.

Relevance Decisions

5.

Request Performance
A)
B)

6.

X-8
.

.

.

.

.

.

.

.

.

X-9

General Performance Analysis Methods . . .
Variation in Generality, Length and Concept
Frequency

.

X-9
X-10

C)

Comparison of Requests of the Two Preparers

.

.

X-20

D)

The Recognition of Important Request Words

.

.

X-26

Performance Effectiveness and Search Procedures

.

.

X-3M-

References

'

X-41

APPENDIX A"Recall-Precision Tables"

A-1

APPENDIX B"Original and Modified ADI Queries"x

B-l

Summary

The present report is the thirteenth in a series covering researchin automatic storage and retrieval conducted by the Department of Computer
Science at Cornell University with the assistance of the Division ofEngineering and Applied Physics at Harvard University,

The present reportcontains a detailed analysis of the retrieval evaluation results obtainedwith the automatic SMART document retrieval system over the last few years
for document collections in the fields of aerodynamics, computer science,and documentation.

The various components of fully automatic document

retrieval systems are covered in detail, including the form of input(section V ) , automatic content analysis methods (sections VI, VII, VIII,
and IX), and the matching procedures used to compare documents and searchrequests (sections III and IV). The complete test environment and theparameters which enter into the evaluation process are also described(sections I and II).
Unlike its predecessor (report ISR-12), the present report does
not cover the iterative search procedures based on user feedback, or thepartial cluster searches designed to speed up the search process, but
confines itself to the treatment of the standard fully-automatic analysis
and search procedures incorporated into the SMART system, and supplements
the summary titled "Computer Evaluation of Indexing and Text Processing",
previously published as section III of report ISR-12.

Preliminary retrieval

results for relevance feedback and cluster searching are contained in
section V of report ISR-12,- a more definitive treatment of user-controlledxisearch and retrieval methods follows in subsequent reports in this series.
The analysis of information search procedures and the measurementof retrieval performance are tasks for which a clearly established methodology does not as yet exist.

For this reason, it becomes necessary toconsider several different procedures, each designed to reveal a different
aspect of retrieval evaluation:

the total system viewpoint, the viewpointof the user who insists on high precision, and that of the user who requires
high recall.

In each case, the aim of the studies included in the present

report has been to reach conclusions which may be of practical help to thedesigner of automatic information systems. The analysis used is thus "insightoriented" rather than "proof-oriented" in the sense that a selective manual
analysis of a few typical requests is used in order to gain an understandingof the general process. Formal statistical significance computations of theevaluation results are contained in section III of report ISR-12.
All but three of the ten sections of this report have been preparedby E. M. Keen.

Section I is devoted to a detailed examination of the test

environment used, including a description of the document collections andsearch requests, of the manner of obtaining relevance decisions, of thevariables entering into the evaluation process, and of the differences in thequery and document make-up for the three collections in use.
The evaluation parameters are examined in detail in section II. The
viewpoint used in generating the performance measures is first described.
This is followed by an introduction of some performance measures which areparticularly useful for systems producing a ranked document output in decreasing order of correlation between documents and search requests. Twotypes of evaluation measures are used including global measures where axii

single number serves as an indication of system performance, and continuousrecall-precision curves.

The construction of the recall-precision curves

is described in detail in section II, as are the methods used for produrinq
curves averaged over many search requests.

Extensions of the basic evalu-

ation techniques are also discussed to cover cases where variable relevance
grades are assigned to documents, and to indicate the problems inherent
in a comparison between experimental and operational retrieval systems.
Detailed test results, covering the correlation methods used tocompare analyzed documents with analyzed search requests are given in
section III.

The analysis includes, in particular, a comparison between

the "overlap" coefficient which represents a measure proportional to thenumber of matching terms, and the "cosine" coefficient which takes into
account also the total number of terms present in a given document.

Ineach case, the terms are either weighted in accordance with their presumed importance, or unweighted.

The conclusion reached is that thecosine correlation used with the weighted content identifiers produces
a superior retrieval performance in comparison with the other possible
correlation procedures.
Ten additional correlation measures are examined in section IV by
K. Reitsma and J. Sagalyn, using the ADI collection for test purposes.
The coefficients used include, in particular, the cosine function, theoverlap measure, the inner product, the Maron-Kuhns measure, the ParkerRhodes-Needham measure, and others.

Overall, when all recall levels aretaken into account, the cosine measure again produces the best results.

xiii

The effects of varying the length of the documents to be analyzed
automatically, and of using a variety of stored dictionaries in the courseof the analysis are examined in detail in sections V, VI, and VII by E. M.
Keen.

Variations in document length are covered in section V, including acomparison for all collections of the use of titles only with the use abstracts, and of abstracts with full text for the ADI collection. Titles
are found to be unsatisfactory for high recall searches with all collections.
At the high precision end of the spectrum, good titles are sometimes
almost equivalent to poor abstracts.

In general, however, abstracts aresuperior to titles as a source for generating content identifiers. The
abstracts are found only slightly inferior to full text for the ADI
collection, suggesting that the increased expenditure of entering fulltext is probably not warranted.
Two types of suffix cut-off procedures designed to reduce language
variability by transforming full word paradigms to word stems are evaluatedin section VI. The suffix f s' dictionary produces common word forms foritems which differ only in a final ' sf whereas the word stem dictionary
reduces a complete family of related words to a common word stem.

The stem

dictionary is found to be superior as a retrieval tool to the suffix 's'
dictionary for the IRE and ADI collections; the suffix ' s* dictionary isslightly superior to the stem dictionary for the Cranfield collection, probably because the more specialized aerodynamics vocabulary provides fewer
opportunities for word reduction.

The suffix dictionaries offer a con-venient mark against which the effectiveness of thesaurus-type dictionaries
can be measured.

xiv

Thesaurus dictionaries, phrase dictionaries and hierarchicalarrangements of terms are described and evaluated for retrieval effectiveness in section VII, A thesaurus is generally used to assemb ^certain terms into common thesaurus groups according to specified similarity criteria.

Terms within the same group can then be reduced toa unique class number, thus providing a certain amount of language
normalization.

The best thesaurus dictionaries produce an average

retrieval performance superior to that provided by the stem dictionaries.
For high-precision users, the thesaurus results are not, however, very
different from the stem results. Thesaurus construction rules havebeen devised to insure that a thesaurus is obtained which will, in fact,
operate satisfactorily in a retrieval environment, and produce theexpected improvements for high recall users.
The results exhibited in section VII for the phrase dictionaries
and hierarchical subject arrangements show that the effect of thesedevices is not as yet sufficiently reliable to warrant their inclusion
in operational situations.
Suggestions are also made in section VII for additional retrieval
experiments using stored dictionaries, and for the generation of additional
language normalization tools.
An experiment in fully-automatic thesaurus construction is described in section VIII by R. T. Dattola and D. M. Murray.

The procedure

consists in breaking a document collection down into sub-collections,using document-document correlation methods. For each sub-collection, athesaurus is then constructed using term-term correlation methods. Finally,xv

a "super-thesaurus" is generated for the whole collection by merging theindividual term groupings obtained from the subcollections.

Retrievalexperiments show that such a fully-automatic super-thesaurus produces
better retrieval results than manually constructed thesauruses.
Statistical word-word association procedures are examined andevaluated in section IX by M. E. Lesk.

Associative procedures producegroups of terms (or documents) based on the co-occurrence of the terms
within the documents of a collection, or within the sentences of adocument.

The effect is then similar to that of a thesaurus, except thatthe construction method is automatic.

The data included in section IX

show that the associative method furnishes results which are essentiallyindependent from those obtained by a normal thesaurus procedure.

The

associative term groups are unrelated to the thesaurus groups, andthere appears to be no basis for the conjecture that second order term
associations are equivalent to synonym groupings.
Like the synonym groupings of a thesaurus, word-word associations
do occasionally improve the recall of a retrieval system; they also
improve the precision by promoting certain relevant documents to higher
rank positions.
A detailed analysis of the search requests used with the ADI
documentation collection is contained in section X by E. M. Keen.

Variouscharacteristics of the search requests are examined, including criteria
for identifying unclear request statements, requests expressing multiple
needs, requests with identifiable important words, requests with restrictive
negative statements, and so on.

Using these characterizations, certain

xv i

hand modifications are made to the ADI queries and the resulting improvements in retrieval effectiveness are exhibited.

Comparisons are also madebetween certain automatic search procedures and manual searches using a
KWTC type index.
A full summarization of all recall and precision tables for allcollections and all search experiments is included in appendix A.
Appendix B contains a listing of the 35 ADI requests for both original forms
and hand-modified versions.
It is hoped that some of the evaluation results presented in thisreport may lead to the design of more effective fully-automatic retrieval
systems in the foreseeable future.

G. Salton

xvii