XII-1

XII.

Query Splitting in Relevance Feedback Systems
A. Borodin, L. Kerr and F. Lewis

Abstract
A modification of normal relevance feedback is presented.

It

is suggested that instead of simply modifying a query on each iteration,
two or more new queries may be formed.

Evaluation of experimental resultsshows this method produces some improvement.

A new measure is introduced

which permits extrapolation of these results to large document collections.
With regard to this measure, query splitting appears to be best suitedfor large systems.

1.

Introduction
Query splitting is an extension of the standard relevance feedback

procedure.

Instead of simply modifying a query on each iteration, two or

more new queries may be formed.
results.

Such a procedure often provides improved

Consider the example shown in Fig. 1.
Q is the original query.

If a simple feedback algorithm moves thequery toward one of the groups of relevant documents, then the relevant
documents in the other group will not be retrieved.
may not move significantly to either group.
replace Q with two queries, Q

and Q .

In fact, the query

Ideally, one would like to

The user then makes relevancejudgments on the documents retrieved by Q

and Q , and a relevance feed-back algorithm can be applied to Q

separately, producing newqueries Q

and Q .

and Q

XII-2x

represents relevant documents

A

represents queries

Query Splitting Example
Fig. 1

XII-3

Query splitting is beneficial when the relevant documents arelocated in distinct groups in the document space*merely hypothetical.
one topic.

Such a grouping is not

User requests may be general and deal with more thanMoreover, the structure of the document space is based on

predetermined correlation judgments which do not necessarily reflect theuser's conception of relevance.

Query splitting is not always required,of course, and indiscriminate use of the method may lead to inefficiencies.
Part of the query splitting strategy, therefore, is to decide when a queryshould be split.

2.

The Query Splitting Algorithm
As mentioned above, query splitting is embedded within a relevance

feedback system.

The system first reads in the user's initial query, Q .

New queries are then formed iteratively, as follows:1.

The documents in the collection are ranked according totheir correlation with Q..

2.

The five highest ranking documents, not previously retrieved,
are presented to the user for relevance judgments.

3.

The user indicates to the system which of the retrieved documents were relevant.

4.

The system examines these relevant documents to see if they form
distinct groups.

This decision is based on the document-document

correlations of the relevant documents, relative to the averagecorrelation between Q. and the first five documents retrievedxXII-4by Q. . If a document-document correlation does not exceed aconstant (TP) times the average query-document correlation, then
the two documents are considered to belong to separate groups.
In this way, the system clusters the relevant documents into
zero (if no relevant documents are retrieved), one, or several
groups.
For each groupj a new queryQ,

is formed according to

the relevance feedback formulaQi + i = Q I + 2_> • YJ "*where {r } represents the relevant documents in the group and{n } represents the two highest ranking nonrelevant documents
retrieved by Q..

If Q. retrieved no new relevant documents,

then just one new query is formed, using the negative feedback
formula,Q-•L

i+i = Qi -;kwhere {n } again represents the two top nonrelevant documents.
6.

The above steps are then repeated for each of the new queries
separately, with the exception that in step 2 only threedocuments are retrieved from each split query.

This avoids aproliferation of retrieved documents when query splitting occurs.
The query splitting algorithm used in the experimental analysis was
not as specific as the one presented above.

It allowed for more extensive

query splitting as well as a more general feedback formula. A descriptionof the program is given in the Appendix.

The algorithm described above wasderived by using the strategy which gave the best results after trying a
number of different parameter values.

XII-53.

Evaluation and Results
In order to implement and test the query splitting strategy, a

program was written to simulate the feedback portion of the SMART system.
The Cranfield thesaurus collection of 200 documents and 42 queries wasused to compare various strategies.

Final evaluation is provided by acomparison of the performance of relevance feedback with and without thequery splitting strategy.
Twenty-four of the forty-two queries in the Cranfield collection
produced some query splitting (i.e. two or more relevant documents wereretrieved on some iteration).

Evaluation is restricted to these twenty-

four queries, since for the other queries, regular feedback and query
splitting perform identically.

The following methods were compared:1.

Regular feedback.

2.

Query splitting with the threshold parameter TP = 1.5.

3.

Query splitting with TP = 0.75 (results in fewer splits).

