THEC O M P U T A T I O N

L A B O R A T O R YHarvard University
Cambridge, Massachusetts

Scientific Report No. ISR-10
INFORMATION STORAGE AND RETRIEVAL
toThe National Science Foundation

Cambridge, Massachusetts

Gerard Salton

March 1966

Project Director©
Copyright, 1965
By the President and !;,< Hows of Harvard CollegeUse, reproduction, or publication, in whole or in part, is permitted
for any purpose of the United States Government.

DOCUMENT RETRIEVAL SYSTEMS r OPTIMIZATION AND EVALUATIONA thesis presentedbyJoseph John Rocchio, Jr.
toThe Division of Engineering and Applied Physics
in partial fulfillment of the requirements
for the degree of. Doctor of Philosophy
in the subject ofApplied Mathematics

Harvard University
Cambridge, Massachusetts
March 1966

PREFACE

This*thesis presents a functional model for document
retrieval systems. Based on this model, a search request
optimization algorithm and an automatic classification algorithm
applicable to efficient storage organization are derived.

Inaddition some novel evaluation measures for document retrieval.
systems are proposed.
The writer is deeply indebted to Professor Gerard Salton forhis guidance during the conception and development of this thesis,and for his confidence, encouragement, and continuing support.
Particular thanks are also due to Mr. Michael Lesk for his
valuable assistance with respect to programming problems and with
operational aspects of the SMART system, and to the other members of
the SMART project at the Harvard. Computation Laboratory.

In addition

the editorial assistance and moral support of Mary Rocchio, theauthor's wife, were of immeasurable value.
Finally the writer wishes to acknowledge the support of thisresearch by the National Science Foundation under grant GN 36O, and by
the Bell Telephone Laboratories under contract with Harvard University.

:.v •TABLE OP CONTENTS

pagePreface. . . . . .

. . . . . . v

List of Figures. xi

List of Tables 'xiii

Synopsis. . xvn

CHAPTER. 1 INTRODUCTION

.

.

. . .

.

.

.

.

......

1-1.

.

. . . .

1-1

.

. .

1-2

.

. . 1-6. . . . . .

1-6

1. The Document Retrieval Problem
2. A Functional Model

3. A Specific Model - The SMART System
A.

Property Vector Indexing

Bi

Request Processing.

. v

C. Angular Distance MatchingD.

Terminology•• .

CHAPTER 2 TEE INDEXING FUNCTION

.

.

.

1-7. .

.

....

. •.

.

.

..

1-7.

1-8. . . . . . . . .

2-1

1. . Introduction•2-1

2. Manual Indexing.

2-2

3. Automatic Indexing

2-2

A.

The Statistical Approach

.

.

.

.

2-3

B.

Semantic Techniques '.

.

. ;.. .'. . . .

2-4

C.. Syntactic Techniques.

.

.

. ••

4.

The Structure of Index Representations

5*

Optimizing-the Index Transformationvii.

.

.
.

.

2-6.

.'

2-8 •.

.

2-1.2

TABLE OP CONTENTS (continued)

page

CHAPTER JSEARCH REQUEST FORMULATION
1.

. . . . . . . .

3-1

Introduction

3-1

2. Request Porinulation

.

.

. . .

•.

.

.

3. Request Optimization

3-5

4*

Relevance Feedback

5*

The Case of No Relevant Documents

6.

Experimental ResultsA.

.
.

Some Sample Search Requests

••

.

3-11.

. ..

3-20.

.

.

3-21

•

••

3-21

.

3-32

B. Average Results and Successive
IterationsC.
CHAPTER 4

Convergence

.

3-3.

.

.< .

3-42

THE QUERY-DOCUMENT MATCHING FUNCTION. . . . .

1.

The Comparison of Structured Operands

2.

Storage Organization

.

.

.

.

4-1

.• .

.

4-1.

.

.

.

.

4-7

3. Automatic Document Classification'.

.

.

.

4-12

4.

.

Classification and Metric Searching

5. A Heuristic Classification Algorithm
A.

Basic Concepts

.

.

.

.

.

4-16
. . .

.

.

.

B. Description of the Classification
Algorithm
6.

