VII-1

VII.

Search and Retrieval Experiments in
Real-Time Information Retrieval
G. Salton

Abstract
Future operating document retrieval systems may be based on fullyautomatic information analysis methods instead of manual indexing, and on
real-time search procedures which allow the user to interact with the system
during the search process.
Performance characteristics are first given for fully-automatic
information retrieval systems, and comparisons are made with presently
operating partly-manual systems.

Thereafter, various user-controlled

search strategies are described, and the potential of these strategies in
improving systems performance is discussed.

The evaluation results for the

real-time retrieval procedures are used to derive design criteria for future
automatic information systems.

1.

Introduction
Throughout the world, the design and operations of large-scale

information 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 useof mechanized or partly mechanized procedures for various information
storage and retrieval tasks has also become more widespread.

As a result,a number of large information systems are now in operation in which atleast the search operations — that is, the comparison of incoming searchVII-2

requests with stored information items is carried out automatically.

Typicalexamples in the United States are the NASA Scientific and Technical Information Facility, and the MEDLARS system at the National Library of Medicine.
While these operational information systems are thus able rapidly
to search vast storage files, often containing many hundreds of thousands ofitems, most of the operations other than the search itself are performed
manually with the help of human experts.

In particular, all the content

analysis and indexing operations, leading to the assignment of suitablychosen combinations of index terms to the stored documents and to incoming
search requests are normally performed by specialists who know the given
subject area, as well as the performance characteristics of the retrieval
environment within which they operate.
As will be seen in the next section, many of the information
systems which base their operations on manual indexing but largely automatic search methods are quite successful in isolating,from the large massof largely irrelevant stored material, many of the items which prove pertinent to the users1 information needs. Nevertheless, the feeling thatmanual systems and procedures should be replaced by suitably chosen automatic methods has continued to grow, and a number of fully-automatic information storage and retrieval systems have been designed and put into operation, at least on an experimental basis. The SMART system represents one
such effort to replace the intellectual indexing by sophisticated automatic
text analysis procedures, and thereby to produce a retrieval environment
in which all document and query handling procedures are performed automatically [1,2,3].

VII-3In the next section, the performance characteristics of presently
operating information systems are briefly outlined and a comparison ismade with the performance of the alternative fully-automatic environment.
Various procedures are then described leading to an improvement in systems
performance, and conjectures are made concerning the design of future automatic information systems.

2.

Performance Characteristics of Information Systems
Many different criteria may suggest themselves for measuring theperformance of an information system.

In the present context, the systemeffectiveness is assumed to depend on its ability to satisfy the users'
information needs by retrieving wanted material, while rejecting unwanted
items.

Two measures have been widely used for this purpose, known as

recall and precision, and representing respectively, the proportion of
relevant material actually retrieved, and the proportion of retrieved
material actually relevant [4].

(Ideally, all relevant items should be

retrieved, while at the same time, all nonrelevant items should be rejected, as reflected by perfect recall and precision values equal to 1 ) .
It should be noted that both the recall and precision figuresachievable by a given system are adjustable, in the sense that a relaxation of the search conditions often leads to high recall, while atightening of the search criteria leads to high precision.

Unhappily,

experience has shown that, on the average, recall and precision tend tovary inversely since the retrieval of more relevant items normally also leads
to the retrieval of more irrelevant ones.

In practice, a compromise isusually made, and a performance level is chosen such that much of theVII-4

relevant material is retrieved, while the number of nonrelevant items which
are also retrieved is kept within tolerable limits.

As an example, the

MEDLARS system at the National Library of Medicine is said to achieve an
average recall of 0.58 and a precision of 0.50; that is, an average user may
expect to retrieve 58 percent of the relevant material contained in thesystem, while only one half of the retrieved material is actually unwanted.
Obviously, other operating points are achievable by altering the indexing or
search techniques, producing either higher recall normally with low precision,or higher precision with lower recall.
In order to make it possible to design more effective retrieval
systems, it is important to be aware of the reasons for system failure underpresently existing operating conditions.

Tables 1 and 2 summarize the per-formance for 18 queries processed by the MEDLARS system.

