Department of Computer ScienceCornell University
Ithaca, New York 1^850

Scientific Report Mo. ISR-12
INFORMATION STORAGE AND RETRIEVAL
toThe National Science Foundation
Reports on Evaluation, Clustering, and Feedback

Ithaca, New York

Gerard Salton

June 1967

Project Director©
Copyright, 1967
by Cornell University

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

ii

Staff of the Department of Computer Science
Cornell University

Kenneth M. Brown
Richard W. Conway
Margaret Dodd
Patrick C. Fischer
Sally Grove
Juris Hartmanis
Eleanor R, IdeE. Michael Keen
Joann NewmanGerard Salton
Robert J. Walker
Peter Wegner
Robert E. Williamson

Project Staff in the Division of Engineering and Applied Physics
Harvard University

Jeffrey Bean
Claudine Harris
Sally Hobbs
Michael Lesk
E# Ricardo Quinonesiii

TABLE OP CONTENTS
Page
SUMMARY

.

.

.

.

.

.

.

.

•xi

PART ONEEVALUATIONI.

SALTON, G.
M

The SMART Project - Status Report and Plans"

1.

Introduction•.

2*

Experimental Results

.

.

.

1-1
1-3

3. Future Plans. .

A) Additional Evaluation Experiments
B)

II.

New Real-Time Operating System

1-6.

•.

.

. . . . . .

•1-6
1-9LESK, M. E.
f,

SIG - The Significance I*ograms for Testing the Evaluation Output"

1.

Introduction

2.

T-tests

II-3

3. Sign Tests

II-8

h.

. . . . . . .

Program Operation

5. Output
References

•.

•.

n-i

•

.

•.

.

11-13
. . . . . . .

iv. II-IO

11-22

TABLE OF CONTENTS (continued)
Page
III.

SALTON, G. and LESK, M. E.
"Computer Evaluation of Indexing and Text Processing"1.

Introduction

III-l

2.

The SMART System

III-3A) Basic Organization

III-3B) Evaluation Process

III-5C) Significance Computations111-12

3. Experimental Results

111-22A) Test Environment111-22B) Document Length111-27C) Matching Function and Term Weights

k.

.

.

.

Ill-31

D) Language Normalization - The Suffix Process .

Ill-38E)

Synonym Recognition

III-^-lF)

Phrase Recognition

111-^-6G) Hierarchical Expansion

111-5^H) Manual Indexing

111-55Concluding Comments

III-60Acknowledgment

III-65

References

111-66PART TWO
CLUSTER SEARCH METHODSIV.

IDE, E., WILLIAMSON, R. and WILLIAMSON, D.
"The Cornell Programs for Cluster Searching and Relevance Feedback"v

TABLE OF CONTENTS (continued)
Page
IV. continued
X-Design Criteria

IV-1

2. Basic Cornell System Organization
3#. . IV-1

System Implementation of Rocchio*s
Clustering AlgorithmU.

. . . .

• • . •

IV-2

System Implementation of Relevance Feedback. . . IV-6

5. Further Details of the Cornell SystemOrganization. . . . . . . . . . . . .
IV-8A) Routines Available Without User
Reprograraming. . . . . . . . . . .
IV-8B) Service Ro\xtines Available to theExperimental Programmer . . . • . . . . IV-10
ReferencesV.

. . . . . . . •IV-13

SALTON, G.
"Search Strategy and the Optimization of Retrieval Effectiveness"
Abstract. . . . . . . .

v-1

1.

Introduction

V-1

2.

Cluster Search ProcessV-^A) Overall ProcessB) Cluster Generation

V-5
v-6

• . . . •C) Cluster Searching and Evaluation
3. Relevance Feedback

.

.

.

.

.

.

v-18
.

.

.

.

.

A) Overall Process • . . . . . • . . . .
B) Feedback Evaluation. . . . . . . . .

vi

v-30
V-30
v-33

TABLE OF CONTENTS (continued)
Page
continuedh.

Adaptive User-Controlled Multi-Level Search .

.

.

References

V-^2
V-^-6

GRAUER, R. T. and MESSIER, M.
"An Evaluation of Rocchio's Clustering Algorithm"
Abstract

VI-1

1.

Introduction

VI-1

2.

A Description of Rocchiofs Algorithm

VI-2

3.

Problems to be Studied

VI-^

k.

Evaluation Scheme

VI-6A) Tabulation of Results

VI-8B) Detailed Analysis

VI-16C) Conclusions and Remaining Questions

.

.

.

References

VT-37
VI-39

LEECH, P. C. and MATLACK, R. C. Jr.
"Information Retrieval: Dictionary Representations andCluster Evaluation"

Abstract

VII-11.

Introduction

VII-1

2.

Rocchiofs Clustering Procedure

3. The Experiment

.

VII-3
VII-5vii

TABLE OF CONTENTS (continued)
Page
VII.

