IX-1

Interactive Search and Retrieval Methods
Using Automatic Information Displays
M. E. Lesk and G. Salton

Abstract
Presently available information storage and retrieval systems do
not produce retrieval results which will satisfy the information needs ofall potential users.

Interactive search methods using console displays

and conversational computing methods promise to furnish retrieval results
which are far superior to those achievable by conventional procedures. In
the present study, various interactive search strategies are used in conjunction with the automatic SMART document retrieval system, and an attempt
is made to evaluate the effectiveness of each method as part of a retrieval system.

In particular, the usefulness of each method in retrieving

wanted and rejecting unwanted items is discussed, as well as the cost of
the user-system interaction in terms of additional user effort and computer time.

It is found that for all but the most experienced users, auto-

matic methods requiring little user effort are preferable to more sophisticated procedures which may produce somewhat better retrieval results at
somewhat higher cost.

1.

Introduction
Throughout the world, the design and operation of large-scale in-formation systems has become of concern to an ever-increasing segment of
the scientific and professional population.

Furthermore, as the amountand complexity of the available information has continued to grow, the use

IX-2

of mechanized or partly mechanized procedures for various information storage and retrieval tasks has also become more widespread.

While a number of

retrieval systems are already in operation in which the search operations
needed to compare the incoming information requests with the stored items
are performed automatically, no systematic study has ever been made of theuse of man-machine interaction as a part of a mechanized text analysis andinformation processing system.

Specifically, the recent development of highcapacity random-access storage mechanisms and conversational input-output
consoles should permit a rapid interchange of information between users andsystem.

Such an interchange can than be used to produce improved search for-mulations, resulting in a more effective retrieval service.
The present report describes and evaluates the performance of avariety of such interactive search and retrieval procedures in which information supplied by the user population is taken into account in an attempt
to achieve improved system responses.
system interaction are possible.

Several basic approaches to user-

On the one hand, an attempt can be madeto construct refined query formulations, using dictionary displays and similar methods, before any file search is actually attempted.

On the other

hand, an original query can be processed when it is first received, and aquery reformulation attempted after the results of an initial search are
actually available.

These two procedures, termed pre-search and post-search,

respectively, can in turn be executed in several different ways:

either thesystem assumes most of the burden of the query reformulation through an
automatic query alteration process, or, the users themselves can rephrase
their queries using the available automatic displays.

In the latter case,IX-3

the skill of the user population becomes a more important factor.

The

stored data most important in the pre-search methods might include synonym
dictionaries and thesauruses, word frequency statistics, and lists ofsignificant words; the post-search information, on the other hand, consistsof the titles, abstracts, or texts of documents retrieved by a previous
search process.
The investigation of the various interactive search and retrieval methods is carried out with the help of the automatic SMART document retrieval system {1,2].

The SMART system is a large computer-based

retrieval system capable of performing a variety of different text analysis, search, and retrieval operations.

Completely automatic text analysis

and information searches are made using several different analysis methods
and search strategies.

Among the main text analysis procedures are syno-

nym recognition, word disambiguation, phrase recognition, statistical term
association, and hierarchical text expansion methods.
The effectiveness of the various analysis and search methods
may be evaluated by using for this purpose the familiar recall and precision measures, representing respectively the proportion of relevant material actually retrieved, and the proportion of retrieved material actually
relevant.

Ideally, all relevant items should be retrieved for the user,

while at the same time, all nonrelevant items should be rejected, thus
leading to a system where both recall and precision are equal to 1.

The

performance effectiveness of an operating system can then be estimated byaveraging recall and precision figures over many searches and comparing
the results with the ideal situation where recall and precision are equal

IX-4

to 1.

The SMART system automatically generates for each search a set ofrecall-precision graphs first introduced by Cleverdon [3] , and also includes
procedures for performing computations of the statistical significance ofthe results. Evaluation data for a wide variety of automatic text processing,search and retrieval methods have previously been published [4].
In addition to the recall-precision data which reflect the capabilityof the system to deliver to the user the information he requests, it is also
important in an interactive computing environment to take into account theamount of effort required from the user to obtain satisfactory results.
Thus, the standard performance of fully-automatic search and retrieval operations must be compared against the improvements obtainable through, interactive procedures at additional cost in user effort and computer time.
In the remainder of this study, the effectiveness of various typesof interactive search methods is examined, including both pre-search andpost-search methods, and semi- or fully-automatic query reformulation procedures.

The results are compared using, in each case, the evaluation

methods incorporated into the SMART system.

Construction principles arethen derived for future information services designed to use man-machineinteraction during the search process.

2.

Fully-Automatic Retrieval
In the SMART system, various fully-automatic language analysis pro-cedures are used to normalize the text of incoming search requests and of
stored documents.

The normalized, reduced forms of the information items,

consisting generally of weighted "concept" numbers, are then compared, andIX-5

the document representations which are most similar to the request representations are extracted from the file as answers to the queries.

The lan-guage normalization procedures incorporated into the SMART system range
from simple word stem matching methods to more sophisticated processes using
stored synonym dictionaries and hierarchies, as well as statistical and syntactic analysis methods [1/2].
Three of the simplest language analysis methods, known, respectively,
as word form, word stem, and thesaurus processes may be described as follows:a).

in the word form, or suffix 's', process, no word
normalization in the proper sense is used at all,and the original words with only the final ' s' removed(to confound, for example, "book" and "books") arecompared directly;b)in the word stem method, the original text words are
reduced to word stems by a suffix cut-off process
to confound words like "analyzer", "analysis", "analyzed",and so on, before the comparison between queries anddocuments;c)in the thesaurus process, each word stem is looked
up in a synonym dictionary, or thesaurus, where it
is replaced by one or more so-called concept numbers,
representing synonym classes;