It may be seenfrom Table 1 that a large proportion of the recall failures of the system(that is, failures to retrieve relevant material) is due to the lack ofsufficient user-system interaction, while Table 2 reveals that many of the
precision failures (that is, failures to reject irrelevant material) arecaused by lack of specificity in the document indexing.

In both cases, themanual analysis process is at least partially to blame, since the query
analyses as well as the document indexing are performed by experts who
cannot — in the absence of specific information concerning the user
population — always be aware of the appropriate indexing requirements.
In the automatic SMART system, an attempt is made to replace theintellectual indexing effort used in the conventional situations by afully-automatic computer analysis of the document and query texts.

Specif-ically, a variety of language analysis procedures — including suffix cut-off

Type of Recall Failure

Numberof
Instances

Percentage
of
Total

Important term missing fromdocument specification(indexer omission)

6

11%

Indexing insufficiently
exhaustive (some aspect of
document content not reflectedin the indexing)

6

11%

Indexing insufficiently
specific (index terms used
are too broad)

9

17%

8

15%

21

40%

3

6%

(resulting in relevant document
not retrieved)A.

Indexing Errors
1,

2.

3.

|

B.

Search Errors
4.

5.

6.

Important term missing fromquery specification (searcher
omission)
Lack of sufficient usersystem interaction (searcher
misunderstands user need)
Missing items because of
selective print-out (retrieved
item not shown to user due tosampling)|

Typical Recall Failures in Conventional Retrieval System(18 queries processed by MEDLARS retrieval system)
Table 1

Type of Precision Failure(resulting in nonrelevant
document retrieved)A.

Numberof
1 Instances

Percentage
of
Total

Indexing too exhaustive (minor
aspect of document content
reflected in indexing)

17

11%

Indexing not sufficiently specific(indexing language used is too
general)

53

34%

7

5%

8

5%

Indexing Errors
1*2.

3,. Important index term missing
or inappropriately or incorrectly used
4.

B.

Incorrect term relationshipspecified by indexing rules

Search Errors
5.

Search formulation insufficiently
specific

18

11%

6.

Lack of sufficient user-systeminteraction

24

15%

7.

Search formulation insufficiently exhaustive (not enough
Boolean formulation)

22

14%

Miscellaneous errors (on thepart of searcher or requester)

7

5%

8.

Typical Precision Failures in Conventional Retrieval System(18 queries processed by MEDLARS)

Table 2

VII-7methods, thesaurus look-up, phrase generation methods, statisticalterm associations, syntactic analysis, and others — are used to reduce
document and query texts into analyzed concept (or term) vectors.

The

concept vectors attached to the documents are then matched with thevectors derived from the search requests, and the documents, arranged
in decreasing query correlation order, are submitted to the user as
answers to the query.
One might expect that an automatic text analysis of the typeused in the SMART system would necessarily produce retrieval results
which are much inferior to those obtained in a system based on manualindexing.

In actual fact, the automatic environment makes it possible

to use for analysis purposes relatively large sections of text, such as
abstracts or summaries, thus insuring a high degree of indexing exhaustivity;
furthermore, the importance of some assigned terms can be enhanced byautomatic weighting methods, leading to a more sophisticated matchingprocess between analyzed queries and documents than is normally possible.
As a result, the benefits of the index language control supplied in the
more conventional retrieval situation by the human indexers appear to bebalanced by a deeper and more complex type of analysis available in an
automatic environment; this is reflected by evaluation results which indicate that the search effectiveness of the fully-automatic systems is
not inferior to that obtainable at present in a partly-manual system.
Consider as an example, the performance characteristics of the
SMART system, presented in the recall-precision graphs of Fig. 1.

The

left-hand graph (Fig. 1(a)) shows the performance of an automatic wordstem matching procedure, using weighted word stems extracted from document

VII-8abstracts and from search requests respectively/ for three different document
collections in the areas of documentation (ADI), aerodynamics (CRAN), andcomputer engineering (IRE).

