DEPARTMENT OF COMPUTER SCIENCECORNELL UNIVERSITYINFORMATION STORAGE AND RETRIEVALScientific Report No. ISR-11
to
The National Science FoundationIthaca, New York
June 1966

Gerard Salton
Project Director

Department of Computer ScienceCornell University
Ithaca, New York I W 5 0

Scientific Report No. ISR-11
INFORMATION STORAGE AND RETRIEVALtoThe National Science Foundation

Ithaca, New York

Gerard Salton

June 1966

Project Director©
Copyright, 1966
by Cornell University
Use, reproduction, or publication, in whole or in part, is permitted forany purpose of the Uhited States Government.

Staff of the Department of Computer Science
Cornell UhiversityRichard W. Conway
Margaret Dodd
Patrick C. Fischer
Juris Hartmanis
Michael Keen
Joann Newman

Christopher Pottle
Gerard Salton
Sidney Saltzman
Robert J. Walker

Project Staff at the Aiken Computation Laboratory
Harvard University

Jeffrey Bean
Claudine Harris
Guy Hochgesang
Michael LeskiiiTABLE OF CONTENTS

PagexiiiSUMMARYSECTION ISALTON, G.: "The SMART System ~ Retrieval Results andFuture Plans"
1. Introduction

1-1

2. Experimental Results.

.

.

.

.

.

.

.

.

1-3

3. Discussion and Future Plans

1-5

SECTION II
LESK, M. E.: "Operating Instructions for the SMART TextProcessing and Document Retrieval System"
1. Introduction

.

II-1

1.1.

Processing Summary

II-2

1.2.

Operating Programs

II-4

2. Basic Operating Procedures
2.1.
2.2.

Run Outline
Tape Setup

2.3.

Input Deck Setup

.

H-4

.

.

.

.

.

.

.

H-T

3. Specifications for the SMART Retrieval System
3.1.
3*2.

H-4
H-6

Specifications Affecting Lookup
Specifications Affecting Hirase
Searchingiv

.

.

.

II-7.

.

H-9

••11-10

TABLE OF CONTENTS (continued)

Page
SECTION II (continued)
3.3.

h.

Vector Expansions by Means of ConceptConcept Correlation • • • . • •3A.
Vector Expansion by Means of Concept
Hierarchies
3-5Vector Formation
3-6.
Request-Document Correlation.
3-7*
Document-Document Expansion
3*8.
Other Specifications
Data Input
.
fc.l.
b.2.
fc-3*
h.k.

Natural Language Documents
Binary Documents
DOCTAFS
Relevance Judgment Data

k.5.

Other Instruction Cards

5* Tape Preparation Programs
5-1.
5* 1.1*5* 1*2.
5.1.3*
5*1^»
5*1*5*
5*1.5.1.
5*1*6.
5*2.
5»3«

.

11-12
11-15
II-16
U-17
11-19
11-19
11-20

.

11-20
11-28
11-29
11-29
H-30
11-31

Writing a New library Tape . . • .
Thesaurus and Suffix List Formation . .
Statistical Phrase Dictionary. . . .
Syntactic Suffix List. . . . . .
The Condensed Oramnar Pile
The Criterion Tree Pile
Criterion Tree Input Format
Hierarchy
The Document Tape
The Program Tapev. • n-31
*
11*33
H-35
H-37
II-38
n-fcO
11-41
11-50
11-51
U-52

TABLE OF CONTENTS (continued)

Page
SECTION n

6.

7*

Auxiliary Programs for Use with the SMART
System

11-52

6.1.

THES

6.2.

M)RVAL

11-54

6.3.

SOCCER

n-55.

11-54

A Sample Input Deck

8. Miscellaneous
8.1.
8.2.
9*(continued)

.

11-56
.

.

Size Limits
Timing.

Acknowledgments

.

.

.

.

.

.

.

.

.

11-59
H-59
11-59

.

.

11-60

SECTION III
HOCHGESAN^r, G. T.:"SOCCER - A Concordance Program11

1. Introduction

HI-1

2.

The Concordance

HI-2

A.

Definitions

ni-2

B.

The Input Text

HI-2

C.

Processing the Text

HI-2

D.

The Output Format

HI-6

3. Tape Usage

III-6

A.

Control Cards

HI-6

B.

The INPUT, 0UTPUT, and SMRTAP Tapes
vi.

.

III-6

oJ

TABLE OP CONTENTS (continued)
Page
SECTION I H (continued)
C.
k.

Scratch Tapes

m-7

Control Cards

HI-8

5. Examples of S0CCER Usage.

.

.

.

••

•.

6. Subroutines used Toy S0CCER
A.
B.

IN0T .
SPECTR

C.

CL0CK

•

HI-11
III-13.

in-13
ni-15
•111-17

7. Some Details about the S0CCER Program

HI-17

A.
B.
Appendix111-17
III-18111-19Source Deck Changes
Timing.

•1