the concepts extracted

from the thesaurus are then matched instead of theoriginal word forms or word stems.

In all analysis methods, the terms are normally weighted, using word frequency and other criteria, before a comparison is made between stored documents and search requests.

IX-6

An excerpt from a typical, manually constructed thesaurus is shownin Table 1.

Three of the synonym classes defined by the thesaurus mapping

are shown in the right-hand side of Table 1.

Concept class 346, for example,

contains words specifying objects which fly; category 345 lists words associated with weather.

If a request were made, asking"do planes fly when the weather is bad?"the system would retrieve a document stating"proper meteorological conditions are necessary for the
successful piloting of aircraft",since both document and query would be assigned the concepts 345 and 346.
The handling of ambiguous words in the thesaurus is exemplified by
the entry for "wind", which could be either the noun, referring to weather,or the verb, indicating a method of constructing loops or coils. The tableshows that "wind" is in two categories, 345 and 233. 345, containing also
"weather" and "atmosphere", represents the noun, and 233, which contains
such words as "winding" "wire-wound", and "solenoid", represents the verbal
meaning.

Whenever "wind" appears, both 345 and 233 will be entered into theconcept vector.

Because the word is considered ambiguous, the weight will

be divided between these two categories; each will receive half of the weightassigned to "wind".
It should be noted that the thesaurus entries may consist of wordstems, so that "meteorolog" suffices to look up "meteorology" and "meteorological".

If desired, however, suffixed forms of a word may be entered in

IX-7

Alphabetic Order
Concept
Code

Word
Wide

438

Will

32032

Numeric Order
Concept
Word
Code

SyntaxCode001 043 040

344

obstacletarget345

atmospheremeteorolog
weather
wind346

aircraft
airplanebombercraft
helicopter
missileplane

009 070 043 044 049Wind

345 233070 043

Winding

233

070 136 137

Wipe

403

043 070

Wire

232 105070 043

Wire-wound

233

001

Thesaurus Excerpt
Table 1

Query Alteration Process

Explanation

Pre-Search .
1.

Repeated Concepts

User chooses query terms to be repeated for emphasis

2.

Thesaurus Display

User chooses terms obtained fromthesaurus display to update query(with or without time restrictions)3.

Word Frequency

User looks at display of word frequency information before updating
query

4.

Source Document

User looks at display of source
document before updating

Post- Search

1

5.

Title Display

User looks at titles of first five
retrieved documents before updating

6.

Abstract Display

User looks at abstracts of first
five retrieved documents

7

Relevance Feedback

Query is updated automatically using
relevance judgments supplied byuser following an initial search'

Combined Methods
8,

Abstract plus Thesaurus

User looks at pre- and post-search
information

Typical Query Updating Methods
Table 2j

IX-8

the thesaurus; this has been done with "winding", since if only "wind" werein the dictionary, "winding" would also be treated as ambiguous, but thepresence of "winding" in thethesaurus makes it possible to identify"winding" in the text with category 233 only.
The high concept number identifies "will" as a so-called common
word, not to be used for content identification.

The syntax codes shownwith the thesaurus entries in Table 1 are not used in the simple automaticthesaurus process.
Since the fully-automatic thesaurus process based on concept number
matching is often an effective analysis tool, more sophisticated language
normalization methods may not normally be required in an operational retreival
system.

3. User Interaction Through Pre-Search Methods
One of the main hopes in obtaining a retrieval performance whichgoes beyond that presently reached under normal operating conditions is
to include the customer in the search process.

In particular, fewer errors

are likely to be made if the information obtained from the users is not
restricted to the search request proper, but is supplemented by a varietyof special user indications, or by evaluation data about the acceptabilityof items previously retrieved by the system in answer to the search requests.
User-system interaction is now current for many computer application, often
implemented by special input-output console devices, with the help of
operating systems which enable the system to render more or less simultaneous service to a large class of users.

IX

In an information retrieval environment, user interaction may takethe form of simple dictionary display routines which can be used to present
to the user selected dictionary excerpts as an aid in formulating the original search requests, or in reformulating queries which were originallyinadequate [5,6].

Alternatively, more sophisticated methods may be used inwhich the reformulation of the search requests is automatically performed
based on feedback information obtained from the user population [7,8],
The conceptually simpler methods are the pre-search procedures
which are based on term and dictionary displays of previously stored information.

In each case, a user would look at the displayed information and,based on the available data, would decide before any file search is actuallyattempted how his query could best be reformulated in order properly toreflect his information needs.

The following types of pre-search informa-tion could be displayed for this purpose:a)lists of terms included in the user's original search
formulation together with word frequency information
giving the frequency of use of each word in one ormore of the stored document collections;b)thesaurus excerpts corresponding to the terms includedin the user's search formulation, and consisting, foreach of the originally available terms, of a complete
thesaurus class, including synonyms and other terms
related to the original;c)titles and abstracts of source documents, that is, ofdocuments originally known to the user as relevant to
his search query (the intent of the user is then to
retrieve new documents similar to the source items).

IX-10The principal differences between fully-automatic retrieval and retrieval
using pre-search interaction are summarized in the flowcharts of Figs. 1(a)and 1(b).

The pre-search requires the generation of a computer display

