IV-1

IV. The Cornell Programs for Cluster Searching
and Relevance Feedback
E. Ide, R. Williamson, D. Williamson

1. Design Criteria
For the present write-up, it is assumed that the reader is familiar
with the SMART project, originally implemented on an IBM 709*+ at Harvard [l,2].
When this information retrieval system was rewritten for a CDC l66k at Cornell,
the programs available at Harvard could not be used directly.

At that time,several design decisions for the Cornell system were made:a.

To continue to run the text analysis programs at Harvard [2],and to rewrite only those programs dealing with document
abstracts and queries as numeric vectors;b.

to concentrate on two major areas at Cornell (the implementation of Rocchio's clustering algorithm [3] and ofvarious relevance feedback algorithms [3*^3)J

c. to write these programs to handle collections as large as
the 1^00 document, 225 query Cranfield collection;d.

to make the resulting system available for use and forexperimental reprogramming to students on one-semester
projects.

2.

Basic Cornell System Organization
In order to implement the last of the points mentioned, the system

was designed using many small routines. This modular structure adds a large
degree of flexibility. An experimenter can generally achieve his purpose byIV-2

modifying one or more small, self-contained subroutines rather than byhaving to rewrite a subsection of a large, complex program.

The system

subroutines communicate through COMMON blocks, and the common systemvariables are rigidly defined for the experimental programmer.
cedure minimizes errors and simplifies debugging.
expansion of the system.

This pro-Further, it facilitates

Often a new program can be built around a set ofbasic routines already available in the system.
Most of the subroutines are written in Fortran rather than in basic
machine language. The sacrifice of speed over assembly coding is slight withthe fast Fortran compiler available on the Control Data l6ck*

This decisionpermits an easier modification of the code and makes conversion of the system to other computers more reasonable.
The large document collection with which the system was eventually
to be used (criterion C) precludes the internal core storage of all thedocument vectors simultaneously, under any packing scheme. Thus, it isnecessary to put the documents onto a tape to be read serially, with advance buffering to overlap computation and tape movement as much as possible.
Since it is desirable to use preliminary and cross-check runs on various different collections, it was felt that it would be easiest if all document
collections were to reside on one system tape, rather than on many different
tapes.

In addition, production runs referencing more than one collection

would be much more convenient to run, since only one tape would be needed.

3. System Implementation of Rocchiofs Clustering Algorithm
In future libraries, collections of fifty to one-hundred-thousanddocuments are contemplated.

For collections of this size, the linear

search schemes used for testing purposes would take an unmanageably longtime, even with batch-processed queries.

If any direct user interaction

were desired, the time cost of a linear search would be prohibitive indollars, and the user probably would not be content to wait for up to
thirty minutes, the time required to perform a fast linear search on fiftythousand vectors.
A clustering system hopefully can group similar documents together,and replace the group of documents usually correlated by a single vector
representing the general area covered by those documents.

If one-hundred-thousand documents could be usefully grouped into one-thousand groups of twothousand documents each (it is often desirable to place a document in morethan one group), only about three-thousand comparisons, as opposed to onehundred-thousand, would be needed to find most of the documents relevant toa given query.

This reduction of search time and money is desirable, andhence considerable efforts are being made to generate effective clusteringalgorithms.
A clustering algorithm is useful only if the resulting documentgroups permit a more efficient search, while maintaining the same quality ofresults provided by a full search of the document collection.

Thus, there

are two separate problems associated with clustering algorithms; that ofclustering the collection into groups, or "centroids", and that of evaluating
the quality of the search results using these centroids.
blems is handled by a separate system subroutine.

Each of these pro-The first subroutine,

CLUSTR, groups the documents, and the second, CENVAL, evaluates these groupings,or evaluates any other centroid groupings previously calculated.

IV-b

Subroutine CLUSTR forms clusters of documents for two-level searches
using Rocchio's algorithm. [3] The routine successively considers eachdocument in a collection as a possible root of a centroid.

It then correlates

this document with all other documents in the collection, and applies Rocchio's
density test to the resulting ranked documents.

If the root passes the den-sity test, it is considered to be a centroid root, and the documents which
will define the centroid are chosen from the top of the ranked list. A"centroid vector" is then formed, which is the center in the document spaceconsisting of the defining documents.

All documents are re-correlated withthis centroid vector and additional documents to be included in the centroid
are chosen from the top of the new ranked list. A user option allows thecentroid vector to remain unchanged or to be redefined at this time to include all documents in the centroid.

Another option determines whether

these documents now included in the centroid are dropped, or not dropped,from the document space. The program then picks a second possible rootand repeats the above process, until all possible centroid roots have beentried.

If, at this point, there are documents that are not included in any

centroid, they may be inserted into the cluster whose centroid root is mosthighly correlated with them.

In this manner, CLUSTR places all documents

in groups represented by their centroid, as seen in Fig. 1.

Parameters for

Rocchio's density test, number and size of clusters desired, and several
other experimental variables are controlled by the system user.
Subroutine CENVAL performs up to four searches of the document collection. One of these is a standard full search for comparison purposes.
The other three runs use the centroids, as generated by a CLUSTR run, forthe given collection. To search the collection using the centroids, a queryIV-5c}