One possible measure of performance is a "user measure" in which
recall and precision values are determined from the order in which theuser receives the documents.
difficult to establish.

Conventions for such ordering are not

Table 1 below shows the improvement over regularfeedback in the number of relevant documents retrieved, as a function of
the number of retrieved documents.
differences appear are listed.

Only the queries for which such

These results tend to favor query splitting,especially for larger numbers of retrieved documents.

XII-6

Increase in no. of rel. doc's retrieved
TP = 1.5

TP « 0.75

No. of doc's retrieved

No. of doc's retrieved

Query No.
5

10

15

20 25
-

3

10

15

20 25

-

+1

+2

+2 +2

-

-1 -1

+1

5

-

-1

-1

-1 -1

7

-

+1
-1

+2

+2 +2

13

5

15
16

.

-1

-

+1

+1 +1

-2

+2 +3

28
31
35
36
38

Total
Improvement

-

+1

0

-2

The User Measure
Table 10

0+1+1+2

XII-7

Another measure, better suited for evaluating overall system
performance, is obtained as follows:

recall and precision values arecomputed for the ranking of documents in each iteration, considering
previously retrieved documents to be removed from the document space.
The recall-precision curves averaged over 24
in Figs. 2 and 3.

search requests are shown

Once again, general improvement for 0.75 query splitting

is illustrated, while improvement for 1.5 query splitting is restricted
to the higher recall range.
There exist two reasons for believing that the previous results
tend to be meaningful:

1.

The Cranfield 200 is a small homogeneous collection which
provides neither the diversification of document space nor
the user population which leads to the type of generalrequest mentioned in the introduction.

2.

The measures used, especially the user measure, are too"sensitive" to the large number of documents retrievedin proportion to the size of the document space.

Fig. 4 illustrates how sensitive Query 7 is to the number of
retrieved documents per iteration.

Gross differences in recall and pre-cision occur depending on whether five or ten documents are retrieved
after the first iteration.

Moreover, Fig. 4 shows that Document 95 would

never be retrieved with regular feedback procedures in a large collection
if the document rankings were kept proportionate.

This is in contrast to

the performance of query splitting illustrated in Fig. 4b.

The document-

document correlations for the relevant documents of Query 7 are shown in Fig. 5.

XII-8Split with 1
Regular• 2nd Iterateo 3rd Iterate
A 4th IterateA

0.5 L.
hr"
0.4 h(gter^-——.
N> ^

^X^ ^
>. ^ ^

\x

c 0.3
o

CO

o

£0.2

"*~"~*-A

\

\.
X

\

r~

\

ys.

\^^.
\ X

\

\ V\
\

S

N#

^V

\ ^ «&
O\\\ *\ V1\T\ v . tA°i i" V

\

\

\

1

A

0.1 hh1

0.5

1

1

1

0.6
0.7
Recall

0.8

T

L-*.

0.9

Query Splitting (TP = 0.75) vs. Regular Feedback(averages over 24 queries)
Fig. 2

XII-9Split with TP = I.5
Regular• 2nd Iterateo 3rd Iterate
A 4th Iterate

0.5
0.4

J 0.3
O

£0.2r
0.1 h
j.

0.5

_L

0.6
0.7
Recall0.8

0.9

Query Splitting (TP = 1.5) vs. Regular Feedback(averages over 24 queries)

Fig. 3

XII-10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
35
38
44
50
66
92
130

Rank

Iteration Number

Rank
1

2

3

4

41* R
100*
90* R
111*
11*
45
110
127
104
192
71
159
42 R
76
133
185
176
83
196
156
72 R
0
95 R
0
0
0
0

41 R
90 R
156*
91*
96*
199*
29*
60
23
109
72 R
95 R
193
42 R
56
155
11
188
141
184
0
0
0
0
0
0
0

100
127*
187*
41 R
196*
24*
128*
72 R
103
39
26
17
170
99
84
154
104
158
83
69
0
0
0
95 R
0
42 R
90 R

90 R
42*R
11
41 R
199
156
188*
45*
111
100
29
173*
39*
104
192
71
159
176
184
76
0
72 R
0
0
95 R
0
0

Regular Feedback

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
24
25
29
35
37
44
59
60
79
86
89
102
137

b)

Iteration

Split
Subqueries

1

