ISR-7
June 1964.

XII-1

XII.

POSSIBLE TIME-SHARING ORGANIZATION FOR A
SMART RETRIEVAL SYSTEM
Joseph J . Rocchio

1.

Introduction
An important characteristic of traditional document retrieval

techniques is the large amount of feedbacks which the user obtains in
the course of a retrieval operation. For example, when scanning an
index file, the user has an opportunity to recast his query as hecorrelates his original conception of the indexing system with the actual
document citations observed under various index headings. If a retrieval
search is made by a trained intermediary, it is again possible to modify
the search prescriptions by an information exchange between user andintermediary.
In many automatic document retrieval systems the capacity foruser interaction with the system is quite limited.

The advent ofoperational computer time-sharing systems does, however, promise a muchhigher degree of man-machine interaction. The present note deals withsome techniques needed to adapt document retrieval processes to a timesharing environment•

2.

Time-Sharing and Retrieval Systems
To establish the value of real time interaction in mechanizeddocument retrieval, and to investigate the effects of the various types

XII-2of feedback which might be provided to the user, three basic facilities
are required:(1) a time-sharing system to effect on-line man-machinecommunication at a reasonable cost, such as theCompatible Time-Sharing System (CTSS) available at
M.I.T. for the IBM 7094;(2) a flexible set of document retrieval programs which
are capable of incorporating information received fromthe user and of providing alternative retrieval
operations;(3)

a communication-oriented executive routine designed
to provide the man-program interaction and to control
the scheduling of the various processing options ina manner compatible with the time-sharing system*

The retrieval system described in other sections of this report(SMART) satisfies requirement (2) and, since the procedures are programmed
for the IBM 7094, the system is compatible with the M.I.T. CTSS. The
design of an executive routine which meets requirement (3) will then permit
various tests to be made to ascertain the value of close man-machineinteraction in retrieval systems.
Faced with a need for information, a user must determine a strategy
to be used in the retrieval operation. The methods adopted will be
influenced by the userfs individual value judgments, past experience, andthe nature of his needs. In view of the large variety of requirements, a

7
The Compatible Time-Sharing System, A Programmer's Guide,The M.I.T. Computation Center, The M.I.T. Press,
Cambridge, Mass. (1963).

XII-3mechanized document retrieval system should allow for a diversity of
attacks so as to satisfy a large class of user needs*

One importantcharacteristic is the need for continuous feedback between the user
and the system during the course of the various retrieval operations.
By providing a high level of communication with the user, and enabling
him to control the course of the retrieval procedures on the basis of
the information he obtains, the chances of achieving satisfactory
performance will be increased.
The retrieval system described in this report, operating in atime-sharing mode, has the potential of providing the kind of service
mentioned above.

One of the main features of the SMART system is thevariety of techniques which are available for modifications of retrieval
request by involving a number of statistical, semantic, and syntactic
procedures. While at the present time it is not clear that all ofthese techniques are needed in the sense that they form an independent,
mutually exclusive, set (the evaluation of these procedures is one of themain objectives of the research on the current system), it is hoped thatsome subset of these operations will enable effective request modification.

3.

Operational Aspects
The basic retrieval procedure of the SMART system is correlationof a query vector with a set of document vectors. The result of thisoperation is a list, rank ordered by correlation coefficient, of documents.

The user presented with this list, or some portion of it, must

XII-4
estimate the adequacy of the retrieval result with respect to hisneeds.

Since he presumably does not know the complete contents ofthe collection, he is operating under some degree of uncertainty. If
he is not satisfied, or requires additional information to reduce thedegree of uncertainty, a number of alternatives are possible.
Consider, as an example, the following situation:

Supposethat as a result of the first retrieval operation the information
presented to the user consists of N. documents, of which the firstn. are listed in detail (See Fig. 1 ) .

Correlation
Level

Number ofDocuments Retrieved

Printed Document
Citations

High

N

i

n-, highest

MediumN2

n~ samples

Low

Nn^ samples

3

Typical Retrieval Results
Figure 1
The correlation cutoff levels in Fig. 1 are based on previous
experiments and the structure of the request vector, and the numbers^ n l' n 2 ,n 3^ ofPririfced citations depend on N-,, NL, and N~ respectively.

Depending on the needs and values of the user and on his interpretation of the observed results one of the following may apply:(1)