followed by a manual choice of terms on the part of the user during thequery formulation process.
The display of word frequency information is designed to inform theuser of the characteristics of the vocabulary which may be used to express
his information needs. Thus, if a user notices that many of the terms
included in his search request are general terms with a very high frequencyof occurrence in the stored document collection (for example, terms such as"computer" and "automatic" in a collection on computer science), he may
decide that it is wise to delete these terms from his query so as to prevent the generation of high query-document correlations for many nonrelevant documents. On the other hand, the user may decide to emphasize manyhighly specific, low-frequency terms by repeating them in the query formulation.
A thesaurus display can be used for manual query updating by requesting a printout of the complete thesaurus classes corresponding to eachterm included in the original query.

Consider, as an example, a query

dealing with the "contraction of satellite orbits", and assume that the user
signifies that he is interested in the "satellite" class. The computer
might then type out terms such as
Discoverer, Sputnik, Vanguard, Cosmos, Moon, rocket,
trajectory, countdown, drag, telemetry, etc.

IX-11After studying the display, the user might decide that his original query
formulation had been insufficiently specific, and the query might then bealtered by addition of the terms "Discoverer, Sputnik, Vanguard, Cosmos,
drag, and telemetry".

The other displayed terms would, however, be re-jected as not being germane to the search topic,

A second expansion

might begin by typing in the term "drag", and then considering the newdisplay of terms related to "drag".
Thesaurus displays are also occasionally useful for the removalfrom the query formulation of incorrectly used and ambiguous terms.

For

example, a user interested in information retrieval who identifies his
search topic as "IR" might discover that the thesaurus display produces
a list of synonyms in the area of "infra-red spectroscopy".

As a result,

the term "IR" would, of course, be removed from the search formulation.
The use of thesaurus displays for manual query updating provides
an opportunity for a selective choice of synonym and related terms.

Thatis, the user can choose some terms to be added to the original query, andothers to replace already existing ones in an attempt to improve searchprecision.

On the other hand, the automatic thesaurus process operates

less selectively and provides synonym recognition by the standard process
of automatically replacing the word stems originally included in the searchrequests and documents by the corresponding concept class numbers extracted
from the thesaurus.

The automatic thesaurus process is thus designed tonormalize query and document statements by generalizing the respective
formulations rather than by making them more specific.

Such a process may

be expected to improve recall, since more relevant documents could now

IX-12

4)
-P rH
X O

O

-p

CD
-P rH
X O
CD > i

O
•P

S &

/K
n
0 £

X CD
CD

o

> i -P
o
ft

O

£
CD
H -P
CD W
>i
0}

CD
>i -P
U fd
<D TJ
2
ft

CD
^ -P
CD TO
TO > i

w an

D

/|\

- p ft
fd •P

•S3
O
*H
-P
fd

/N
o

CD
-P
rH

A

W

•H
<H
•H

TO
TO
CD
O
O
JH
ft

0

/\
rd
O

o
M
rd
CD
if)

ufd a)o

ft
H
CD

O

o

/\

fd

.5 &

ft

t P CD
H Ot
O

p

'rH
IW
•H

fd
CD
CO
I
-P
TO
O
ft

-P
fd

CX

O
H
-P
fd

m ftu

rH

G

1

0

CD

o
2

-H
-p
fd
'

o
O
Q

CD
O

M

3

a*w o
to

•P
fd

Q

M
0 •P
C

0

>1

fd

TO CD
3 £

rH

p
ft M U
TO 3

fd 0
Q

•H

Q

TO

7R

3

T3
CD

U
0

ftu
rC

u
5M
fd
CD
OQ

W
TO
CD
O
O
U
ft

£
U
H
fd
CD
W

-P
TO

O
ft

H3

A

G
rd
i

<D
U
ft

tP

c
> i -H
H -P
CD fd
CM ft
D

T5

A
1
CD

W
CD

H
> i TJ
fd CD
rH >
ft CD
TO - H
-H H
Q -P

"TF

o

TO
TO

CD

A

CD

c:
o

-r4

X^ n
W Q -P

u

.3
U
U
fd
CD
W

fd CD

tf 3

fd

•H
•P
fd

CD

1 CD
CD
d

G
U
o ^ o fd
•H O Q -P-P
fd
fd >i TJ Q
£ fd Q)-H rH >£ ft CD

o -p

A

-p
T3

c

C
fd

o

A
-^

TJ

CD
> i -P
^ fd
CD ^
5
ft
Ol p

CD
U
U
3 fd
O -P
w cd
Q
O •P
>i
G
fd TO 0)H 3
g

ft u 3
TO
H
Q

3
fd
TO

A

fd

fd

-S &

•H

t n CD
-H
3
U CX
O

'u a
o

H

tn CD

U
O
Q

TO
CD

3

na
a)
rj
0

ftu

^

o

H

V4
fd
CD

-H

en

ft

CD

is
•P
fd

ter

fd
£

-P

•

tn

IX-13match the query statements and could thus be retrieved in answer to therespective search requests.
Obviously, the manual query updating methods using thesaurus displays places a considerable burden on the user, since he is forced to consider a large number of alternative possibilities before eventually making
a move.

Moreover, the choice must be made before a search has actually

been performed, at a time when he cannot know as yet how well the machine
will perform with any potential query formulation.
A comparison of the effectiveness of manual and automatic thesaurus
procedures is contained in section 5 together with the other evaluation
output.

4.

User Interaction Through Post-Search Methods
The post-search methods are those applicable after an initial search

has first been performed.

In such a case, one or more documents will al-

ready be available, including in particular those items which were initiallyjudged to be most similar to the search requests.

These items can now be

used in a manner analogous to that previously utilized for the thesaurus
displays.

Specifically, the titles, or abstracts, of the first few