continued
k*Results and Evaluation. • .-• • • • . . •VII-7A) The Null Dictionary. •VII-7B) The Thesaurus Dictionary. . . . . . .

VII-13. • • • • • .

VII-1^C) Comparison of the Null andThesaurus Dictionaries
5. Conclusions
References.

.

. . • . . . . . . • . •VII-16.

VII-18

•

.

.

.

.

.

•••

.

*.

PART THREEUSER FEEDBACK ALGORITHMS

VIII.

IDE, E.
"User Interaction with an Automated Information Retrieval System11Abstract
1.

. . . . . . .

Introduction

VIII-1. • .

VIII-1

2. The Experimental Environment

VIII-5

3. Experimental Results

VIII-7. . . . . . . . . .

A) Comparison of the Cranfield and ADI
Collections.
B) Strategies Using Relevant Documents OnlyC) Amount of FeedbackD) Strategies Using Non-relevant Documents
k.

. •
• .

Conclusions

Acknowledgments

VIII-8
VIII-10
VIII-13
VIII-18
VIII-28. . . . . . . • . • • • •ReferencesVIII-31
VIII-32viii

TABLE OF CONTENTS (continued)
Page
IX.

KELLY, J*"Negative Response Relevance Feedback"1. Introduction
2.

•Principal Algorithm

DC-2

3. Experimental Method
k.

H>1

• . •

IX-5

Results

DC-7

5. Conclusion

IX-9

References

IX-10

Appendix

IX-11

X. FRIEDMAN, S. R., MACEYAK, J. A. and WEISS, S. F.
"A Relevance Feedback System Based on Document Transformation"
Abstract

X-l

1. The Problem

X-l

2. The Implementation• • . . . • • . • • •3. Experimental Results

X-7

h.

X-17Conclusions

References

XI.

X-3

X-19

AMREICH, M., GRISSOM, G., MICHELSON, D., IDE, E.
"An Experiment in the Use of Bibliographic Data as a Sourceof Relevance Feedback in Information Retrieval"
Abstract

XI-1ixTABLE OF CONTENTS (continued)
Page
XI.

continued
1.

Introduction

.

.

.

. . .

.

. . .

2.

The Bibliographic Assumptions

•.

. . .

3. The Problem and Method
h.

.

.

.

XI-1

.

.

XI-2. .

••

.

.

.

.

.

•XI-3

Query Alteration in Feedback.

.

.

.

.

.

.

.

XI-9

5. Evaluation6.

XI-9

Conclusions and Recommendations. . . . . . .

XI-25

References

XII.

XI-27

HALL, H. A. and WEIDERMAN, N. H.
"The Evaluation Problem in Relevance Feedback Systems"
Abstract. . . . . .

.

.

1.

Introduction

2.

The Present Evaluation System.

.

.

.

.

.

.

. . . . . . . . . . . . .
.

.

XII-1
XII-1
XII-2

3. The Problem

XII-5

^.

The Solution

XII-85»Preliminaiy Results

XII-106.

Conclusion

XII-16.

References

XII-18x

Summary

The present report is the twelfth 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 of Engineering and Applied Physics at Harvard University. Unlike some of thepreceding reports (ISR 7> 8, 9 and 11), the present report does not deal
principally with the programming design of the fully-automatic SMART document retrieval system, now implemented both at Harvard on an IBM 709^ computer and at Cornell on a CDC l6ok.

Instead, the report deals with thesearch and retrieval experiments undertaken over the last year (June 1966to June 1967)> ^ d with the evaluation results obtained by applying theSMART System to document collections in computer science, documentation,and aerodynamics.
The report is divided into three parts, titled Evaluation, ClusterSearching, and User Feedback Methods, respectively.

The first part, Evalu-ation, contains a complete summary of the retrieval results derived fromsome sixty different text analysis experiments.

In each case, significancecomputations are included which can be used to assess the statistical significance of the reported retrieval results. Conclusions are drawn from theexperimental results which may affect the design of future fully-automatic
information retrieval systems.
The second and third parts are devoted to a number of experiments inreal-time information retrieval, designed to make the user participate in
the search process. Specifically, various iterative search strategies arexievaluated based on feedback information returned to the system by the user,
following an initial search operation.

This feedback information is thenused to improve the output obtained during subsequent searches. Evaluation
results are presented in part three for many kinds of user feedback strategies.
If the user is relied upon to assist in the search operations, thenthe system response times must be strictly controlled.

In particular, it

becomes impossible to perform full searches of the stored document collections
which may require the comparison of each stored item with each given searchrequest.

Instead, fast searches are required where only small subsectionsof the available collections are examined.

Such "document cluster" searches