The performance for the three collections isgenerally comparable, ranging from an average precision of 0.80 at recall of
0.10, to an average precision between 0.10 and 0.30 for a recall of 1. Fig.
1(a) also exhibits the large distance which remains to be covered between
the performance of the automatic word-stem matching system and that of an
ideal system (in the upper right-hand corner of the graph) where both recall
and precision values are close to 1.
A variety of more refined language analysis procedures can be usedin an attempt to improve the performance of automatic information systems[4,5],The use of a stored thesaurus capable of recognizing synonyms andother closely related terms is one such process which can be incorporated
into an automatic content analysis system.

Fig. 1(b) represents average

performance for 780 documents in the computer field for both the wordstem matching process and a thesaurus look-up method in which all wordstems are first replaced by thesaurus group entries (concepts) prior tothe comparison between query and documents.

It may be seen that thesynonym recognition implicit in the thesaurus procedure serves to improve
the retrieval performance by approximately ten percent. Other language
analysis methods produce some further improvement but do not come close
to the ideal performance area [5].
A comparison between the automatic SMART procedures using abstract
processing, and the conventional operational retrieval situations based on
the matching of manually assigned index terms shows that the retrieval

VII-9cou<n «"—^

E

O
CL

c
o

w

fO

• ~ ?

0>

3

E

i

tw

«

-j

3
O

•—

in

lis / /

w.
3

O

«/>

H

O

oo

<
/>
4>
JC

Wor
The

"XD

</>
c
<3U

•—

s Com
Docum

w

<x>

D

UJ

cr
•—i
o
Of)

h- N1 V„

E

O

0)

*/>

(/)
6

CJ

D

o
en.
u

XD
w

O

o
w-

<0

"5
o
c
a>

E
3
U

o

a

0>

>

£ <
oo

c
o
X3

>

(VJ

T>

O

o

'Z

CL

•^

c

2w

«/>

«

U
w

-H

0>

num

en

Proc

UJ

€1

fa

*o
c
a> o
u
c
o

a>
c
«n

aroct

t>

-C

O

" £ o
*

o

^ ° *
«§ I
a ~8

o

t/>

k.

10

s

o

Com
Ilecti

S

o

a.
15
u

>s

<
9
!

u
a <J
•

CO *>
i.

o

£ p

o

fc_

a>

•—

<

i

o

»4 •

E (J

•-•

LJ

E
t-

a>

o

4>

w

CL

O

o

*—*

VII-10effectiveness achievable is quite comparable in the two cases. Table 3(a)shows "normalized recall" and "normalized precision" values averaged over
42 queries for 200 documents in aerodynamics formerly used as part of the
Aslib-Cranfield tests [4]. Columns 1 and 3 of Table 3(a) give the performance for the manually assigned index terms both without and with theuse of word normalization through the thesaurus. Columns 2 and 4 do thesame for the SMART word stem and thesaurus procedures.

It may be seen

that, in each case, the evaluation measures exhibit the same order ofmagnitude, the stem process being slightly better for the index terms,
and the thesaurus process favoring slightly the automatic abstract process.
The same general conclusions can be derived from the recall-precisioncomparisons of Table 3(b), which reflect the average performance of 18
queries and 273 documents in biomedicine.

Column 1 indicates the performancefor the MEDLARS manual indexing process used at the National Library ofMedicine, while columns 2 to 4 contain figures for three automatic methods
incorporated into the SMART system.

It is seen that, for the small sample

collection, somewhat better average recall is obtained with the SMART methods,
and somewhat better precision through the manual indexing.
The description of the test environment used to produce the dataof Table 3 must remain outside the scope of the present study [5,6].

How-

ever, if the data given are assumed to be representative of performancedifferences between presently operating semi-manual retrieval systems andthe fully-automatic analysis systems of the future, then a conclusion thatthe performance level is comparable seems reasonable. Moreover, in bothcases, the performance is far below that which an ordinary user submitting
a search query to a retrieval system might be hoping to achieve.

VII-11

Stem
Indexing

SMART Stem |I
Thes-3
Indexing
Abstracts

SMART Thes-3
Abstracts

Normalized Recall

0.890

0.864

0.873

0.884

Normalized Precision

0.683

0.670

0.694

0.695

a)

Comparison of Cranfield Index Term Match with SMART Abstract Processing(Cranfield 200 documents; 42 queries)

MEDLARS
Indexing

SMART
Word Form

SMART
Word Stem

SMART
Thesaurus

Recall

0.643

0.704

0.718

0.690

Adjusted Precision

0.625

0.571

0.570

0.611

b)