retrieved documents can be examined, and document terms which appear toreflect the wanted subject area can be added to the query statement, whileambiguous and unwanted terms can be removed.
Consider, for example, the previously cited query dealing with the"contraction of satellite orbits", and assume that the first two retrieved
items are entitled "Discoverer satellite and South Pacific splash down",

IX-14and "The moon and the tides"• A user could now proceed to add "Discoverer
satellite" to the original query, but could avoid the addition of "South
Pacific".
The document feedback expansion may be even more difficult to carryout than the dictionary display procedure, since the user is forced tomake sophisticated decisions using relatively large text excerpts. Thus,
whereas the dictionary display procedure can often be performed in lessthan a minute per query, approximately four minutes are required on the
average for the use of five typical document abstracts. Furthermore, thedocument expansion process also entails a higher cost in machine time andstorage space than the dictionary display, since document abstracts innatural language form constitute a much greater bulk than dictionary excerpts.

In addition, an initial retrieval run must first be made before

document feedback can be used.

On the other hand, a stored dictionaryneed, of course, not be available for the document feedback method.
Another post-search method is designed particularly for those users
who do not wish to assume the burden of query reformulation themselves.
For such users, an automatic relevance feedback method is available which
requires only a minimum of interaction with the user, since most of theburden is placed on internally stored routines [7,8,9,10].

Specifically,an initial search is first performed for each request received, and asmall amount of output consisting of some of the highest scoring documents, is presented to the user.

Some of the retrieved output is thenexamined by the user who identifies each document as being either relevant(R) or not relevant (N) to his purpose.

These relevance judgments are

IX

later returned to the system, and used automatically to adjust the initial
search request in such a way that query terms, or concepts, present in therelevant documents are promoted (by increasing their weight), whereas terms
occurring in the documents designated as nonrelevant are similarly demoted.
If the terms from the relevant items are added to the search requests, while terms from nonrelevant items are subtracted, the first query
updating operation can be represented by the equation:qn1

where q=qo

+ L r, - X s.
. -a
, —i

is the original query formulation, q

the set of terms identifying the iis the updated query, r. is

document specified as relevant by theuser, and s. is the set of terms identifying the inonrelevant document.

This process produces an altered search request which may be expected to
exhibit greater similarity with the relevant document subset, and greater
dissimilarity with the nonrelevant set.
The altered request can next be submitted to the system, and asecond search can be performed using the new request formulation.

If thesystem performs as expected, additional relevant material may then be retrieved, or, in any case, the relevant items may produce a greater similarity with the altered request than with the original.

The newly retrieved

items can again be examined by the user, and new relevance assessments canbe used to obtain a second reformulation of the request.

This process canbe continued over several iterations, until such time as the user is satisfied with the results obtained.

Since the method makes very few demands

IX-16on the user, the automatic relevance feedback process may be expected to
be preferred by users unfamiliar with the system operations. On the other
hand, the process is not likely to be effective if the user is unable toidentify for the system at least one document which is clearly relevant to
his needs.
The post-search methods as well as the combined methods making useof pre- as well as post-search information are illustrated in the bottom
half of Fig, 1. A summarization of all the query updating methods is given
in Table 2.

5.

Evaluation Results and Discussion
The experimental results included in this section are based on

the manipulation of a collection of 200 abstracts of documents in aerodynamics, together with 42 search requests proposed by scientists active inaerodynamics.

Complete relevance judgments, prepared by these same scien-tists, were available which identify for each query the set of relevant
documents.

The aerodynamics collection has previously been used for test

purposes by the Aslib-Cranfield project [3] and by the SMART system [4].
The thesaurus used for both the manual and automatic query expansion operations contains 3230 word stems and 736 thesaurus classes. This
thesaurus was constructed by SMART staff members using text concordances,word frequency lists, standard dictionaries and reference works, and wordlists obtained earlier from the Cranfield project. An attempt was made totime the query expansion operations by restricting the use of the thesaurus
display to either one minute, two minutes, or more than two minutes. WhileIX-17the output of Table 3 shows that increasingly more terms can be added to thequeries as more time becomes available for the updating operations, the differences in retrieval effectiveness are small, and the evaluation output
shown represents the output obtained for a display time of two minutes.
The main results are presented first in terms of recall-precisiongraphs, and then in terms of cost and user effort.

A)

Recall-Precision Results

The evaluation output is presented in Figs. 2 to 7 using the standard recall-precision graphs, averaged in each case over the 42 queries
used with the collection of 200 documents.

The curves are, as usual, mono-

tonically decreasing, reflecting the fact that as more relevant items are
retrieved (as recall goes up), more irrelevant items are also retrieved(causing the precision to go down).

Increasingly more effective retrieval

performance is reflected by recall-precision curves close to the upper
right-hand corner of the graph where both recall and precision take on ideal
values of 1.

Next to the graphs, some of the numeric values are presented

in terms of recall-precision tables, giving the average precision values
at certain selected recall values.
Significance values, computed by a standard t-test, are also includedin the output figures, representing in each case the probability that theperformance values for two specified processing methods are in fact derived
from the same distribution.

Thus, if the computed probability value ishigh, the two methods are assumed to be statistically indistinguishable; on
the other hand, if the probability value is low - say 0.05 or less - theIX-18likelihood that the evaluation results could have been derived from the samedata set is very small, and the differences in performance can then be assumed
to be statistically significant.
The following principal conclusions can be drawn from the output ofFigs. 2-7:a)automatic thesaurus vs. pre-search using thesaurus display(Fig.2):the automatic thesaurus expansion and the manual expansion
using pre-search thesaurus display both produce an improvementin performance over the word stem matching process.