The user is satisfied with the retrieved documents,
in which case the process terminates or the completeset (N-[) of highly correlated references may berequested as output.

XII-5(2) The user identifies one or more documents within
the retrieved set which he deems relevant to his
request, and he would like to have the systemproduce those documents within the collection
strongly related to the ones selected.

In thiscase the system must find a cluster, or clusters,
about elements of the selected set, or alternatively,
must use in turn each of the selected documents asrequests, and produce the intersection of theresulting sets of answers.
(3)

The user desires to alter his request by modifying
his original query on the basis of the observed
citations.

(4.) The user is satisfied with the basic structure of
his request but would like the system automaticallyto expand or contract the set of retrieved documentson the basis of the observed performance.
In all cases where additional system processing is requested,
the user obtains new output results and a further set of alternatives.
There may, for example, be several transformations available for narrowing the scope of a retrieval prescription.

In this case, if requested

to provide automatic restriction, the executive routine might call in
one of these transformations, say a relatively moderate contraction.
If a restriction is again requested, after the original transformation
has been applied, a stronger transformation might be carried out next.
Another possibility is that on the basis of the prior statisticalevidence, the system could decide in each case the most appropriate
transformation to be used to comply with the user's chosen alternative.

XII-6
In any case, by providing the ability to choose from among a sequenceof retrieval operations, based on the information the user obtains while
progressing through the various levels, a more effective document retrieval
service can be provided for a wider class of user needs.

h.

Implementation
Two basic phases are necessary for the implementation of this

proposed system on a system such as the M0IoT0 Compatible Time-Sharing
System•First, those portions of SMART to be used in the time-sharing

version must be altered to conform to CTSS conventions•

In particular,

this requires extensive modification of input-output orders to convert
from tape operation to disk operation0

Since all document processing

and library maintenance programs now provided in SMART need not be
included in the time-sharing versions (e„g., document and library files
may be loaded off-line onto the disks), the effort required for this phase
is not extensive.

Second*, an operational procedure for time-shared

request processing must be developed, and an executive routine must be
written to implement this procedure, and to provide the coordination of
the various request processing subprograms which the current executive(CHIEF) provides in the SMART system.
Two sources of possible difficulty must be mentioned here0One

arises in connection with the syntactical processing sections of thesystem (Sec. VI of this report) due to the size and time requirementsof these programs.

It is not clear at present how many modifications

would be required to incorporate these syntactic programs into a CTSS

XII-7type system.

(This would depend to some extent on the evolution of the

CTSS system in the direction of allowing greater magnetic tape usage.)
Furthermore, it is not determined how the response delay would be
affected by incorporation into a time-sharing system. Initially,
however, due to the wealth of system processes available (other thansyntactic processing), this will not be a serious drawback.
The second potential difficulty arises in connection with thefact that the presently available request processing subprograms alone,
together with the required data files, constitute more than a full coreload. The current system is therefore run as a chain job under the M S
monitor on the regular IBM 7094 • As there is no direct equivalent of achain organization on CTSS, it will be necessary to change certain of
the communication conventions which are implicit in the current system(e.g., leaving data in COMMON between individual chain links).
Two possibilities exist for implementing the kind of sequence
dependent control which the CTSS system allows. One is to provide theuser with a specialized language which is interpreted by the executive
and results in the selection of one of the set of processing options.
The other is to incorporate the effective syntax of such a language
explicitly into the executive, in which case the user is given an
explicit set of alternatives and is told merely to indicate his choice.
This latter approach has two advantages:

first, the user need have noadvance knowledge in order to use the system; and, second, theimplementation of the executive is simpler since explicit executive
control over the branching structure required for path selection can beXII-8maintained. Assuming that this latter approach is to be taken and thatthe necessary modifications can be made to the selected programs of
SMART, the mode of operation may be outlined as follows.
The user, at a remote CTSS console creates a request file on
the disk by use of the built-in CTSS commands (INPUT,EDIT). When theuser is satisfied that the request(s) are error-free the FILE commandis issued, to create a disk file consisting of a sequence of card images
corresponding to the entered text.
At this point the retrieval process may be initiated. The
user, again via the CTSS commands, causes initial configuration programs
to be loaded into core. The executive requests from the user the nameof the query file and then calls the input routine (SEGMNT) to read thisfile into core. After the query has been read, the lookup program isentered.

This program reads in the thesaurus from disks and generates

a concept vector for the query. This vector is written out as a special
file, and the status information concerning the lookup is left in core.
Upon return to the executive the core space required by lookup andthesaurus is released (to improve response time), and the status of thelookup is tested.

If any words were not found in the thesaurus, theseare displayed to the user and he is given the option of proceeding or
modifying his request. If all words were found this fact is reported
and the supervisor automatically proceeds to request document correlation.
This type of proceeding is made possible by providing a special
status file maintained by the supervisor on disk. At the start of eachprocessing step, the first task of the executive is to read this status

XII
file, and to determine from it the function of the current retrieval
phase. Thus, at the end of the lookup phase, the executive and correlation programs are loaded. The executive then reads the status fileand sets up the document and query vectors in core. After the correlation programs generate a query-document correlation matrix on a disk
file, the executive can release the excess core space and present theresults to the user. Again, the user is given a set of alternatives
applicable at this point. When a choice is made by the user, theexecutive updates the status file and chains into the LOaDGO CTSS
command with the appropriate parameter to load the set of programs
required for the next processing option. Thus, at the termination ofeach processing phase, the executive sets up the data for the next
phase chosen by the user, and then causes the appropriate programs to
be read in from the SMART program files on disk*
A rough block diagram of this procedure is given in Flowchart 1.
Additional effort is required in designing detailed specifications, andin studying the feasibility of such a system organization*
A hypothetical example of retrieval sessions at a CTSS console
is given in Appendex A.

XII-10START(Manual)READ STATUS FILE
(INITIAL STATUS)

REQUEST QUERYFILE NAME

GT3S
SUPERVISOR-*ASETUP TEXT IN
CORE FOR LOOKUPCALL LOOKUPk-W

RELEASE LOOKUP«e
CORE SPACELOOKUP V

READ THESAURUS FRCM DISKLOOKUP TEXTWRITE QUERY FILE>A

ANY WORDSNOT FOUND?

Yes
A*r-

DISPLAY TO
USERNoINDICATE-»-A

Possible Time-Sharing Organizations for SMART
Flowchart 1

XII-11

ASK USER IF
GO AHEAD OR
NEW QUERY

GO AHEADSET STATUS TO
CORRELATECALL FOR LOAD OF
CORRELATION PROGRAMS-*ASTART (automatic)

READ STATUS FILE
(CORRELATE)

ii
READ IN DOCUMENTAND QUERY VECTORSRELEASE CORE SPACEAND DISPLAY RESULTS

WRITEOUT REQUESTDOCUMENT CORRELA-I
TION MATRIX-^A

Flowchart 1 (continued)

XII-12DISPLAY ALTERNATIVESTO USERPRESENTMORE
OUTPUT->AA <-SET STATUSTOHIERARCHY

REQUEST DOCU-]KENT NUMBERS