Comparison of MEDLARS Index Term Match with SMART Abstract Processing(MEDLARS 273 documents; 18 queries, macro-average)

Comparison of Index Term Matching with Automatic Abstract Processing

Table 3

VII-12In the next few sections, various interactive search techniques
are described which may help in raising the search effectiveness closer tothe optimal area in the upper right-hand corner of the recall-precisiongraph,

3.

User Feedback Retrieval Methods

A)

General Methodology

One of the main hopes in obtaining a retrieval performance whichgoes beyond that presently reached under normal operating conditions, is toinclude 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 need indications, or by evaluation data about the acceptability of items previously retrieved by the system in answer to the search requests.

User-system interaction is now current for many computer applications,

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.
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 theoriginal search requests, or in reformulating queries which were originallyinadequate [7,8],

Alternatively, more sophisticated methods may be used

in which the reformulation of the search requests is automatically performed
based on feedback information obtained from the user population [9,10].

The

VII-13

relevance feedback process incorporated into the SMART system is particularly
well adapted to a time-sharing computer organization with simple console
equipment, since it requires only a minimum of interaction with the user,
and places most of the burden on internally stored routines.
Specifically, an initial search is first performed for each request
received, and a small amount of output, consisting of some of the highest
scoring documents, is presented to the user.

Some of the retrieved output

is then examined by the user who identifies each document as being either
relevant (R) or not relevant (N) to his purpose.

These relevance judgments

are later returned to the system, and used automatically to adjust theinitial search request in such a way that query terms, or concepts, present
in the relevant documents are promoted (by increasing their weight),
whereas terms occurring in the documents designated as nonrelevant are
similarly demoted.

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 relevanceassessments can be used to obtain a second reformulation of the request.
This process can be continued over several iterations, until such time as
the user is satisfied with the results obtained.

VII-14A large number of feedback experiments have been performed with the
SMART system in order to identify those methods which appear to be mosteffective in improving retrieval performance.

These experiments are basedon a query alteration algorithm described by the following equation:
n

^
q

2

i+l = a q i + S q 0 + Y / ^i " 6 / ^i * /
i=l

i=l

n

3

n

4

^i^i + / ^i^i
i=l

(1)

'

i=l

st
Here, the (i+1) " query statement, <3-4.-i /is defined as a composite
obtained from the ith query formulation

q. , the initialq, a set ofn_ documents, r, , identified by the user as relevant, a set of n_1—i2
documents,s. , identified as not relevant, a set of

—a

n^
3

documents, d. ,—isupplied by the user without specific relevance indications, and a set ofnimportant concept numbers, £. , also obtained from the user. A numberof parameters (a,6,y,6,w., and v,) serve as weighting functions. These
parameters are set equal to zero when the corresponding information items
are not specified.

Alternatively, they may be set equal to 1 or greater

if the corresponding items are to be added to (or substracted from) the
present query statement in order to produce the new query.
Equation (1) represents a vector transformation in the document
space, which moves the query close to the documents, or concepts, identified as important by the user, and away from the documents, or concepts,
specified as unimportant.

The effect of various types of transformations

is examined in the next few subsections.
B)

Positive Feedback

One of the simplest feedback methods is obtained by using previouslyVII-15

retrieved relevant items to update the search requests.

Fig. 2(a)represents the output obtained for the Cranfield collection by retrieving,in each case, 5 documents at a time, asking the user to identify any
relevant items, and adding these relevant items to the search requests
to obtain new query formulations.

Fig. 2 presents averages over 42

search requests for initial runs, as well as first and second feedback
iterations, using equation (1) in the following simplified form:

q

i+i=

•^ •£

Fig. 2(a) shows that an average improvement of twenty percent is obtainedin the precision between initial run and first feedback iteration.