Overall,the automatic thesaurus (which requires no user intervention)is superior.

At high precision, however, the greater selec-

tivity of the words chosen by the manual process produces
better results.

The superiority of the automatic thesaurus

at medium and high recall is attributed to the previously
mentioned difficulty of selecting appropriate terms from thethesaurus display.
b)

automatic thesaurus vs. pre-search using source document
display (Fig. 3 ) :the source document display produces a precision improvementof up to ten percent over and above the automatic thesaurus
process; however, the table appearing with Fig. 3

shows thatthe improvement is not statistically significant.

The rela-tively modest increase in performance may be due to the factthat the source documents and queries used in the experiment
originated with the same authors, so that the source documents
contain many of the terms already included in the query statements; also, some of the source documents appear only marginally relevant to the actual queries; both of the interactive
pre-search methods turn out therefore to be not substantiallyIX-19superior to the fully-automatic thesaurus method (except at
high precision).
post-search procedures using displays of titles or abstracts
of previously retrieved items (Figs. 4 and 5 ) :title and abstract post-search displays are superior to bothof the pre-search displays, as shown in Figs. 4 and 5.

Im-provement with title display is limited to the high precision
regions, since the titles are so short that words not in thequery are rarely included.

The query alterations due to title

display are therefore limited to deletion of unnecessary concepts, improving mostly the precision.

Abstract displays pro-

duce both precision and recall improvements, at the cost of
greatly increased work on the user's part.

The amount oftext examined during an abstract display process is about1000 words, from which five to ten may be selected for query
expansion.
automatic thesaurus vs. post-search updating using abstract
display and relevance feedback (Fig. 6 ) :both the manual post-search method with abstract display andthe automatic relevance feedback process are superior to thestandard word stem process; the abstract display is best in
the very high precision ranges.

The performance differences

between the two post-search methods are not significant athigh precision, although the improvements obtained with bothmethods over the standard word stem process are significant.
The relevance feedback output included in Fig. 6 is obtainedby retrieving, in each case, 5 documents at a time, asking
the user to identify any relevant items, and adding thecorresponding terms to the search request.
combined pre-search dictionary and post-search abstract
display (Fig. 7 ) :IX-20Fig. 7 shows that a combination of abstracts and thesaurus
displays offers an overall improvement of about twenty percent
over the standard word stem process, and of ten to fifteen
percent over the thesaurus process; in both cases, the improvement is statistically significant. When word frequency information is added to the display, a further improvement results
for the word stem procedure, since the user can now ensure thatall parts of the query are properly weighted.

The output ofFig. 7 is approximately equivalent to the automatic relevance
feedback process (Fig. 6); however, the combined pre- and postsearch process requires much more user effort and experience
than the relevance feedback method before it can operate
successfully.

B) Overall Evaluation
The performance of the various interactive procedures is summarizedin Table 4.

The first column reflects computer demands; the second, user

effort; and the last two reflect search effectiveness in terms of recall
and precision improvements over and above the normal word stem matching
method.
Since the post-search methods require two separate file searching
operations - one prior to the interactive process and one following it the computer demands are comparatively higher for post-search than for theother methods.

Thus, when search time may be expected to be considerable -for example, for very large collection sizes - the pre-search procedures
may become mandatory.
From the user's viewpoint, the less information is displayed, theeasier will normally be the interactive process.

Thus the relevance feed-

IX-21

1! Average Number ofSignificant Terms
per Query

Query Type

Original Query

8.3

Terms added in 1 minutein 2 minutes
later

3.6
2.0
1.0

Variation in Query Length
Table 3

Processing Method

Demands i DemandsononComputer
User

Precision Improvement
over Word Stem Match
Low Recall

High RecallA) Fully Automatic
normalnormal

none
none

+4%

+6%

thesaurus display

normal +mediumhigh

+6%

+4%

source document display

normal +medium+8%+5%

mediumvery higtj
, low

+13%
+17%
+ 10%

+2%
+7%
+7%

word stem match
automatic thesaurusB) Pre-Search InteractioniC) Post-Search Interaction
title display
abstract display
relevance feedback

high
high
high

Performance Summary
Table 4

IX-22back procedure is simplest, since the user must merely identify one or
another document as either relevant or nonrelevant; the pre-search thesaurus
displays, and the post-search abstract displays are hardest, since complicated decisions are required to update the search requests.
Turning now to the performance parameters, it is seen in Table 4
that, everything else being equal, the post-search methods are more powerful than the pre-search procedures.

(Unfortunately, those are also themethods which put the highest demands on the computer).

One obvious reason

why the post-search methods operate more reliably is that a computer search
has already been performed before the user is asked to update the query.
Thus, the query alteration process is undertaken with prior knowledge of how
well the original query has performed.

The post-search alteration can thenbe used to initiate small changes for queries requiring only little improvement, and more massive changes for the others. For the pre-search methods,
no such prior information is available.
Of the post-search methods, the best performance is obtained with
abstract display; however, this method also makes the greatest demands on theuser.

The relevance feedback method is superior and much preferable from theuser's viewpoint.
To summarize the performance and cost indications, the following
search strategy would appear to be useful under most circumstances:a)normally, use standard automatic thesaurus method without
user interaction;b)

if improvement is needed and search time is not excessive,
use relevance feedback;IX-23c)

if search time is £t a premium, use pre-search source
document or thesaurus display;d)on the other hand, if high retrieval performance is mandatory, try post-search abstract display.

The difficulties of the manual query updating methods may beillustrated by the example of query 317, reproduced in Table 5.

The

original word stem retrieval run produces the two relevant documents
in rank positions 4 and 10.
words were selected:

From the thesaurus display, the following"elastic", "resilient", "unstiffened", "modulus","aeroelastic", "laminar-boundary-layer".

This promotes the two rele-vant documents to rank positions 2 and 5; however, the automaticthesaurus run yields rank positions 2 and 4, without any user interaction.

When the post-search displays are used, the results are

similar.

Title display is not very effective for this particularquery, yielding only an indication that "theoretical" should be increased in weight, which raises the rank positions of the relevantfrom 4 and 10 (in the original word stem run) to 4 and 9.
display is more fruitful, adding "elastic"

Abstractand "resilient" as well.

This increases the ranks of the relevant documents to 1 and 6.

How-

ever, the same query, now processed through the automatic thesaurus(abstract display and automatic thesaurus run) yields perfect performance, as does the automatic thesaurus run with relevance feedback.
To achieve perfect performance using only manual updating
methods and word stem matches, it is necessary to utilize a combined
thesaurus display, abstract display, and word-frequency information,

IX-24

which yields the following rather complex set of changes: delete "anyone"and "investigate"; increase the weight on "theoretical" and "flexibility"
by a factor of two; add with weight of one the words "analytic", "resilient","calculate", "unstiffened", "aeroelastic", and "laminar-boundary";

add withweight of two "flexure"; and add with weight of three "elastic". Thesechanges produce a word stem run with perfect performance, but at far greater
time and trouble than the automatic thesaurus with abstract display run.
The exact adjustment of the term weights is normally performed more accurately and more easily by the automatic thesaurus. The manual methods arethus best reserved for users with the skill and interest to consult lengthy
displays and to make complex decisions.
A meaningful cost analysis is difficult to make without the use ofan operational time sharing system to perform the experiments. Table 6 contains an estimated cost summary based on running times for the IBM 7094.
Machine and user costs are assumed to be $75.00 and $10.00 per hour, respectively.

Scanning time is 5 milliseconds per document, and additional cen-tral processor time is ignored.

Table 6 shows that the post-search methods

are clearly the most expensive (they also are the most effective), with
relevance feedback relatively cheaper than abstract displays.

In general,

the automatic procedures appear economically and operationally better suited
to the retrieval operations than the manual methods.

Since the cost of

human time may be expected to continue to increase relative to the cost ofmachine time, the automatic procedures may grow even more attractive in the
future.

*— x:

CO

>»
o

+^,

CL

CO

in

a>

w-

Q>

3

3

O
CO

.798
.339
.168
.181
.252
.634 .691.669.534 .594.605.462 .5 10 .541
.343 .376 .411
.253 .292
.314

c £
o

c
CO
o

CL O
—

10

— K> I O S 0>

odd

do

1

—

que

i-

CO
CO

CO

o

QL

quer

a>

3

o

esa

*

**~-'

Q.

"3

wor

TJ

CO
-1

ord

«*CO

^^

A

a
a>
co

o

E
a>

Precision

E

c

<

1=

Recall

*—»

.580
.203
.199
.138
.061

o

o

T-test Significance 1

IX-25

E
o
o

CM

o

en

k.

—
o

O

c
o

c
o»

••-

•—

o

o
c
e*

o
o

O

c
o

A
<J

D

cwo

Ajp

^

J

J*

///

Jtf

I

o

1

o
o

UJ

HCM

o

a.

<J0D
* — ' —

00

—

1

CD

1

CD

H
AC D

H*

iff

o
CO

CXJO

1

c
o

HOO

•<JO

c
o

a

J

1
CM

1

IX-26

10
1£u
fd

o n

<J

-HD

|m
l-H
G
tn
l-H
lw

C^ ro rCM V£ CM VD
co CO LO r>-

r>-

o 1
r^
r^

3
ft

4J

1 t(i

N

^

1 <u3

o^ 00
ro vD
r^ ro r H
(X)
CT.

G
r H CMCO LO
r H CM

fd
U)
CD

I+

H

-a

• i
IEH

H

5
CD
U

G
n3
o
•H
MH
-H

CJ
c
0 r^

1

n

9
rL,
D

G

saurus1|-Ho
1 m s\
H <p
| <u
D
^i

<—
B»
Q)
-P
U)

T)
U
0
'£
Ul
QJ
-H

u
Q)

^-v

en
3
M
3
rd

0)

(U
.C
-P
0)
(D
-H
>H
CD

&

0

O

<

rH

H <tf

<tf
LO

O

rH
<tf

CM

U o
Pu -rH
1 -P

r-{
CO

rH

^r

fi

CO CM
<^ CM
vD • ^ cr>

CO ro^ 0 LO

^r

0)

H -H
rd -P
o 05

fd

H
ft
10
•H
Q

-P
CO

CO CM

-P

1

&
o
ti^

rH

o

ro

LO

O

o

r^ en

o

o

Q

0

o

CD
U

CD

u
o

U

CO

o

CD
U

Cn

r* VD
^r co

£

c

-H
H
O

H
rH

-P
G

-H

tn

0 ^ LO
VO o
KD ^D

LO
00
LO

CM

0)

-H
13

tf

M

Y
6

>1
01
rH
Q^
[fl

c

•H

o

•*—

Tl

•H

ro
O
^D

1^

lO.

(D

£
-P

rH
fd

H

00

^r
r-

- H -rH
0) CO
-H
U H
CD fd

MH
O

0)

M
3
o

2
<d
U)

-P
CD

O

o
O
O
CM

c/)
CD

o
o

0)

IT

D

&
u
c
o
•H
0)
-H
U
QJ

00

H

r^
I
rd