CALL FOR LOAD
OF HIERARCHYPROGRAMSSET STATUS
TO
CLUSTERCALL FOR LOAD
OF CLUSTERPROGRAMS

Flowchart 1 (continued)-*AXII-13APPENDIX A

AS a further illustration of the type of retrieval service theproposed time-sharing system might provide, an example is given below
of a hypothetical session of a user at a CTSS console• The retrieval
results shown are based on initial experiments with the present SMART
system; the document file used for these experiments consisted offifty document abstracts taken from the collection contained in the
IRE PGEC Transactions.
In the description below user input is capitalized and indented.
Computer output from CTSS or the SMART system appears in lower case.
Explanatory notes are enclosed in parentheses.
(After logging in, the user is ready to type in his query-Atthis point the conversation is between the user and CTSS.)... INPUT
00010 ... *TEXT ANALOG-TO-DIGITAL
00020 ... ANALOG TO DIGITAL CONVERSION. DEVICES ANDTECHNIQUES FOR THE CODING
00030 ... OF ANALOG INFORMATION.
00040 ...

IT

(puts CTSS in manual input mode)(The first line identifies the query to the SMART system. The user now
creates a disk file named WUERY by the following CTSS command.)... FILE QUERY DATAXII-U(At t h i s p o i n t r e t r i e v a l may be i n i t i a t e d j t h e u s e r c a u s e s l o a d i n gof t h e i n i t i a l program segment.). . . LOAD SMART. . . START(Responses t o t h e u s e r from t h i s p o i n t a r efrom t h e SMART system.)e n t e r t h e name of t h e query f i l e. . . QUERY
all words found by lookup
retrieval results by query-document correlation:
query:

analog-digital

answers:
correlation .66, 2 documents
296

a high-speed analog to digital converter

132

logical synthesis of some high-speed
digital comparators

correlation .55* 6 documents, one of which is:229

matrix programming of electronic analog computerscorrelation .44* 6 documents, one of which is:62

on programming of arithmetic operations

options:
to alter query type *end* and use ctss editing commands.
For display of all answers withcorrelation above N type *print N*
for expansion or contraction by hierarchy
type *hier expand* or *hier contract*for document clustering type *clust n-, ,n *with as many document numbers as desired
separated by commas.
to terminate retrieval type *end*.
... PRINT .5
additional answers with correlation above .5
322

usea of compiler programs to solve power problems

289

stable high-speed digital-to-analog conversion forstorage tube deflection

263

machine language in digital computer design

255

three levels of linguistic analysis in machinetranslation

options:same as those above.
... CLUST 296, 289
document cluster of 296, 289:
cluster contains documents 296, 289*
options:same as those above. . . END