Somefurther improvement is produced by the second feedback run, particularlyin the high recall region [11,12].
The output of Fig. 2(a) is obtained by a process illustrated forquery 8 in Table 4(a). Five documents are first retrieved by the initialrun, labelled respectively 187, 173, 39, 33, and 139.

Document 39 is

now identified as relevant (marked 'Rf in Table 4(a)), and is used tomodify the query.

The modified query now produces the five documents

labelled 39, 42, 179, 112, and 181.

Relevant document 39 had alreadybeen retrieved in the initial run, but 42 is new, and after it is identified as relevant, a new query is constructed which, in turn, produces
five additional documents, and so on, until the user obtains no further
useful information.

Obviously, the choice of cut-off, which in theexample is set at five retrieved items, is arbitrary, and may, in practice,
be made to depend on the user's wishes.

Initial
Rank

Doc

Corr

Doc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

187
173
39R
33
139
185
36
188
42R
199
41R
15
98
178
23

.2315
.1949
.1949
.1949
.1771
.1743
.1714
.1702
.1666
.1621
.1542
.1291
.1238
.1231
.1208

39R
42R
179
112
181
188
97
45
41R
2
173
62
187
101
185

a)

.9641 1.6533 1.5200 1.5095 1.4429 1.3865
.3559 1.3529 1.3022 1.2925
.2606 1.2494 1.2474 1.2371 1.2355 1

39R
42R
179
112
181
188
97
45
2
173
62
117
116
187
41R

.9143
.8871
.5804
.5609
.4600
.4090
.3757
.3735
.3296
.2703
.2661
.2615
.2612
.2510
.2430

39R
42R
179
112
181
188
97
45
2
173
62
117
116
187
41R

Corr
.9143
.8871
.5804
.5609
.4600
.4090
.3757
.3735
.3296
.2703
.2661
.2615
.2612
.2510
.2430

Feedback Results for Query 8 (all effects)

Initial
Rank

Doc

Corr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
17
134
143
200

187
173
39R
33
139
185
36
188
42R
199
41R
15
98
178
23
0
0
0
40R

.2315
.1949
.1949
.1949
.1771
.1743
.1714
.1702
.1666
.1621
.1542
.1291
.1238
.1231
.1208
0
0
0
.0000

b)

Feedback Iterations
2
3
1
Corr
Doc
Corr
Doc

Feedback Iterations
2
3
Corr
Doc
Corr
Doc

Corr

187
173
39R
33
139
42R
179
112
181
188

.2510
.2703
.9143
.0317
.0865
.8871
.5804
.5609
.4600
.4090..

Y/ffl

,3296

• //62

.2661

.2510
.2703
.9143
.0317
.0865

V/ltl/ / 'M~&
r
1
I

4IR
0
40R
0

Feedback Results for Query 8 (feedback effect only)"Increment Only" Strategies for Query 8(Cranfield thesaurus; cosine numeric N=5)
Table 4

.2430
0
.0368
0

VII-17

<
c
o
C C ^

c

+
00

-•-•.Oi-iJt
r

•» *

«•_

a

<J

o

•

c UJ
o

c
2

5

a>

i
o

ii

0 j;
iO

9

tr «*.
u

(\J

<

1*
O

O)

(7)
.

ai
E

o
CO
™«+-L

c
00

0)

cr
a.

E

*>
o
c

iD

• •»
c3
k.

3

_i

<

o

c
cr

u
c
o

C

4

o

E

o

i
T5

w

J? o
00

r «_ « C «.t: *_ 8—

<0

o

<

i
o

<i

A