(M

c
o
00

10

CVJ

CD

>
-H
-P
O
CD
MH
LW

W

U
CD

>

O
0)
CD

tn
rd
H
CD

>
fd

-H

fa

T-test Significance
A
a
o
o

IX-27

ro

o o o ooo o o ooC

CVJ CVJ N <fr IC
O O O —roQ.

0)o o o oo
^

O

o
c 'C

.2 c

0> <*• N tooo(J) — CVJ CVJ CM

D

E

o

a.
co

o :r

co CVJ co h - r h» CO «0 fO C\J

O

o

a. o
I .2

h - r - CD * • to

A

Precision

E

<o

"o CO

o
o

u

oc co

^- <fr CVJ rororo ro co ^ - i n
co io TJ- ro CVJ

•-

to
-Q

<

Recall

O

co
<D

i~

0)
3

cr

3

O
Q.

2

S

CO

*•-

8 '

i

o

o

^

— ro to K o>

6 6ddd

o
o

cr
«-

c
o

/ / /
D< O

Q.
O

CO

L.

o
ex

o
co .2
CO

d<] o
CM

o

CO

0-

I

/

a<
I /

/

D <
/ /

a<
o
CO

o
CD

o
o
CD

O
/

CVJ

o

" 1

00

/

o
/

CO

CVJ

E
o
o

T-test Significance
A
a
o
o

IX-28

ro

—

oo ooooo oooo ro a> oo —00 O 0) rOCD
IO CM
O

T3
C

3
Q.

<

«•-

CO
CD

13

O
CD

J3
O

K

a> ^ r- K> oo
0 > — CVJ CVJ CM

o
c

O
O

c Ho c
CO

o»

a

U CO
CD

*-*
E

<D
«•CO

CO

CD

•o

CO

k>

T3
k.

o
J

O

*
'
CO

CD
k.
CD
•D
CT

*
>*

o

CL
CO

T3

o
*

(7) 0 ) — ^ <7>(0 io m ro CM^ ^ CM ro ro

>v
O

k.

_

Q.
CO

CL o
| o

Q

+—
CO
__
O 'Z

o o

CD

CD

QC CO

ro ro co ^ to
<D to *• ro CM

TJ
C

<

Recall

-D
k-

••-

A

E
CD

— ^ o <o w

o

CVJ

^
E

h- r- a> *• ro

PrecisionE— ro# io N a>

»-

o
c

O O OO O

Q.
CO
TD

—
O
c
o»

*O
o

«•-

•k.
•CO

•k—
.

o

o

T)

o

O

<1

D

O

tP

O

f^

O

k.

o
c
o

o
o
CD

JQ

a.
a

fit

hr
m

k.

O

u
CD

/

a/

a/

//

<o
Jl
<o

CD

a:

II
<o

CD

a.
I
o
u

CM

c
o
CD

CO
CD
k.

CXIO

a

CM

o
CL

E
o

O
CO

in

IX-29

0)

o

c
ed
o
-H

-P

CDO

00 rH rH rH rH

3o o o o o

a,
-p

O

en

O

O

O

O

TJ

3

c o

01

-P

0)

w

in

<D

d)
-P
I

u

ti

rH 01
•Q u
01 •H
H MH
-H

G C
0 cn

(T> ^

r ^ oo oo<T> r H

CN CN CN- H •H0) c/3
^H
u rH
CD 01
H C)
P-4 •rH
1 -P
rH in
rH -H
03 -P

r^ r-> KD -*$ oo
O
«H

-H

-p

u

(D

H

rr CN OO oo
U0
oo 0 0 KG <tf
V£> U00 0 CN

Tf

CD

OJ
PL.

u

03
-P
00

>

KT

-P
W

w

O
<D
Pd

(D

6
a)

6
<D
-P

cr> ^ ^r O 0 0
o 00 o rH 0CO0
00 r- r- i n

en

o

u
01

0)
H
<D

T)

u
o

w
(U
H
H
(1)

2
0^
q
tp
-H

T1

X
0

0

rd • H-P
010) 5-10) (1)
4-1 -P*H€—>•H oo in r^ <y\• • • • •o o o o o

id

u

> i

01
H
O.
in
*H

01

>1
03
rH
10
-H

TJ

0)
U

Q

-p

03

05

4J
U
01

>
rH

H

u
O

M

o

+J

4->
in

a:

•a

o
O

d

<J

CL

f/°?

PI

o
o E
—• oo
00

"35
a
v-

<] o o

CD

J_

J/ J

/ /

.2 -*Lo O

V
I
00

"o
o
a>

/

«tf

/

CJ

/
CD

CL

C\J

MH

o
o

in
-H
o3
QA

U

<D

-H

a.
CO

.009
.007
.014
.001
.002
.787
.695
.631
.469
.361

Q
A

Precisionoc.634 .794.534 .668.462 .595.343 .445.253 .349

a>

V)

3

3

o

a> a>
X) o

O

E

.009
.002
.006
.001
.002

o

<

E

o

13

r

o

T-test Significance

IX-30

o c
h- o
o
c «*o c
CO o»
o en
<D
w-

o
o

CL —
o

| o
••_n_ CO
•
—
o n

£

<p

CD

or (7)C/>

T)

RecallOXX— K) if) f- 0>

66od 6

T3
O

o

5
>i

C

>*

J5 .2

o 2
E 5

51

~

o-S

.2

DM

JO

E
o
o

o
o
CD

O

<

a:

D
D<J O

o

2

-

o
c
o

00

D<

o

O

CD

CD

O
O

ft

CVJ

<n o
ao

CD

CVJ

o
CO

o

6
o
o