CLUSTRII

Have all documents been seen?

NOlYES

1=0
Blend each unclustereddocument into centroidof highest correlation

1 = 1 + 1

Ith document apossible centroid
root?

iISOReturnj YES©

Correlate Ith documentwith all documents thatcan enter the centroid;rank these documents*

I

Redefine centroid
vector? (user option)

NOIYES

Sufficiently dense(by density test)?

NORe-form centroid
vector using all
documents in centroid

IYESI

Select documents todefine centroid ofcluster

Drop documents inNO
centroid? (user option)

IiIYES

Form centroid vector
Documents in centroid
can no longer enter
other centroids

Re-correlate centroid
vector with all documents and rankI

Write centroid
on auxiliary tape

Select documents tobe in centroid

6Flowchart for Routine CLUSTRFig. 1

IV-6

is first correlated with each centroid, and the centroids ranked according
to this correlation.

Then for each of the three centroid searches, a user-

supplied number of these centroids are pulled off the top of the ranked
list, and the documents included in these centroids are ranked and listed.
The performance measure used to evaluate the "quality" of these searches is
the recall-precision graph normally used by the SMART system [5]- A recallprecision graph is plotted for each query, and average statistics are given
for the set of queries. A flowchart for the CENVAL routine is shown in Fig. 2.

4«

System Implementation of Relevance Feedback
Relevande feedback is a process whereby a poor query can be im-proved using feedback supplied by a user after he is shown a small fractionof the documents in the system.

The user first submits an initial draft ofhis query, which is processed by the system. The user is then given a few
documents that the system believes to be most relevant to his initial request. The user indicates which of these documents are relevant, and which
are non-relevant

to his needs. The system uses this information to modify

the original query, and searches again. This process can be iterated asoften as desired.

The relevance feedback process is often justified bynoting that if the query is not stated in terms similar to those used formost of the relevant documents, the system may, nonetheless, be able tolocate one or two of the relevant documents. These documents may be more
highly correlated with the remaining relevant documents than the initialquery, and may therefore provide valuable input for a query modification
procedure.

IV-7c I

CENVAL}

Read ML, N2, N3, andother user options .

II

1=0
I = 1+1

YES
Print average results

Have all queries
been evaluated?

IIcReturn3NO

Search full document
collection

Search centroid
vectors

Search documentsin the first Nlcentroids

I"Search" means
correlate each searched1
document (or centroid) |vector with query I •and rank the documents '(centroid vectors) "by |their correlation,Search documents inthe first Nl + N2
centroidsSearch documents inthe first Nl + N2 +N3 centroids

Print results forquery I

Flowchart for Routine CENVAL
Fig. 2

IV-8

The relevance feedback algorithm described is implemented in theCornell system by subroutine RELFBK. RELFBK first performs an initial
search of the collection.

Three feedback iterations, each altering thequery, are then performed for each query.

A feedback iteration first alters

the query by combining the weights in a given number of the documents mosthighly correlated with the query, and then performs a new complete search.
By means of control cards, the experimenter can add to the query those concepts present in the relevant documents, or subtract those concepts which
are present in the non-relevant documents. The number of documents recovered on each iteration (that is, the number that might be used to update
the query) can also be varied.

(See Fig. 3)

5. Further Details of the Cornell System Organization

A) Routines Available Without User Reprogramming
A basic control routine was written to permit execution of same
standard jobs. This routine, named EXEC, can be used in most cases without
modifications to execute most possible sequences of desired procedures. TheEXEC routine reads control cards, each containing the alphabetic name of oneof the system subroutines. Upon reading a control card, EXEC calls thenamed subroutine, which executes and then returns control to EXEC so that
another control card can be read. The basic system jobs listed below canbe executed with control cards through the EXEC routine:a.

START - initializes a new document tape with no collections.
This routine is used before making a new collection tape;cIV-9>iRELFBKRead ML, N2, N3 andother user options

II

1 = 0

Have all queries been
evaluated?

YESI
I

woPrint average resultscReturn

I = 1+1

JSearch full document
collection with initialquery II

Modify query according
to user options using
relevance judgments ofthe first Nl documents
in initial search
results

ISearch full document
collection with firstmodified query

I

Modify query using
relevance judgmentsof the first N2
documents in first
iteration search
results

I

Search full document
collection with second
modified query

I

Modify query using
relevance judgmentsof the first N3
documents in second
iteration search
results
Flowchart for Routine RELFBK
Fig. 3