2

3

41*R
100*
90*R
111*
11*
45
110
127
104
192
71
159
42 R
76
133
185
176
83
196
156
0
0
0
72 R
0
95 R
0
0
0
0
0
0
0

41 R
100
71*
111
39*
83*
25
84
110
29
155
127
45
156
92
114
153
23
192
90 R
72 R
0
0
0
95 R
0
42 R
0
0
0
0
0
0

90 R
91*
11
111
95*R
93*
110
94
192
195
159
109
104
100
76
96
121
199
176
82
0
0
41 R
Q
42 R
0
0
72 R
0
0

a
0
0

Query Splitting (TP = 0.75)

Indicates Retrieved Document
Sensitivity of Number of Retrieved Documents per Search Iteration
Fig. 4

XII-11

A new measure is introduced which attempts to capture the notionof "relative improvement" between iterations.
with initial rank R.

Consider a relevant document

Suppose one iteration of relevance feedback causes

the document to attain a new rank of R/3.

Then if subsequent iterations

sustain this "rate of convergence", the number of iterations required toretrieve the document is the leastiwhich satisfied(1/3) 1 R <_ n
where

n

is the number of documents given to the user.

the rate of convergencer

For this example,

is 1/3.

In the case of query splitting, the descendents become independent
queries, each with its own rate of convergence for any previously unseen
relevant document.
of convergence.

The best of these rates is taken to be the true rate

This is justifiable, since query splitting is designed

to iterate towards individual groups, and the document need only be retrieved by one of the split queries.

However, to be consistent withregular feedback, a document is considered to be retrieved only when its
rank becomes less than n/S where S is the number of queries into which theoriginal query was split.

weak
mediumstrongQuery 7
Correlations Between Relevant Documents of Fig. 4
Fig. 5XII-12

Formally, let r be the expected rate of convergence, and assume thatr is maintained throughout all iterations. This assumption may not be completely valid; however, it was found, experimentally, that r is maintained
at least as well for query splitting as it is with regular feedback. A
document with initial rank R will be retrieved withiniiterations if(r)1- R £ n/S
where S is the expected number of queries generated in the splitting process.
Algebraic manipulation yields
log (R/n) + log S- log rSince

r < 1, log r is negative.

ment

M = - log r.

This motivates defining a rate of improve-

From the experimental results, values of r and S were obtained foreach query, for the three methods. Then
parameter K1 = log (R/n).

i was computed in terms of a

These values ofi were averaged over theseventeen queries of the original twenty-four which did not retrieve all
relevant documents on the first iteration, and the average , I, was plottedagainst K1 for each method.

The results are shown in Fig. 6.

Since I (the average number of iterations) is an indication of
retrieval effort, the best method is the one which yields minimal values ofI.

The curves of Fig. 6 show that query splitting is not beneficial unless

K1 > 2.2, i.e. R/n > 150. Since R is the same order of magnitude as the size

XII-13average numberof iterations
I , 5 = 4.40K' 4 1.79
0 . 7 5 s 4 - 9 0 K ' +0.70= 5.21 K*

I-0.75 split
regular feedbackII
2
3
K' (= log R/n)Expected

Iterations

Requiredfor Relevant

Fig. 6-L-^K'

Document

RetrievalXII-14of the document collection, this means that in large collections/ query
splitting would probably produce better results than those obtained with
the Cranfield 200, for which K' * 1.

4.

Conclusions and Suggestions for Further Research
As in all systems, one must weigh expected gains against the costof a proposed improvement.

Although the query splitting algorithm iseasy to implement, the cost of the increased computing time may prove
prohibitive.

However, the algorithm can be readily modified for use withclustered document spaces.

In this form, it should be realistically con-sidered for use with the large collections for which query splitting appears
to be most appropriate.
The following topics are suggested for further research:1.

Some scheme for dropping nonproductive queries would resultin improved precision and a reduction in computing time.

2.

A potentially useful modification would consist in generatingby negative feedback an additional query on each iteration.
Such a strategy might retrieve documents which could not be
retrieved in any other way.

These queries would have ahigher probability of being nonproductive, however, so thismodification should be implemented in conjunction withsuggestion 1.
3. A better understanding of the topology of relevant documentsin the document space might lead to more complex but more
efficient query splitting strategies.