Experimental Results

viii

.

. . .

.

4-19.

4-19
4-20

. . . .

4-36

TABLE OP CONTENTS (continued)-

page
CHAPTER 5 EVALUATION OP DOCUMENT RETRIEVAL SYSTEMS

.

.

.

5-1

1. The General Problem

5-1

2. Evaluation Measures and tne Collectionof Statistics

5-2

A.

The Idealized Experiment. . . . . .

5-2

B. Evaluation Statistics

.

.

.

•.

.

5-6

C.

Output Characterization

.

.

.

.

.

.

5-12

D.

The Precision-Recall Tradeoff. . . .

5-15

5.

The Use of. Optimal Queries in Test Design .

.

5-17

4*

Cutoff-Independent Performance Indices

.'

5-19.

5-19.

5-29

A.

Derivation.

-B. Experimental Use.

Appendix A - The. SMART System

ix.

.

.

.

.

.

. . . . . . .

A-1

LIST OF FIGURES

Figure2.1

Excerpt from the. SMART Thesaurus

2.2

Alternative Property Space Index Representations

3.1

Query Formulation - The User-System Interfaces

3.2
3-3

3.4.

.

. '. .

.

. 2-7.

. 2-11.

. 3-2

Geometrical Representation of Relevance Feedback.

. 3-14

Relevant Document Images (r^ and fp) Which Have
Only Slight Association. . . . . .: . .

.

. 3-19.

. 3-19.

Hypothetical Document-Document Correlations Amongan Assumed Set of Relevant Documents

.

.

.

.

3*5

A Typical Sample Search Request.3*6

Query Processing Using Relevance Feedback for
Search Request. "I-R Indexing". . . . . . . .
Correlation Distributions for Search.Request"I-R Indexing"-. . .'• .• .'" "...

3.7
3-8

3*9

3.10

3.11

3.12

3.13

Query Processing Usltig Relevance Feedback for
Search Request "Pattern Recognition". . .

. 3-26.

3-29.. 3-31.* . 3-33

Query' Processing Using Relevance -Feedback for
Search Request "Analogs-Digital" . . . . . . . .

3-34

Precision vs. Recall for Initial Queries and Queries
Modified by Relevance Feedback (Averaged Over 24
Search Requests)
. .
; . .

. 3-3^

Comparison of Retrieval Results Using Original andModified Query for Search-Request "Random Numbers" .

. 3-37

Precision vs. Recall for Initial Queries and*Two. Iterations of Relevance Feedback
Retrieval Ranks of Relevant Documents for Query. "Automata" Comparing Original Results with Those
Obtained on Successive Iterations. . . . . .

xi

3-40.

. 3-41

LIST OP FIGURES (continued)

Figure
3.14

3.15

page
Retrieval Performance as a Function of Amount ofFeedback for Query "I-R Indexing"

..

3-43

...

. 3-44Retrieval Performance as a Function of Amount ofFeedback for Query "M9 Natlang"

.' .

•.

.

3.16

Document - Document Correlation Matricies

3-45

3.17

Retrieval Results for Two Queries Produced from
Original Search Request "M9 Natlang"

4*1

Set Image Matching Operations.4.2

Retrieval Operations with Boolean Query Images

4*5

Total Number of Comparisions Required vs. theNumber of Categories

.

.

.

.

3-46.

. ',.

.

.

. 4-4.

.

. 4r6.

• 4-22.

. 4-25.

4.4

Flowchart of Region Density Test' .

.

.

*.....

4.5

Graphical Illustration of the Density Test

4.6

Program for Specifying Cutoff Correlation

4-27

4.7

Progression of Categories and Correlation Distributions.

4-50

4.8

Classification Vectors

4-51.

4-26

4-9
4.10

Flowchart of the Classification Algorithm . . . . . 4-55'
Cumulative Frequency Distribution of the Cutoff
Correlation for Three Classifications
4-59
4.11 . Query-Classification Vector Correlation Distribution
for Request "Core Memory"• . . • , . . 4-40
4.12
Evaluation of Two Level Searching for Test Query"Core Memory".\ ...

. .