(\J

o
CO

rr^—L

o

cr
CL

00

a>

•?

(NJ

C\J

a
o

o

JO
TO

JO

^

o

_

••-

O

*-

<&>

_

*5

CM

o £
J&

esaur
(feed bocoVII-18

The example of Table 4(a) illustrates the fact that an improvement
in recall and precision may be obtained from one search iteration to thenext for two different reasons, known as the ranking effect and the feedback
effect, respectively [13] . The former is exemplified by document 39 whose
rank is improved from 3 to 1 between the initial run and the first feedback
iteration, following its identification as a relevant item.

The feedback

effect proper is illustrated by relevant document 42, which was notinitially retrieved, but jumps from rank 9 to 2 as a result of the feedback
action.
One may argue that the ranking effect, which reflects improvements
in rank of items already retrieved, should be disregarded, since the user
may not care to look at retrieved items more than once. The feedback effectalone may be measured by freezing the ranks of all items as they are retrieved.

This is reflected in the output of Table 4(b), where the first

5 ranks are maintained throughout, the first 10 ranks after iteration one,the first 15 after iteration two, and so on. Document 42 is now seen to
improve only from rank 9 to 6, since the top 5 ranks are preempted.

The

corresponding recall-precision graph shown in Fig. 2(b) shows that the
feedback effect produces less improvement than the ranking effect.
In a practical retrieval system, a compromise might be made between
the output of Table 4(a) and 4(b) by taking documents previously identified
as either relevant or not relevant out of the system, but leaving the others
alone.

For the example of Table 4, this would delete document 39 after

the initial run, and documents 39 and 42 following the first iteration.

VII-19

The output of Fig. 2 and Table 4 clearly shows that user feedback
information can help in improving retrieval performance by moving thequery close to the area identified

as important by the user.

Occasionally,

however, it happens that some relevant items are lost as other new ones
are retrieved.

Consider, for example, the relevant document 41 which

initially receives rank 11 in the output of Table 4.

After the first

iteration, it gains from rank 11 to 9, but after document 42 is identified as relevant, item 41 decreases from 9 to 15.
approaches document 42, it recedes from 41.

That is, as the query

This situation is showngraphically in Fig. 3, where query 8 first approaches document 39, andthen document 42, while at the same time, it gets away from document 41.
In Fig. 3, the size of the correlation coefficient between query anddocument is represented as varying inversely with the physical distance
between them.
It is clear that in a situation such as the one illustrated inFig. 3, the search request covers several subject areas.

To obtain good

retrieval performance, the query must then be split into two parts, one
to reflect the subject area of documents 39 and 42, and the other the areaof document 41.

Experimental query splitting algorithms are presently

under construction.

C)

Negative Feedback

The feedback process illustrated in the last subsection, operates
with a fixed number of retrieved documents, and uses only positive information (that is, relevant documents identified by the user) for feedback
purposes.

In a practical system, one may anticipate that some users would

VII-20b) First Feedback(after retrieval of 39)a) Initial Search

D

query

O

relevant items©

relevant retrievedc)Second Feedback(after retrievalof 39 and 42)

Feedback Illustration for Query 8(Query Splitting)Fig. 3

VII-21

be willing to look at more information than others before supplying
feedback data.

This may be the case particularly in situations wherenothing useful is retrieved within the top 5, or top 10 items.

In such acase, two different procedures are available, known respectively as
variable and negative feedback.
In the variable process, the cut-off value, which determines thenumber of documents to be retrieved for the user before feedback is returnedto the system, varies from query to query.

One possible strategy might

consist in first retrieving five items; if the user is now in a position
to supply a relevance judgment, retrieval stops, and the query is updated
in preparation for a subsequent search operation; if not, additional
documents are retrieved (in decreasing correlation order with the query)
until such time as a relevant item is identified by the user.
The recall-precision performance of a typical variable feedback
system is shown in Fig. 4(a) for the 200 document Cranfield collection,
averaged over 42 search requests.

In the output of Fig. 4(a), the cut-off

is chosen directly after the first relevant item, with a maximum possible
cut-off of 15.

It is seen that the variable cut-off process operates much

more successfully than the standard system based on a fixed cut-off of 5
items (the second iteration of a standard cut-off process is shown superimposed on the graphs of Fig. 4). Furthermore, out of 42 queries used in
the Cranfield tests, only two were found without any relevant items in
the top 15 ranks, the average number of items examined being only four.
While the variable process thus shows promise, particularly at thehigh-precision end of the performance scale, some queries may always beVII-22

<
U

Si

c?

</)S-

A
O<J

U.^

M

_

in

o

0>

O

00

o

iS 8

&

c
^
o o
o> =
</>

c

o

B

H-

XT

/
/ /

U.^

7/

/

<\j

I

u &

>

> 8

•c

*

o

Z