Print results forquery ISearch full document
collection with third
modified queryIV-10b.

RESTRT - initiates the use of a document tape which does
contain collections. Either START or RESTRT must be thefirst control card in each computer run;c.

CLUSTR - groups the documents (or queries) in a given
collection using Rocchio's clustering algorithm (see part 3);d.

CENVAL - searches the documents in a given collection using
document clusters created by CLUSTR*(see part 3);

e. RELFBK - searches a given collection of documents using
a given set of queries, providing up to three iterationsof relevance feedback (see part k);f.

MAKTAP - reads a document (or query) collection from cards
and adds it to the document tape; MAKTAP also provides andstores on the document tape summary statistics for thecollection, including the maximum concept number and maximum weight of each document, and the maximum number ofconcepts in any document in the collection;

g. LISTAP - lists a given document or query collection fromthe document tape;h.

TIME (I) - prints the time recorded on the internal computer clock numbered I; if I is negative, TIME sets clock |l|to zero. This routine is used to obtain the execution timeof any section of the run.

i. MASTER - an undefined system name to be used to call a userwritten subroutine from EXEC without modifying the existing
system subroutines.

B)

Service Routines Available to the Experimental Programmer

Several input-output and other service routines are available to theexperimental programmer.

These routines are also used by the basic sub-routines listed in section A above. All routines in section A can also becalled by user-written routines.

IV-11

A set of special subroutines, listed below, is used to handle allmovements of the document tape (DOCTAP). These routines provide bufferingand are efficient in tape movement.

Further, if the experimental program-mer uses these routines exclusively for all DOCTAP movements, the documenttape is protected from unintentional change by his routines.

a.

START, RESTRT, MAKTAP, LISTAP. (see section A)b.

NEWCOL - locates a given document (or query) collection on
DOCTAP, positioning the tape to read the first document ofthe collection; it also reads and stores in COMMON the firstrecord of the collection, which contains collection parameters used by other subroutines;c.

LOCDOC - reads a given document within the collection thatwas selected by the last previous call to NEWCOL;d.

DOCMOV - a fast basic machine language subroutine that moves
DOCTAP forward or backward over a specified number of end-offiles, which serve to demarcate collection boundaries.

It isused by the other subroutines that move DOCTAP.
A set of anuxiliary tape subroutines is available to be used for
temporary storage of data on tapes other than DOCTAP.
a. WRITE (VEC) and READ (VEC) - single-channel double bufferedtape reading and writing routines;b.

CRDCEN - generates a centroid tape from the documents,
specified on cards, defining a centroid (document group)
vector, and from the documents contained in that centroid.
This routine makes it possible to reuse the clusters resulting
from a run of CLUSTR.

IV-12c.

CENDOC - transfers a set of document vectors from anauxiliary tape to DOCTAP, and defines these vectors as a new
document collection; this routine is used to store the centroid vectors generated by CLUSTR on DOCTAP, to be usedlater for centroid clustering or for re-evaluation of different two-level search schemes;d.

DOCCEN - transfers a collection from DOCTAP to an auxiliary
tape; this routine is used to reverse CENDOC so that storedcentroid vectors may be reused•

Other important service routines available are:a.

INNER - forms the inner product (correlation) of two documents
in core storage. Any one of three different correlation coefficients can be used;, b.

SRTUP and SRTDWN - sorts a system vector (called CORR) innumeric (SRTUP) or inverse numeric (SRTDWN) order. These
sort routines are high speed routines and use n log n locations in CORR, where n is the number of items to be sorted;c.

MKITAP - correlates each document in a centroid (read froma tape of centroid vectors) with the centroid itself, andgraphs the distribution of documents within a centroid;

In addition, a system of associated printer-plotter routines isavailable which can be used to print output graphs with user-controlled
scale and plotting characters.

17-13

References[l]G. Salton et al., Report No. ISR-9 to the National
Science Foundation, Harvard Computation Laboratory,Cambridge, Mass., August, 1965*[2]

G. Salton et al., Report No. ISR-11 to the National
Science Foundation, Department of Computer Science,Cornell University, Ithaca, New York, June, 1966.

[3]

J* J» Rocchio, Jr., Document Retrieval Systems —Optimization and Evaluation, Report No. ISR-10
to the National Science Foundation, Harvard Computation Laboratory, Cambridge, Mass., March, 1966.

[k]W. Riddle, T. Horwitz, and R. Dietz, RelevanceFeedback in Information Retrieval Systems, Report
No. ISR-11 to the National Science Foundation,
Section VI, Computer Science Department, Cornell
University, Ithaca, New York, June, 1966.

[5]

G. Salton, the Evaluation of Automatic Retrieval
Procedures - Selected Test Results Using the SMART
System, American Documentation, Vol. 16, No. 3, July,
1965, pp. 209-222.