4.15- • Average Evaluations for 24 Search Requests
5.1Characterization of Retrieval Results
xii.

.

.

.

. 4-45. . . .

4-44.

.

.

.> . 5-4

LIST OF TABLES

pageWord Stem Frequency List of a Sample Document .. • .... . 2-10
Program Steps for Producing Relevance Feedback
Modified Queries. . . •

3-23

Titles of Documents Relevant to Search Request"I-R Indexing". . . . . . . . .

Comparison Operations on Set Represented Operands

.

3-30
. 4-3

Comparison Operations on Tector Represented Operands

4-7

Summary of the Steps of the Classification Algorithm. 4-34

Retrieval results for 4 Equally Probable Query Itypes. 5-11Comparison of Precision and Recall Estimates • .

xiii.

.

• 5-12SYNOPSIS

A model for document' retrieval systems consisting of thefunctional elements:

indexing, search request formulation, andrequest-document matching is examined in this thesis. Analysis of
the request formulation function leads to the definition of an •optimality criterion and to a request optimization algorithm suitablefor use in a system environment which allows iterative searching andreal time user-system interaction.

The optimality criterion has

applicability to the evaluation of index languages, and generally tothe design of evaluation tests for document retrieval systems.
Investigation of the request-document matching leads to a novelautomatic, classification algorithm applicable to metric comparison
measures, and useful for establishing an efficient storageorganization.

Finally'the statistical basis for the evaluation of

document retrieval systems is reviewed and some novel performancemeasures are proposed which are particularly suited to systems which
induce a retrieval ordering on the members of the searched collection.
Chapter 1 is introductory in nature and attempts to define
the area of discoairse and its relation to the general field of
information retrieval. A..general model for document retrieval systems
is introduced, and the basic functional elements of this model arebriefly outlined.

This material draws heavily on the work of Salton

and the SMART automatic document retrieval project, as well as thegeneral literature of the field.

xv

The indexing component of the model la discussed .in chapter 2
which is primarily descriptive in nature. The work of a number of
researchers in this area is cited in describing the development andcurrent trends of automatic content analysis. Particular emphasis isplaced on concept vector indexing techniques which incorporate
thesaurus type semantic associations.. The SMART system generates
document and query index images by such techniques and these were usedin obtaining the experimental results presented in Chapters 3 and 4.
The original contributions in chapter 2 are related to the techniques
proposed for index image optimization.
A search request optimization algorithm analytically derived
from an assumed optimality criterion is presented in Chapter 3. The
optimization algorithm and the'notion of request optimization by an
iterative sequence of retrieval operations are original with the author.
In addition the notion of testing index language devices by the use of
optimal search requests is original. Experimental results illustrating
the optimization process are presented.

These were derived by asimulation which was coded and run on the .IBM 7094 in conjunction with
the SMART retrieval system. A search request formulation based on this*optimization technique offers the promise of improving the performanceof document retrieval systems, given'the current state of developmentof computer time sharing and man-machine communication technology.
Chapter 4 pre'sents an original automatic documentclassification algorithm, heuristically motivated by considerations ofsearch• efficiency and by the functional nature of query-document'
matching operations. This algorithm was coded in Fortran and run on

xvi

the IBM 7094 producing several classifications of a-collection of 405
document index images (incorporated into the SMART system).

Someexperimental results illustrating the use of the classifications for
improving search efficiency are presented.

Document classificationof the type described is novel, in that it is proposed as a direct
adjunct to the query-document matching operation.

Normally,

automatic classification algorithms have been considered as replacements for manual classification or indexing.
The statistical basis for the evaluation of document
retrieval systems is discussed in Chapter 5«

Several of the topics

considered are' based'on previous work which is cited by bibliographic
reference. The organization and presentation as well as some of the.
conclusions drawn are original. In addition-some novel performancestatistics are derived which are particularly applicable to querydocument matching operations possessing a high degree .of discrimination such as the correlation measure of the assumed model. Each ofthe statistics derived is capable of describing overall system
performance with a single parameter in contrast with several of theevaluation measures in current use.

xvii

DOCUMENT BETRIEVAI, SYSTEMS - OPTIMIZATION AMD EVALUATION