IX-31

Query 317;

Has anyone investigated theoretically whether
surface flexibility can stabilize a laminarboundary layer?
(Two Relevant Documents)

Processing Method

A)

Terms "Added"or Deleted

Fully Automaticword stem match

4 ,10
2,4

automatic thesaurus

B)

Ranks of
Relevant
Documents

Improved Searches
word stem plus
thesaurus display(pre-search)"unstiffened", "modulus", "elastic", "resilient" , "aeroelastic"

2,5

word stem plus
title display(post-search)"theoretical"

4,9

word stem plus
abstract display(post-search)"elastic", "resilient","theoretical"

1,6c) Perfect Searches
1,2

automatic thesaurus
plus relevance
feedback
word stem plus
abstract display
plus automaticthesaurus"elastic", "resilient"

1,2

thesaurus display
plus abstract
display plus
word frequency
displayanyone, investigate,"theoretical", "flexibility", "analytic","resilient", "calculate","unstiffened", "aeroelastic", "laminarboundary" , "flexure","elastic"

1,2

Typical Manual Query Updating
Table 5

Estimated Cost per Query

Processing Method

A)$10.00$10.00$ 6.00$ 5.50$11.00$10.50$10.50$13.00$10.50$20,50$23.00$20.50$ 0.50$ 1.00$ 6.00$11.50$ 8.50$14.00Interactive Post-Search
title display
abstract display
relevance feedbackD)$ 5.00$ 5.00Interactive Pre-Search
thesaurus display
source document display

C)

100,000 documents

Fully Automaticword stem match
automatic thesaurusB), 50,000 documents

Partial Searchcluster searches Conetenth of collection)cluster search plus
relevance feedback
cluster search plus
abstract display

Assumptions:

machine cost
$75.00/hour
document scan
5msec/doc
central processing cost0
human time
$10.00/hour

Estimated Cost Figures
Table 6IX

The bottom part of Table 6 shows that processing cost goes down
drastically if partial searches of the collection are performed, rather
than full searches.

Such partial "cluster" searches are implemented with

the SMART system; however, the cluster searches cannot be used if a recall
performance higher than about 50 percent is required 111].

6.

Conclusion
The best overall process for precision purposes is the abstract dis-play used in conjunction with a word stem matching procedure.

For recall

purposes, a combination of abstract display with thesaurus word normalization appears best.

The automatic relevance feedback approximates the ab-stract display method while requiring much less user effort.

Considering

the complexity of the abstract display system, a sensible set of recommendations for high performance real-time retrieval would be the following:a)for highest precision, use title display and word stem
matching;b)for highest recall with normal users, use the automaticthesaurus followed by automatic relevance feedback; withexperienced and patient users, use abstract display anddictionary display plus frequency information;c)for maximum cost reduction at lower performance, use partial
searches of the document collection.

These rules provide a graded set of feedback methods, ranging fromautomatic procedures which make only minimal demands on the user and aresuitable for novices (automatic thesaurus expansion, relevance feedback),

34

to methods permitting sophisticated user-system interaction which combine
the best features of manual and automatic query adjustment (thesaurus andabstract display)•

One may expect that a suitable mix of user feedback

procedures can be found to produce optimal retrieval under many different
conditions over many types of user classes.

IX-35

References[1]

G. Salton and M. E. Lesk, The SMART
Automatic Document Retrieval System An Illustration, Communications of theACM, Vol. 8, No. 6, June 1965.

[2]

G. Salton, et al., Scientific Reports on
the SMART System to the National Science
Foundation, Nos. ISR-11, ISR-12, ISR-13,
Department of Computer Science, Cornell
University, Ithaca, New York, June 1966,
June 1967, and January 1968.

[3]

C. W. Cleverdon, Jack Mills, and E. M. Keen,
Factors Determining the Performance ofIndexing Systems, Vol. 1, Design, AslibCranfield Research Project, Cranfield
College of Aeronautics, 1966.

[4]

G. Salton and M. E. Lesk, Computer
Evaluation of Indexing and Text Processing,
Journal of the ACM, Vol. 15, No. 1,
January 1968.

[5]

R. M. Curtice and V. Rosenberg, Optimizing
Retrieval Results with Man-machine Interaction, Center for the Information Sciences
Report, Lehigh University, Bethlehem, Pa., 1965.

[6]

H. Borko, Utilization of On-Line Interactive
Displays, in Information Systems Science andTechnology, D. Walker, editor, Thompson Book
Co., Washington, D. C., 1967.

[7]

J. J. Rocchio, Jr., Document Retrieval Systems Optimization and Evaluation, Harvard University
Doctoral Thesis, Scientific Report No. ISR-10
to the National Science Foundation, Harvard
Computation Laboratory, March 1966.

[8]

J. J. Rocchio and G. Salton, Information Search
Optimization and Iterative Retrieval Techniques,
Proceedings of the AFIPS Fall Joint Computer
Conference, Vol. 27, Spartan Books, November 1965.

[9]

G. Salton, Search and Retrieval Experiments in
Real-Time Information Retrieval, Proceedings
IFIP Congress - 68, Edinburgh, August 1968.

IX-36

References(contd)[10]

E. Ide, User Interaction with an AutomatedInformation Retrieval System, Scientific
Report No. ISR-12 to the National Science
Foundation, Section VIII, Department ofComputer Science, Cornell University,
June 1967.

[11]

R. T. Grauer and M. Messier, "An Evaluationof Rocchio's Clustering Algorithm", Scientific
Report No. ISR-12 to the National Science
Foundation, Section VI, Cornell University,
Department of Computer Science, June 1967.