5 IS

o

^I
*z

(/>

o

00

UJ

<x>

o w

(\J

<r
QL

S» c
o
<

•?§

o

c

5

32

QC

S "o
o o
o +.
.o c o</><0

3 ! 2 3s5

o

<3

i

i

OJ

o
</>

o
UJ
Q:

a.

00

u>

OJ

I' o
o

00

55 i n ;-

2 «

o ± °
•c *- ••OoID

VII-23

submitted for which relevant items are difficult to identify without an
exhaustive examination of a large part of the collection.

Under thesecircumstances, a negative strategy can be used, designed to inform thesystem about what the user does not wish to retrieve. One of the simplest
strategies consists simply in identifying the top document as nonrelevant.
The query will then be modified in such a way as to decrease its similarity
with the item identified as nonrelevant; at the same time, the assumption
is that this modification may increase its similarity with the relevant itemsin the collection [11].
Consider, as an example, the output for query 1 processed against
the collection of 200 Cranfield documents. The standard feedback strategy,
which consists in incrementing the concept weights from documents identified
as relevant, is illustrated in Table 5(a). A cut-off of 5 documents is again
assumed.

It is seen from the table that no relevant document is everidentified within the top 15 documents, so that the feedback procedure isunavailing in that case. The relevant documents 21, 22, and 1 remain attheir initial ranks 32, 33, and 200 respectively.
On the other hand, when the negative feedback strategy is used in
the formq. ++ \) £.
r. -- s,s.
% + 1 == 3,

1

Lr

x

,

(3)

the altered query retrieves relevant document 22, which, in turn, is used
to retrieve the remaining relevant items (21 and 1 ) . The process is illustrated in the output of Table 5(b), and the graphical representation ofFig. 5. The first nonrelevant item Cno. 125) is first identified by the user;

VII-24

Rank
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
32
33
200

0

Documents
1
2

3

125
12 I
159
64
66
123
67
65
24
29
190
25
127
136
85
21R
22R
1R 1

125 1
12 1
159 1
64 1
66 1
123 1
67 1
65 1
24 |
29 I
190 1
25 1
127 1
136 1
85 I
21R 1
22R 1
1R 1

125
12
159
64
66
123
67
65
24
29
190
25
127
136
85
21R
22R
1R

1

1

125
12
159
64
66
123
67
65
24
29
190
25
127
136
85
21R
22R
1R
1

a) "Increment Only" Strategy for Query 1(Initial Run (0) and three Feedback Runs (1-3))

Rank
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
32
33
199
200

Documents
1
2

0

Q i/^
12
159
64
66
123
67
65
24
29
190
25
127
136
85
21R
22R
0
1R

125
1 125
12 1
12
159
1
159
v\£y&
64 1
64
66
1 66
1
22R
22STl
22R
1 161
l ^ V \ 161
1 155 I fS$ y l 155
1 184 I 184- 1 184
1 189
l a ^ / i 189
1
70
21R 1 21&/1
i
4
IR i
/yh\
1 136
141 \ MXi
37
59 V ' 69
1
3130\ y 30
1
0
0
1
0
1
0
0
1
0
1
1R
0
1
0
1
21R
0
1
0
I

b)

3

11 .

I

"Decrement High" Strategy for Query 1(feedback only evaluation)"Decrement High" Strategy for Query 1
Table 5

VII-25b) First Negative
Feedback(document 125)a) Initial Search(no relevant
retrieved)c) Second Positive
Feedback(document 22)

Negative

•

query

O

relevant items©

relevant retrievecd) Third PositiveO
Feedback(document 1,21)

Feedback
Query 1
Fig. 5Illustration

non-relevant itemVII-26

as the query moves away from document 125, it approaches item 22, whose
rank improves from 33 to 6 between initial runs and first iteration. When
item 22 is identified as relevant after the first iteration, the otherrelevant items 1 and 21 increase their positions from ranks 199 and 200 to
11 and 12 (the top ten ranks are frozen by this time in the output of
Table 5(b)) .
The negative feedback strategy profits from the fact that in a reasonably homogeneous document space, the various alternative subject areas
should be reachable in a small number of negative feedback steps [14]. The
case of query 1 previously discussed renders plausible the large average
improvement shown for the 42 Cranfield queries in Fig. 4(b) between thenegative feedback strategy of equation (3) and the positive strategy ofequation (2). Fig 4(b) shows the first iteration curve using negative
feedback, compared with the second iteration positive strategy.