XII-15

References[1]

S. Friedman, J. Maceyak, S. Weiss, A Relevance Feedback
System Based on Document Transformation, Information
Storage and Retrieval, Report ISR-12 to the National
Science Foundation, Section X, Department of Computer
Science, Cornell University, June 1967.

[2]

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

[3]

E. Ide, User Interaction with an Automated Information
Retrieval System, Information Storage and Retrieval,
Report ISR-12 to the National Science Foundation,
Section VIII, Department of Computer Science, Cornell
University, June 1967.

[4]

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

[5]

G. Salton, Search and Retrieval Experiments in RealTime Information Retrieval, Technical Report 68-8,
Department of Computer Science, Cornell University,
February 1968.

XII-16

Appendix
A Brief Introduction to the FALTER System

1.

Introduction
The FALTER system was developed as a programming device used totest the feasibility of query splitting.

In order to thoroughly checkthis idea, a general purpose experimental system was required.
Flexibility, simplicity, and modularity are maintained throughout
the system.
main program.

It consists of ten independent subroutines controlled by a
The interfaces between the routines are exceedingly simple

so that modifications and substitutions can be made easily*
Every aspect of the relevance feedback portion is input controlled.
Also, the amount of output can be indicated through input parameters.
These features will be described below.

2.

General Algorithm
The FALTER system is built on a skeleton of relevance feedback, pro-ducing new queries according to the formula:
na

nb

lna

E-

Q. . = 7TQ. + 030 +
w
i+l
*i
*o

lnb

A method of query splitting has been added to the standard relevance
feedback mechanism.

This is done by first clustering the relevant documents

retrieved by the query using the correlation coefficient for this purpose.
The above formula is applied to produce the new queries taking one cluster at
a time.

XII-173.

System Operation
The main portions of the system are indicated by the flow chartof Fig. 7.

Some of the options in the system are described below:a)

All of the constants (ALPHA, MU, NA, etc.) are read inby the program.

b)

The numbers of iterations desired, documents retrieved,
queries processed are read in also.

c)

Splitting is controlled by input parameters.

d)Three levels of output are provided as a trace feature.
These levels are selected by input.

A listing of the routines follows:1.

Main ProgramThis routine controls operation, input and output.
Variables involved:
PI, ALPHA, MU, OMEGA, NA, LNA, NB, LNB are feedback
constants
NUMIT - number of iterations
IRUN - number of queries
NUM - # docs retrieved/iteration
HINUM - # docs retrieved without split
LONUM - # docs retrieved/query on split
NNUM - length of output-chartISW =ITRACE =012

positive feedback only
standard split - no negative
regular feedback - no split-1 final output
0 slight trace
1 much output

TP - controls split (set to 0.75)

NEWQRY
This routine reads in information about a query.
TITLE - the query itself
NUMSEQ - its sequence # (1,2,3,etc.)
NUMCOL - its "collection #"CONCPT - the concepts
WGHT - their weights
SUMSG - sum of weights squared
NUMREL - # of relevant documents
RELDOC - the relevant documents
INDOCSThis routine reads the documents in to a structure as below:
ISPACE\y Sequence ## concepts
concept 1 1
weight 1
.
IDISP
1
•
•

.
I

\ Sequence ## concepts
concept•

These are the document space and display table
SOCSQ - sum of weights squared for documents«•

XII-19

CORLAT
A document-document correlation according to:z< ) Vd. d!
1

1

COSINEA query document correlator according to:Ld. • q.
l^i

L< "L<The result is a list of the document numbers:
DOCNUM and the correlations:

CORR

SORT
2
Simple n /2 sort on CORR and DOCNUM

PUTOUT
Output chart LIST made up from DOCNUM with correlations
in ACORR and relevance indication in ISRELJJRELChecks the relevance of a document and returns an R
where applicableFEDBAK
Performs vector modification and constructs new queryUANLIZ
The relevant and irrelevant documents retrieved are indicatedin IREL and JREL and they are noted in GOTITCONSOL
Sorts part of output array

STRTGYThe splitting routine which determines the query structure
for this iteration using clustering operation

REGFDBSet up constants

CONST
Set up constants

EVAL
Executive routine for system which merges split queries into
a composite query, and computes recall and precision values