ISR-9
August 1965
XIX-COMBINATIONS OF ANALYSIS METHODS - THE MERGED OUTPUT RESULTS
J.J.

1.

Rocchio, J r .

Introduction
One of the most interesting features of automatic indexing in document

retrieval is the flexibility it permits in the generation of index images ofdocuments and search requests. The SMART system is designed to take advantageof this flexibility, and one of its principal aims is to study the effect ofvarious information analysis procedures on retrieval performance.

In addition

to investigating the gross retrieval characteristics of various indexing
techniques, it is interesting to examine their fine structure as reflected,
for example, in their retrieval performance with respect to particularrelevant documents. This is particularly appropriate in light of the factthat an operational retrieval system may require a variety of techniques
adaptable to a wide spectrum of users' information needs. One of the means
for measuring the detailed behavior of a particular sequence of analysis
methods is to consider their joint behavior under the assumption that a given
user will first use method A, and will then switch to method B If the original
search results were found wanting. This method has been investigated by using
some of the initial results obtained with the SMART system after "merging"
the retrieval results obtained from different procedures into an effective
combined result. The present section outlines the merging technique, anddescribes some of the results which have been obtained.

XIX-22.

The Merging Process
The details of the merging procedure for the retrieval results

obtained from various analysis methods, as well as characteristics of thecomputer program which performs the merging operation, are described inSec. XVIII of this report.

In summary, the retrieval results for an experi-mental run using the SMART system consist of an ordering of the documentsof the source collection with respect to the input query. The combined
result for m-different methods is defined by an m-way merge of the ordered
list of document identifiers pertaining to each individual method, such thatin the merged list each document identifier is represented only once with arank determined by its highest rank in one of the original lists (see Fig. l ) .

Example Illustrating the Two Possible
Merges of Two Individual Lists
Figure 1XIX-3
The result of such an m-way merge is then again an ordered list of document
identifiers, which is taken to be the compos it or effective result of them methods combined. Such a merge is somewhat sequence dependent, in thatthe resultant ordering is a function of the sequence in which the m component
methods are considered (see Fig, 1 ) . However, when m is small compared to
the number of items to be merged, this sequence dependency does not seriously
affect the evaluation measures derived from the resultant list.
By considering the nature of this merging process, some general
conclusions can be drawn. In particular, a document which has a minimal rank
index i in a set of m-individual methods can have at most a rank index ofin- i in the ordered merged list. Thus the rank position of a document in a
combined method is a function of its best ranking (lowest rank index) overall component methods. This is illustrated in Fig. 2, which shows the ranksof the relevant documents for the request "Automata Phrases/1 for each of
three simple methods, and for the merged result of all three. It should benoted, for example, that document 264 is ranked 74th under "Harris TWO,"
64-th under Stat. "Phrases," and first under "Hierarchy Up."In the combined

result it receives rank 3, indicating that "Hierarchy Up" was last in themerging order.

It is clear that the rank list of relevant documents will

be improved by the merging process, if the individual methods are successful
in identifying different subsets of the relevant set for the input query*
In the case where a given method dominates all others, that is, retrieves
every relevant document with the highest rank (lowest rank index), the merging
procedure is likely to produce worse, or certainly not better combined

XEC-4Query:

Automata Phrases
Rank Position in Retrieved Ordering

Relevant
Document
NumberHarris
TwoHierarchyUp

Stat
PhraseH2 + Up+ Stat

316

122

1129

2

594313
176

3225U
750

85868

1371
372

26116

3241
315

29381337421963915741 264.

74

164

3Ranks of Relevant Documents f o r Search Request"Automata P h r a s e s " Under Three A n a l y s i sMethods and the Merged R e s u l t
Figure 2results. Comparisons of the combined retrieval effectiveness for sets ofalternative analysis procedures provide a measure then of the potential
usefulness of incorporating these methods into an operational retrieval
system.

3. Sample Results
Figure 7 of Sec. XXIV of this report presents in summary form resultsof SMART system retrieval experiments for a sajnple of 17 search requests.
Data are presented for six analysis procedures, including the thesaurus mapping(Harris Two), the word stem mapping (Null Thes.), the addition of phrases

detected by concept-concept cooccurrence (Stat. Phrases), the addition ofphrases detected by syntactic matching (Syntax Phrases), the search request
transformation by means of adding related "more general11 terms from theconcept hierarchy (Hierarchy UP), and the request transformation by meansof adding related "more specific" terms from the concept hierarchy (Hier.
down)*In addition, 13 two-way merges and nine three-way merges of thesesix basic methods are included.

Note that all of these indexing methods aretransformations of the concept space defined by the thesaurus with theexception of the method labeled "Null Thesaurus." This last indexing
transformation is for a distinct space defined by the detection of uniqueword stems from the source collection.
The summary data for the single and combined methods may be presented
in the form of "Quasi-Cleverdon" graphs, or as averages of various evaluation
measures (see Sees. Ill and IV of Information Storage and Retrieval, Report
No. ISR-8). Figure 3 presents a summary of the relations of the various
merges to their component measures. In this figure improvement, represented
by a "+," indicates that a higher normalized recall or precision value wasobtained for the merged method compared to the individual simple ones.