The im-provements in retrieval effectiveness exhibited in Fig. 4 for the variable
cut-off and negative feedback methods make it appear that the two strategies might be combined in an actual operational situation.
The feedback procedures described in the present section are likely,
substantially, to improve retrieval performance, over the presently achievable performance levels.

In some cases, the improvement may be as high as

30 percent in the high precision area and 20 percent in the high recall area.
The recall-precision graphs included in this study demonstrate, however, thatthe distance to the theoretically desirable ideal system is still large.
A perfect system, exhibiting both high recall and high precision may well
not be reachable in the near future.

VII-27

X document vector•

cluster ctfntroid

A typical query/Zf

Sample Clustered Document SpacePRECISION
4
5% search

(2,

(n)

\s<s

full searchsearch of nclusters- 3 0 % search! |\5)f\
recall ceiling

M l
1

1

LL

0.2

0.4

i

06

^

0.8

h-^ RECALL

10Cluster Search Evaluation(Cranfield 2 0 0 documents, 4 2 queries,
abstract stem process, 23 clusters)

Fig. 6

part of collection
actually searchedVII-28This is particularly true in view of the fact thatf in practice,time limitations make it impossible to compare the complete document filewith each search request, since system responses must be furnished to theuser population in real time.

In the SMART system, the documents in acollection are grouped into clusters, and only those document clusters aresearched which are situated close to the search request [12,15].

Such apartial search system, illustrated in Fig. 6, brings with it a built-in
ceiling in the attainable recall — since some relevant items may not be
included in the document groups which are actually searched.

Such partial

search systems, operating in conjunction with user feedback strategies remain to be studied experimentally, before being implemented in practice.
In the meantime, the search and retrieval methods included in the present
study may serve as a preview of the potential of the automatic retrieval
systems of the future.

VII

References[1]

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

[2]

M. E. Lesk, Operating Instructions for the SMART Text
Processing and Document Retrieval System, Scientific
Report No. ISR-11 to the National Science Foundation,
Section II, Department of Computer Science, Cornell
University, June 1966.

[3]

G. Salton et al., Scientific Reports on the SMART
System, Nos. ISR-11, ISR-12, ISR-13, Department ofComputer Science, Cornell University, June 1966,
June 1967, and December 1967.

[4]

C. W. Cleverdon and E. M. Keen, Factors Determining
the Performance of Indexing Systems, Vol. 2 — T e s t
Results, Aslib-Cranfield Research Project, Cranfield, 1966.

[5]

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

[6]

G. Salton and D. Williamson, Notes on the SMART-MEDLARS
Study, to be included in Scientific Report No. ISR-14
to the National Science Foundation, Department of Computer
Science, Cornell University, 1968.

[7]

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

[8]

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

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

[10]

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.

VII-30

References(contd)[11]

E. Ide, User Interaction with an Automated Information
Retrieval System, Scientific Report No. ISR-12 to the
National Science Foundation, Section VIII, Departmentof Computer Science, Cornell University, June 1967,[12]

G. Salton, Search Strategy and the Optimization ofRetrieval Effectiveness, Proceedings of the FID/IFIP
Conference on Mechanized Information Storage, Retrieval,and Dissemination, Rome, June 1967; also in Scientific
Report No. ISR-12 to the National Science Foundation,
Section V, Department of Computer Science, Cornell
University, June 1967.

[13]

H. A. Hall and N. H. Weiderman, The Evaluation Problem
in Relevance Feedback, Scientific Report No. ISR-12
to the National Science Foundation, Section XII, Department of Computer Science, Cornell University, June 1967.

[14]

J. Kelly, Negative Response Relevance Feedback, Information Storage and Retrieval, Scientific Report No. ISR-12
to the National Science Foundation, Section IX, Departmentof Computer Science, Cornell University, June 1967.

[15]

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