SECTION IV
SALTON, G., and LESK, M« E.: "Information Analysis andDictionary Construction"
1. Introduction•IV-1

2. Language Analysis

IV-23. Dictionary ConstructionA)
B)
C)

The Synonym Dictionary (Thesaurus)
The Ntill Thesaurus and Suffix List
The Phrase Dictionariesvii

•

IV-7

•

IV-7
17-15
IV-21

•
.

TABtM #CdMEENTg (&6fftihued)

Page

SECTION IV (continued)
D)k.

The Concept Hierarchy

IV-27

Dictionary Performance

IV-32

A)
B)

The Null Thesaurus
The Regular Thesaurus

IV-33
IV-38

C)

The Phrase Dictionary

IV-U2

5* Automatic Thesaurus ConstructionA)
B)
C)•iv-kkFully-Automatic Mtethods
Semi-Automatic Methods
Sample Thesaurus Generation

IV-48
IV-50
IV-56

6. Semi-Automatic Hierarbhy Formation

IV-59

«

SECTION VLESK, M. E., and SALTON, G.: "Design Criteria for Automatic
Information Systems"
1. Introduction•V-l

2. The SMART Experiments

v-3

3. Evaluation Results and Design Criteria
A)
B)
C)
D)

.

.

Indexing Depth and Document Length
Synonym Recognition
Phrase Processing
Statistical Association Methods.

•viii.

•.

•.

••

7-11
V-ll
V-16
V-19
V-22

TABLE OP CONTENTS (oontiitued)

Page

SECTION V (continued)
E)

Hierarchical Subject Expansion

P)

Manual Indexing

G)

Iterative Searching

H)

Summary.

.

.

.

.

.

v-28.

•.

V-30
V-32

•

V-33

SECTION VI»

RIDDLE, W., HORWITZ, T., and DIETZ, R.:

1«Introduction2.

Principal Methods
A)"Relevance Feedback in an
Information Retrieval System"

•

VI-4

Determination of the Number ofDocuments Retrieved

•VI-5

B)

The Effect of the Correlation Function

C)

Determination of the Relevance Weighting
Factors

D)

VI-1

.

VT-5

•VI-6

Determination of the Value of &VI-8

3#E)
Termination of the Modification Process
Experimental Results•k.

Conclusians

•••.

.

.

.

.

.

.

•.
•. VI-10. VI-lJO.

.

VI-12

Appendix A

VI-16

Appendix B (by. E. M. Keen)

VI-19ix

TABLE OP CONTENTS (continued)

Page

SECTION vn
LESSER, V* R.:"A Modified Two-Level Search Algorithm
Using Request Clustering"

1. Introduction
2.

VH-1

A Modified Clustering Algorithm and aCorresponding Two-Level Search Strategy

•

VII-3

3. Advantages of the Query Clustering Systemk.

.

•.

Design of an Experiment to Compare the Modified
with the Normal Two-Level Search Scheme.
A)
Problem Areas .
B)
Tests to Compare the Effectiveness ofEach Search Procedure
C)D)

Implementation of the Noimal andModified Two-Level Search Schemes
Test Data Base.

.

VTI-7
VII-7
VII-7.

.

.

B)

VH-9
VII-12

5. Actual Comparisons of the Modified versus theNormal Two-Level Searches
A)

VII-5

VII-13

Data Generated for Two-Level Search
Algorithm

VII-13

Data Generated for Modified Two-Level
Search Algorithm

VII-1^

C)

Experimental Evaluation

VH-16

D)

Evaluation Results

VH-25

6.

A New Criterion for Search Effectiveness7.

Conclusions.

.

.

.

VII-27
VII-28

Appendix AVII-30x

TABLE OF CONTENTS (continued)
Page
SECTION V U I
BLOMSREN, G., GOODMAN, A., andKELLY, L.: "An Experimental Investigation of Automatic
Hierarchy Generation1*
1. Introduction

VIII-1

2. Automatic Construction of Hierarchies

.

VHI-2

3. Outline of the Investigation
Appendix A

VTII-12•

VHI-15SECTION DC
BROFFIT, J. D., MDRGAN, H. L., andSODEN, J. V.: " On Some Clustering Techniques for Information
Retrieval"
1. Introduction

ix-i

2. Similarity Measures

IX-k

3. Rocchio's Procedure

DC-5

h.

2X-7

Bonner's Procedure

5* The Experiment
6. Evaluation

IX-10
•

•

7. Results and Conclusions

ix-ll
IX-12xiTABLE OF CONTENTS (continued)
Page
SECTION X
LESK, M. E.: "Design Considerations for Time Shared AutomaticDocumentation Centers"
1. Introduction

X-l

2.

X-2

Principles

3. Methods

X-5

k.

X-9

Practicalities

5* Conclusions

x-17xii

Summary