are examined in part two of this report.
Part 1 on evaluation consists of sections I, II, and III. Section I
by G* Salton contains a short report on the present state of the SMART
project, including also a summary of the research proposed for the immediate
future.
Section II by M. E. Lesk contains a write-up of the new evaluation
system incorporated into the SMART System for the determination of thestatistical significance of the output results. Specifically, for each pairof search and analysis methods being compared, statistical measurements arepresented assessing the significance of the differences in performance between the two methods. Thus, it becomes possible to distinguish randomvariations due to individual request differences from statistically validresults.
Section III by G. Salton and M. E. Lesk is a summary of the SMART
evaluation results obtained during 1966 and the first part of 1967 withxii

collections of 780 document abstracts, 82 short papers, and 200 abstracts
in the areas of computer science, documentation, and aerodynamics, respectively.
The main (statistically valid) results which are obtained for all collections
state that the use of weighted subject identifiers is always more effective
than the use of logical identifiers with weights restricted to 0 and 1;
the cosine correlation is superior as a method for the comparison of analyzed documents and search requests; furthermore, full document abstracts
are far more effective as a source of content identification than document
titles alone. A thesaurus process, involving synonym recognition always
performs more effectively than methods using the original words, or wordstems, included in a document; other dictionary methods, including procedures based on phrase dictionaries and subject hierarchies are not substantially more useful than synonym dictionaries alone. The more effective,
fully-automatic text analysis procedures are approximately equivalent in
performance to standard retrieval methods based on manually assigned keywords.
The cluster search procedures based on automatically generated
document groupings are described in Part 2, consisting of Sections IV toVII.

A short description of the computer programs developed both forcluster searching and for the user feedback operations is contained in
Section IV by E. Ide, and D. and R. Williamson. The principal searchstrategies and feedback operations useful in a real-time, user-controlled
retrieval environment are then described in Section V by G. Salton, wheretypical evaluation results are also given.
Several alternative parameters for the generation of document
clusters are evaluated in Section VI by R. Grauer and M. Messier.

xiii

It is found, in particular, that search systems "based on a large numberof document groups, each group containing only a few documents, produce
generally better results than systems based on fewer clusters of larger
size. This same result is also obtained in Section VII by P. C. Leechand R. C. Matlack using document groupings obtained from several kinds ofanalyzed document representations.

Sections VI and VII contain a varietyof additional results leading to the generation of more effective documentgroups useful in partial search systems.
Part 3, consisting of sections VIII to XII, describes the so-called"relevance feedback" process which allows the users to introduce data concerning their information needs in order to obtain improved service. A
large variety of feedback strategies is considered in Section VIII byE. Ide. Evaluation results are presented, in particular, for systems inwhich the user examines a fixed number of documents following each search
operation.

Situations where a variable number of items is used in each

iteration are also treated.

It is found that users desiring high-precision

should feed back information for only one relevant item in each of two
search iterations. Users requiring high recall should, however, examine
a larger number of documents after the initial search. Results are also
given in Section VIII for a "negative" feedback strategy where information
concerning the first nonrelevant item is used to update the search request,
in addition to information derived from relevant items.
"Negative" feedback strategies are further studied in Section IX
by J. Kelly for the special case where the system fails to produce any
useful items for a given customer.

In that case, the information to bexiv

fed back is wholly negative in the sense that the available search request
is known to be unhelpful, even though it is not clear how it can be improved
directly.

A negative feedback strategy is described and evaluated which isdesigned to sweep through the document space in a controlled manner so as toinsure that relevant items are eventually picked up if they exist.
A feedback strategy based on a dynamic document space is investigatedby S. R. Friedman, J. A. Maceyak, and S. F. Weiss in Section X.

This strategy

consists in altering the document space by letting both documents and searchrequests approach the set of relevant items previously identified by theusers (in a normal feedback process only the queries are moved but not thedocuments).

It is shown that the system based on document transformations

produces greater improvements in search effectiveness than query transformations alone.
Bibliographic information is used as an additional feedback resourcein an experimental system described in Section XI by M. Amreich, G. Grissom,and D. Michelson. Specifically, relevant items are identified by the users
as before. The user is then allowed to supplement the respective content
identifiers by information consisting of the names of authors of related
documents, or of bibliographic information cited by the relevant documents.
Bibliographic information used as a source of feedback is found to be comparable in effectiveness to feedback information derived from subject identifiers alone. These findings reinforce the importance of previous work on
citation tracing and "bibliographic coupling" as an aid in the retrieval
process.
In Section XII by H. A. Hall and N» H. Weiderman, a new evaluation
algorithm is introduced for searches using feedback procedures. Two separatexveffects are noted both of which may increase the recall and precision of a
feedback search: the shift between successive iterations in the rank of
documents which had already been retrieved earlier, called the ranking effect;
and the retrieval of new relevant items, called the feedback effect. Evaluation methods are proposed which take into account the feedback effect only,and disregard the ranking effect.
Readers interested in an overview of the work contained in this report
should start by looking at sections III, V, VI, and VIII before taking up theremaining studies.

xvi