Itis evident that with the exception of some of the merges involving the two
hierarchy methods, the merging process provides general improvement.
In terms of the normalized precision evaluation, measure (the moresensitive of the two normalized measures), the best single method is the"Stat. Phrase" option. The best merged pair is obtained by combining the"Stat. Phrase" method with the "Null Thes." method, and this In fact turns

XIX-6rOu
J=»

£«5O

•i

Q
rH0
•H

H0W

«Hiw,+

^

1i

1 Qo
^
0i

•H+1+i1I^-N+—.~ji|

10
•Hi

1

1ii

4--f-P£
CO+++4-

4-i

j+

1i

H+*1o•-

HrH3arrHCG•H4-^K

4-

1+-p-prHcd+3COflCO+CN;:r:3s-P0r-\—Cu&4-rHr-i03O10)H

1 c!
01 >*-Hco jxj+++ £ooQ

^0
•H

*1w

coo5|0H
G
013w

o pu
rrj

4-0

^ 'CS3•HCO r H0 03
Bo

£<

^UOC!

+l 3rHrH4^
CJ

33>»
CO+
4-4-4-+rHr-i

1-pOd03-P

3 :°+OQCO•H+++UCNCMC\iw

WWcv&w0)

uorH0

co00;

a o ±>• H OH O3r^
O
•Ho-H

1 - P TJ
^ j dcitiO-H&>

CO « H0rH *CO - ^ - —CHcrj
0COdcoHOrHO -H -H
0 co o3
T3 - H P^
OHC)

0rH+ rd--^ 00 rH
co cd
cd B
0rH

IBUJM

£S3CO « H

^w0rH
HtSJ
03
•H
W X lrH -H
O
03 rH
SiH
O
rH OJ
aT30

Q* W

EHP.

d•cd—,0r
O HW)^ >soK ^nrj, ^^~N"£
0 3 JH0-P -H
CO M

H0OrHaO-HCO-HO0H—0H^CJ«H03-pH£4^
CO0+ |•A

H^+4-L;

l J3— - tiO•HCO H+3i-P•H+rHs;1CH4->
1 03U+cd

H>>*H
CO j r j

rHa oo-Pcd-PCOO0 aN •H•H
H
03 cdrj.ar

1ffl+'V

4-1rH9SrHr H T3Cd 00)
rHd,t3•£CO- P 'TD<P O0 XI
rH - P+txj

0B^

cdd££r5H
Oo arH0g0-pHr5COCD«Cr>

CDPHt3m•Hrr<XIX-70•HH (i)H 3cd cvo0)

oHc-c ^H
•CD>
CDO

CD>

rHOdO-H

1CQ>ru0)bfl•H -H cti
CQ
O U03

CD^—"NMu wQ)

3 JH >
0> Ps <u'<*+ -P
O ctf;S: - P
£H CO

00

CO +•H?H r H-£>••(•>

•i
CD.

vO

Ho
* oUA

«H
HaJ
O03

-^"-cn-Oi••.

oL;0L-^i-vOao•HCO•Hoa;
PHC\i)

H•>11 XI
CD - Pr H CDup^•t•H r 7 j
CO CDttO- P FH
CO 0CD

mparis n of t e Be
Tri le-mo
XJ.dooocu

U::::
(;"!
•T -1

frries

XIX-HHCD3

cd O 'ofloCD r£ Ho• !Hr-> CO CD0)T"5;• >> S3 Oo0

H o '.-•5O •H CD
iro 1 0•i 4 • H
cdCO O ucd 0) '!)d U >a> m - 1

Recall for Harris Two
Combination

CO1 voH
H4- -^CO^cdO

3 -H

CDU xJ0 EH-rJ

CO> rd+ cvoo^COsOao•HCO• H(J0-tCMO

Quasi-Cleverdon Precisio
Stat Phrase, ad ai. r^

U \CD0PHdbfl•H&W

XIX-9+ o

Recall for Nu 11 Thesombination4-tt)

•r•

*' 3

• i Nm>v(JHi-t•<Y\0cv••*O00

sfsOHo•HCO•HO0JH
PHrr>

C\J(1)/..I

PHrH>
a 'Ou ^*•>

CO-\Ho'!)'>1£H

aQuas •Cleve don Pr ecisiot Phrase. anHH0•HP^

XIX-10out to give the maximum normalized precision over all 27 methods presented.
The best three-way merge results from the combination of the "Harris Two"
method with the "Null Thes." and nStat. Phrases" methods, and this yields
the second highest average normalized precision. The "Quasi-Cleverdon"
precision versus recall graphs for these three methods are shown in'Fig. 4.
Figures 5 and 6 show the precision versus recall curves for Harris Two,
Stat. Phrases and their merge, and Null Thes., Stat. Phrase and their merge,respectively.

In each of these cases it is important to note that at certain

recall levels the merged method results in. higher precision than either ofits components, the improvement being more marked in Fig. 6.

U*Conclusions

The results obtained to data, illustrated in the present section,
support the hypothesis that combinations of alternative information analysis
procedures can provide improved retrieval characteristics. Specifically, themerging of certain of the retrieval options available in the SMART system haveshown marked improvement over the individual component methods. These results
suggest that document retrieval systems be equipped with a set of analysis
procedures capable of being employed in user directed sequences, as opposed
to using a single, fixed indexing technique*