The present report is the eleventh in a series covering researchin automatic storage and retrieval conducted initially at the Computation
Laboratory of Harvard University, and more recently jointly undertaken
by Harvard and by the Department of Computer Science of Cornell tfaiversity.
From the outset, the design of automatic information systems was ofprincipal concern, and the research dealt specifically with the evaluationof a variety of fully automatic methods for information analysis and search.
This work resulted in the design of an experimental, fully automatic
document retrieval system, called SMART, operating on an IBM 709^ computer,and described in detail in two previous reports in this series, numbered
ISR-7 dated June 1 9 ^ , and ISR-9 dated August 1965«
The SMART system is characterized by the fact that documents and searchrequests are handled in the natural language without any prior manual
analysis, and are processed by one of many different content analysis
procedures incorporated into the system.

Among these are various statisticaland syntactic language analysis methods, and table look-up routines basedon a variety of dictionaries and thesauruses. The dictionaries are normallyconstructed not by committees of subject experts, but send-automaticallystarting with representative document collections for each subject area.
Since it is unreasonable to expect that the documents retrieved by a single
search of the collection should provide adequate answers to all users inall circumstances, iterative search procedures have been used in conjunctionxiiiwith the SMART system which make it possible to obtain improvements insubsequent searches, using feedback information supplied by the users
as a result of earlier searches.
Evaluation results comparing the effectiveness of some of theautomatic analysis and search procedures incorporated into the SMART systemwere first published in report ISR-8 in this series, dated December 196^.
More extensive evaluation output is included in the present report,summarizing the work performed during the fall of 1965 and the first halfof 1966.
The present report contains work in three main subject areas : automaticand semi-automatic dictionary construction, evaluation output based on
results obtained by processing four document collections in three subject
areas, and iterative search experiments based on user feedback.
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 theimmediate future. A complete set of operating instructions for the present
version of the SMART system is presented in section II by M. Lesk.

A

study of this section should make it possible to other interested parties
to run portions of the SMART system on different 709*f installations.
Various aspects of the automatic dictionary construction problem aredescribed in sections III, IV and V H I of the present report.

Section III

by G. Hochgesang contains a description of a very fast concordance
generating program which produces keyword-in-context (KWIC) type output
from ordinary text input. This program is used to generate the concordances which are later incorporated in the dictionary construction system.

xiv

The concordance program described in section H I is presently being
distributed through the SHAEE organization.
In section IV by M. Lesk and G. Salton the complete information
dissemination process is examined with emphasis on the use and construction
by automatic or semi-automatic techniques of synonym dictionaries andhierarchical subject arrangements. One specific proposal for the fully
automatic construction of subject hierarchies is presented in section
V I H by G. Blcmgren, A. Goodman, and L. Kelly.

It is shown in particular

how the structure of the hierarchical arrangement changes as various
parameters are changed.
Section V of this report by M. Lesk and G. Salton contains in summary
form the systems evaluation output produced by the SMART system, based on
extensive operations with four document collections in three subject fields(documentation, computer science, and aerodynamics). One document collectionused in the experiments consists of document abstracts manually indexed bytrained indexers, thus permitting a comparison between the effectivenessof the standard keyword matching techniques and the automatic analysis
procedures incorporated into the SMART system. Another collection wasavailable in the form of abstracts as well as longer summaries, thus
permitting an evaluation of the effects of document length.
Three sections are devoted to a study of iterative search techniques
and user feedback techniques, including sections VI, VII, and IX.

SectionVI by W. Riddle, T. Horwitz, and R# Dietz examines the effectiveness of avariety of relevance feedback procedures in which the users supply to thesystem relevance judgments about documents previously retrieved.

xv

Thesejudgments are then used automatically to generate a new search request
more indicative of user need and preference.

This relevance feedback

process, first described in detail in section III of report ISR-1X), isshown to be extremely effective, and to provide continued improvements
in search effectiveness througjh at least three feedback iterations.
Section VII by V. R. Lesser, and section IX by J. D. Broffitt,
H. L. Morgan, and J. V. Soden describe variations of the multi-levelsearch techniques originally introduced in section IV of report ISR-10.
These techniques drastically reduce the number of comparisons needed
between incoming search requests and stored documents by grouping thestored items, and comparing search requests at first only with a typicalitem for each group.

Individual comparisons are then made only for those

documents included inhighly scoring groups*

The effectiveness of avariety of document grouping procedures used as part of a multi-level search
process is evaluated in section IK.

Section VII, on the other hand,describes an experiment in which requests previously processed by the system
are grouped, rather than documents, and new incoming requests are firstcompared with these request clusters. The search procedure for a new
request is then made to depend on the results obtained with similar requests
processed by the system at some previous time.

The results of section VII

indicate that this heuristic process is useful in reducing search time when
the requests to be processed fall into definite patterns, as they may beexpected to do in an operational situation.
The last section, number X by M. Lesk contains system design specifications for a SMART type system operating in a time-sharing environmentxvi

where many users have access to a central document file, and users
originate search requests asynchronously, and independently of each other.
Equipment specifications and timing considerations are included.

xvii