Five
SEARCH STRATEGIESIntroduction

So far very little has been said about the actual process by which therequired information is located. In the case of document retrieval theinformation is the subset of documents which are deemed to be
relevant to the query. In Chapter 4, occasional reference was made tosearch efficiency, and the appropriateness of a file structure forsearching. The kind of search that is of interest, is not the usual kind
where the result of the search is clear cut, either yes, the item ispresent, or no, the item is absent. Good discussions of these may befound in Rnuth 1 and Salton2. They are of considerable importancewhen dictionaries need to be set-up or consulted during text processing.
However, we are more interested in search strategies in which the
documents retrieved may be more or less relevant to the request.
All search strategies are based on comparison between the query andthe stored documents. Sometimes this comparison is only achieved
indirectly when the query is compared with clusters (or more precisely
with the profiles representing the clusters).
The distinctions made between different kinds of search strategies
can sometimes be understood by looking at the query language, that is
the language in which the information need is expressed. The nature of
the query language often dictates the nature of the search strategy. For
example, a query language which allows search statements to be
expressed in terms of logical combinations of keywords normallydictates a Boolean search. This is a search which achieves its results bylogical (rather than numerical) comparisons of the query with the
documents. However, I shall not examine query languages but instead
capture the differences by talking about the search mechanisms.
Boolean search

A Boolean search strategy retrieves those documents which are ‘true’81

SEARCH STRATEGIES

for the query. This formulation only makes sense if the queries are
expressed in terms of index terms (or keywords) and combined by theusual logical connectives AND, OR, and NOT. For example, if thequery Q = {KX AND /f2) OR (K 3 AND (N0T /f4)) then the Boolean
search will retrieve all documents indexed by K\ and K2, as well as all
documents indexed by K 3 which are not indexed by K4.
Some systems which operate by means of Boolean searches allow theuser to narrow or broaden the search by giving the user access to a
structured dictionary which for any given keyword stores related
keywords which may be more general or more precise. For example, inthe tree structure in Figure 5.1, the keyword K\ is contained in the
more general keyword K \, but it can also be split up into 4 more
precise keywords K], K \, K \ , and K \. Therefore, if one has aninteractive system the search can easily be reformulated using some ofthese related terms.
.0

3

A

Figure 5.1. A set o f hierarchically related keywords

An obvious way to implement the Boolean search is through theinverted file. We store a list for each keyword in the vocabulary, and ineach list put the addresses (or numbers) of the documents containingthat particular keyword. To satisfy a query we now perform the set
operations, corresponding to the logical connectives, on the A)-lists. For
example, if
K i -list ! D \, F)2, D 3, D 4
K 2~list : D X, D 2
A"3—list : D u D 2, D 3^ 4 - l i s t : £>1

and Q = (K, AND K2) OR (K 3 AND (NOT K 4))
82

SEARCH STRATEGIES

then to satisfy the (K 3 AND K 2) part we intersect the K x and K 2 lists,
to satisfy the (K 3 AND (NOT Ka)) part we subtract the K 4 list fromthe K 3 list. The OR is satisfied by now taking the union of the two setsof documents obtained for the parts. The result is the set {Dlt D2, D3}
which satisfies the query and each cocument in it is ‘true’ for the query.
A slight modification of the full Boolean search is one which only
allows AND logic but takes account of the actual number of terms thequery has in common with a document. This number has become
known as the co-ordination level. The search strategy is often called
simple matching. Because at any level we can have more than one
document, the documents are said to be partially ranked by theco-ordination levels.
For the same example as before with the query Q = K X AND K 2
AND K 3 we obtain the following ranking:Co-ordination level3

D u D2

2

D3

1

Da

In fact, simple matching may be viewed as using a primitive
matching function. For each document D we calculate \D n Q\, that is
the size of the overlap between D and Q, each represented as a set of
keywords. This is the simple matching coefficient mentioned in
Chapter 3.
Matching functions
Many of the more sophisticated search strategies are implemented bymeans of a matching function. This is a function similar to an
association measure, but differing in that a matching function measures
the association between a query and a document or cluster profile,whereas an association measure is applied to objects of the same kind.
Mathematically the two functions have the same properties; they only
differ in their interpretations.
There are many examples of matching functions in the literature.
Perhaps the simplest is the one associated with the simple matching
search strategy.
If M is the matching function, D the set of keywords representing
the document, and Q the set representing the query, then:SEARCH STRATEGIES

is another example of a matching function. It is of course the same as
Dice’s coefficient of Chapter 3.
A popular one used by the SMART project, which they call cosine
correlation, assumes that the document and query are represented as
numerical vectors in r-space, that is Q = (q\, q
j <?f ) andD = (di, d 2, ■. d t ) where qt andare numerical weights associatedwith the keyword i. The cosine correlation is now simplyt
Z Qi d i'

1=1

r = -------------------------- 7( z=i (mf (=iidi?
)2
i
*
m

or, in the notation for a vector space with a Euclidean norm,(Q, D)' “ iic iriM =cosine#where 6 is the angle between vectors Q and D.

Serial search
Although serial searches are acknowledged to be slow, they are
frequently still used as parts of larger systems. They also provide aconvenient demonstration of the use of matching functions.
Suppose there are N documents Dt in the system, then the serial
search proceeds by calculating N values M(Q, £),) for i - 1 to N. In
other words the matching function is evaluated at each document forthe same query Q. On the basis of the values M(Q, D,) the set of
documents to be retrieved is determined. There are two ways of doingthis:( 1) the matching function is given a suitable threshold, retrieving
the documents above the threshold and discarding the ones
below. If T is the threshold, then the retrieved set B is the set{D i\M (Q , D i ) > T }( 2) the documents are ranked in increasing order of matching
function value. A rank position R is chosen as cut-off and all
documents below the rank are retrieved so that B = {Df|r(/) < R }where r(i) is the rank position assigned to Dt. The hope in eachcase is that the relevant documents are contained in the
retrieved set.
84

SEARCH STRATEGIESThe main difficulty with this kind of search strategy is the
specification of the threshold or cut-off. It will always be arbitrary since
there is no way of telling in advance what value for each query willproduce the best retrieval.
Ouster representatives

Before' we can sensibly talk about search strategies applied to clustereddocument collections, we need to say a little about the methods used torepresent clusters. Whereas in a serial search we need to be able tomatch queries with each document in the file, in a search of a clustered
file we need to be able to match queries with clusters. For this purpose
clusters are represented by some kind of profile (a much overworked
word), which here will be called a cluster representative. It attempts tosummarise and characterise the cluster of documents.
A cluster representative should be such that an incoming query will
be diagnosed into the cluster containing the documents relevant to thequery. In other words we expect the cluster representative todiscriminate the relevant from the non-relevant documents whenmatched against any query. This is a tall order, and unfortunately there
is no theory enabling one to select the right kind of cluster
representative. One can only proceed experimentally. There are anumber of ‘reasonable’ ways of characterising clusters; it then remains amatter for experimental test to decide which of these is the mosteffective.
Let me first give an example of a very primitive cluster
representative. If we assume that the clusters are derived from a cluster
method based on a dissimilarity -measure, then we can represent eachcluster at some level of dissimilarity by a graph (see Figure 5.2). Here
A

B

-

^

/

Figure 5.2. Examples o f maximally linked documents as cluster representatives

85

SEARCH STRATEGIES

A and B are two clusters. The nodes represent documents and the line
between any two nodes indicates that their corresponding documents
are less dissimilar than some specified level of dissimilarity. Now, one
way of representing a cluster is to select a typical member from thecluster. A simple way of doing this is to find that document which is
linked to the maximum number of other documents in the cluster. A
suitable name for this kind of cluster representative is the maximallylinked document. In the clusters A and B illustrated there are pointersto the candidates. As one would expect in some cases the representative
is not unique. For example, in cluster B we have two candidates. To deal
with this, one either makes an arbitrary choice or one maintains a list ofcluster representatives for that cluster. The motivation leading to thisparticular choice of cluster representative is given in some detail in Van
Rijsbergen3 but need not concern us here.
Let us now look at other ways of representing clusters. We seek amethod of representation which in some way ‘averages’ the descriptionsof the members of the clusters. The method that immediately springs tomind is one in which one calculates the centroid (or centre of gravity)of the cluster. If { A , D 2, .. ., D„}are the documents in the cluster andeach Dj is represented by a numerical vector (d2, d 2, . .., d t ) then thecentroid C of the cluster is given by
1

4n

”

Pi
£ HAH

where ||Z),|| is usually the Euclidean norm, i.e.
\ \ Di W=\ / d\ +dl +. . . + d 2t
More often than not the documents are not represented by numerical
vectors but by binary vectors (or equivalently, sets of keywords). In
that case we can still use a centroid type of cluster representative but
the normalisation is replaced with a process which thresholds thecomponents of the sum 2 A - To be more precise, let A now be abinary vector, such that a 1 in the /th position indicates the presence ofthe /th keyword in the document and a 0 indicates the contrary. The
cluster representative is now derived from the sum vectorns= £ ai =1(remember n is the number of documents in the cluster) by thefollowing procedure. Let C= (ci,c2„ . . ct ) be the cluster
86

SEARCH STRATEGIES

representative and [Z),-]y the /th component of the binary vector
then two methods are:n
1 if X [A ] ; > 1
1=1

( 1)

ci = .0 otherwiseorn

1 if X [A]/>log2«
( 2)

1= 1.

c/ = .0 otherwise

So, finally we obtain as a cluster representative a binary vector C. In
both cases the intuition is that keywords occurring only once in thecluster should be ignored. In the second case we also normalise out thesize n of the cluster.
There is some evidence to show that both these methods ofrepresentation are effective when used in conjunction with appropriate
search strategies (see, for example, Van Rijsbergen4 and Murray5).
Obviously there are further variations on obtaining cluster
representatives but as in the case of association measures it seems
unlikely that retrieval effectiveness will change very much by varying
the cluster representatives. It is more likely that the way the data in thecluster representative is used by the search strategy will have a larger
effect.
Finally, it should be noted that cluster methods which proceed
directly from document descriptions to the classification without firstcomputing the intermediate dissimilarity coefficient, will need to makea choice of cluster representative ab initio. These cluster representatives
are then ‘improved’ as the algorithm, adjusting the classificationaccording to some objective function, steps through its iterations.

Cluster-based retrieval
Cluster-based retrieval has as its foundation the cluster hypothesis,
which states that closely associated documents tend to be relevant tothe same requests. Clustering picks out closely associated documents
and groups them together into one cluster. In Chapter 3, I discussed
many ways of doing this, here I shall ignore the actual mechanism ofgenerating the classification and concentrate on how it may be searchedwith the aim of retrieving relevant documents.
87

SEARCH STRATEGIESSuppose we have a hierarchic classification of documents then asimple search strategy goes as follows (refer to Figure 5.3 for details).
The search starts at the root of the tree, node 0 in the example. It
proceeds by evaluating a matching function at the nodes immediately
descendant from node 0, in the example the nodes 1 and 2. Thispattern repeats itself down the tree. The search is directed by a decision
rule, which on the basis of comparing the values of a matching function
at each stage decides which node to expand further. Also, it is necessary
to have a stopping rule which terminates the search and forces aretrieval. In Figure 5.3 the decision rule is: expand the nodeM(Q,2)>M(Q, 1)
M I Q, 2) > M(Q.0)

Continue

M(CU) >M(Q,3)
M(Q,4)>M(Q, 2)
Continue
M ( Q , S ) , M (Q ,6),M (Q ,7 ) < M (C U )Stop. Retrieve duster A

F ig u re 5.3. A search tre e and th e a p p ro p ria te values o f a m a tc h in g f u n c t io n illu s­
tra tin g th e a c tio n o f a d e cis io n ru le a n d a s to p p in g ru lecorresponding to the maximum value of the matching function
achieved within a filial set. The stopping rule is: stop if the current
maximum is less than the previous maximum. A few remarks about thisstrategy are in order:( 1) we assume that effective retrieval can be achieved by finding justone cluster;( 2) we assume that each cluster can be adequately represented by acluster representative for the purpose of locating the cluster
containing the relevant documents;(3) if the maximum of the matching function is not unique somespecial action, such as a look-ahead, will need to be taken;(4) the search always terminates and will retrieve at least one
document.
88SEARCH STRATEGIESAn immediate generalisation of this search is to allow the search toproceed down more than one branch of the tree so as to allow retrievalof more than one cluster. By necessity the decision rule and stopping
rule will be slightly more complicated. The main difference being thatprovision must be made for back-tracking. This will occur when the
search strategy estimates (based on the current value of the matching
function) that further progress down a branch is a waste of time, atwhich point it may or may not retrieve the current cluster. The searchthen returns (back-tracks) to a previous branching point and takes analternative branch down the tree.
The above strategies may be described as top-down searches. A
bottom-up search is one which enters the tree at one of its terminal
nodes, and proceeds in an upward direction towards the root of thetree. In this way it will pass through a sequence of nested clusters ofincreasing size. A decision rule is not required; we only need a stopping
rule which could be simply a cut-off. A typical search would seek thelargest cluster containing the document represented by the starting
node and not exceeding the cut-off in size. Once this cluster is found,the set of documents in it is retrieved. To initiate the search in response
to a request it is necessary to know in advance one terminal nodeappropriate for that request. It is not unusual to find that a user will
already know of a document relevant to his request and is seeking otherdocuments similar to it. This ‘source’ document can thus be used toinitiate a bottom-up search. Unfortunately, very little is known about
the effectiveness of the bottom-up search strategy. The author has donesome preliminary experiments but found it difficult to evaluate theresults.
If we now abandon the idea of having a multi-level clustering andaccept a single-level clustering, we end up with the approach to
document clustering which Salton and his co-workers have worked on
extensively. The appropriate cluster method is typified by Rocchio’s
algorithm described in Chapter 3. The search strategy is in part a serial
search. It proceeds by first finding the best (or nearest) cluster(s) andthen looking within these. The second stage is achieved by doing a serial
search of the documents in the selected cluster(s). The output isfrequently a ranking of the documents so retrieved.

Interactive search formulation
A user confronted with an automatic retrieval system is unlikely to beable to express his information need in one go. He is more likely towant to indulge in a trial-and-error process in which he formulates his
query in the light of what the system can tell him about his query. The
89
IR -7

SEARCH STRATEGIES

kind of information that he is likely to want to use for thereformulation of his query is:(1) the frequency of occurrence in the data base of his search terms;(2) the number of documents likely to be retrieved by his query;(3) alternative and related terms to be the ones used in his search;(4) a small sample of the citations likely to be retrieved; and(5) the terms used to index the citations in (4).
All this can be conveniently provided to a user during his search session
by an interactive retrieval system. If he discovers that one of his searchterms occurs very frequently he may wish to make it more specific byconsulting a hierarchic dictionary which will tell him what his options
are. Similarly, if his query is likely to retrieve too many documents hecan make it more specific.
The sample of citations and their indexing will give him some idea ofwhat kind of documents are likely to be retrieved and thus some idea of
how effective his search terms have been in expressing his informationneed. He may modify his query in the light of this sample retrieval. This
process in which the user modifies his query based on actual search
results could be described as a form of feedback.
Examples, both operational and experimental, of systems providing
mechanisms of this kind are MEDLINE6 and MEDUSA7 both based on
the MEDLARS system.
We now look at a mathematical approach to the use of feedback
where the system automatically modifies the query.

Feedback

The word feedback is normally used to describe the mechanism bywhich a system can improve its performance on a task by taking
account of past performance. In other words a simple input-output
system feeds back the information from the output so that this may be
used to improve the performance on the next input. The notion of
feedback is well established in biological and automatic control
systems. It has been popularised by Norbert Wiener in his book
Cybernetics. In information retrieval it has been used with considerable
effect.
Consider now a retrieval strategy that has been implemented bymeans of a matching function M. Furthermore, let us suppose that boththe query Q and document representatives D are r-dimensional vectors
with real components where t is the number of index terms. Because it
is my purpose to explain feedback I will consider its applications to aserial search only.
90SEARCH STRATEGIESIt is the aim of every retrieval strategy to retrieve the relevant
documents A and withhold the non-relevant documents A.
Unfortunately relevance is defined with respect to the user’s semanticinterpretation of his query. From the point of view of the retrieval
system his formulation of it may not be ideal. An ideal formulation
would be one which retrieved only the relevant documents. In the caseof a serial search the system will retrieve all D for which M{Q, D )> T
and not retrieve any D for which M(Q, D) < T, where T is a specified
threshold. It so happens that in the case where M is the cosine
correlation function, i.e.
M(Q, D) =(Q,D)

II211 llflllllien nonX(q xd x + q 2d 2Qtdt)>

the decision procedure
M (Q ,D )-T > 0
corresponds to a linear discriminant function used to linearly separate
two sets A and A in R * . Nilsson8 has discussed in great detail how
functions such as this may be ‘trained’ by modifying the weights q{ todiscriminate correctly between two categories. Let us suppose for the
moment that A and A are known in advance, then the correct query
formulation Q0 would be one for which
M(Q0, D ) > T

wheneverD e A

M(Q0, £)) < T

whenever D e A

and
The interesting thing is that starting with any Q we can adjust it
iteratively using feedback information so that it will converge to Q0.
There is a theorem (Nilsson8, page 81) which states that providing Q0
exists there is an iterative procedure which will ensure that Q will
converge to Q0 in a finite number of steps.
The iterative procedure is called the fixed-increment error correction
procedure.
It goes as follows:
Qi = Q i- i + cD

Qi = Q i- 1 - cD

if

M(Qi_1, D ) - T < 0

and

DeA

if
and

D ) —T > 0
DeA91

SEARCH STRATEGIES

and no change made to Qi_\ if it diagnoses correctly, c is the correction
increment, its value is arbitrary and is therefore usually set to unity. In
practice it may be necessary to cycle through the set of documents
several times before the correct set of weights are achieved, namely
those which will separate A and A linearly (this is always providing asolution exists).
The situation in actual retrieval is not as simple. We do not know thesets A and A in advance, in fact A is the set we hope to retrieve.
However, given a query formulation Q and the documents retrieved byit we can ask the user to tell the system which of the documents retrieved
were relevant and which were not. The system can then automaticallymodify Q so that at least it will be able to diagnose correctly those
documents that the user has seen. The assumption is that this will
improve retrieval on the next run by virtue of the fact that its
performance is better on a sample.
Once again this is not the whole story. It is often difficult to fix thethreshold T in advance so that instead documents are ranked indecreasing matching value on output. It is now more difficult to define
what is meant by an ideal query formulation. Rocchio9 in his thesis
defined the optimal query Q0 as one which maximised:
* =ni

£

DeA

ll L _ m , D )M( Q .O ) - iIA
IDeA

If M is taken to be the cosine function (Q, D)I\\Q\\ ||Z)|| then it is easy
to show that <f> is maximised by' 1 y D,1
- 41DeA W
OW
where c is an arbitrary proportionality constant.
If the summations instead of being over A and A are now made overA n Bi and A n Bt where Bt is the set of retrieved documents on thezth iteration, then we have a query formulation which is optimal for 5,
a subset of the document collection. By analogy to the linear classifier
used before we now add this vector to the query formulation on the zth
step to get:
Q i+1 = W i Q i + w 2

1D
1-4 n Bi\ D e A DB ; ll-^ll

I

D_
1-4

linn

where uq and vv2 are weighting coefficients. Salton2 in fact used aslightly modified version. The most important difference being that
there is an option to generate Qi+1 from Qu or Q, the original query.
92

SEARCH STRATEGIESThe effect of all these adjustments may be summarised by saying thatthe query is automatically modified so that index terms in relevant
retrieved documents are given more weight (promoted) and index terms
in non-relevant documents are given less weight (demoted).
Experiments have shown that relevance feedback can be very
effective. Unfortunately the extent of the effectiveness is rather
difficult to gauge, since it is rather difficult to separate the contribution
to increased retrieval effectiveness produced when individual
documents move up in rank from the contribution produced when new
documents are retrieved. The latter of course is what the user mostcares about.
Finally a few comments about the technique of relevance feedback
in general. It appears to me that its implementation on an operational
basis may be more problematic. It is not clear how users are to assess
the relevance, or non-relevance of a document from such scanty
evidence as citations. In an operational system it is easy to arrange for
abstracts to be output but it is likely that a user will need to browse
through the retrieved documents themselves to determine theirrelevance after which he is probably in a much better position to restate
his query himself.

Bibliographic remarks

Discussions on search strategies are usually found embedded in moregeneral papers on information retrieval. There are, however, a few
specialist references worth mentioning.
A now classic paper on the limitations of a Boolean search is
Verhoeff et al. 10 Miller11 has tried to get away from a simple Boolean
search by introducing a form of weighting although maintaining
essentially a Boolean search. Rickman12 has described a way of
introducing automatic feedback into a Boolean search. Goffman13 hasinvestigated an interesting search strategy based on the idea that therelevance of a document to a query is conditional on the relevance ofother documents to that query. In an early paper by Hyvarinen14 one
will find an information-theoretic definition of the ‘typical member’cluster representative. Negoita15 gives a theoretical discussion of abottom-up search strategy in the context of cluster-based retrieval.
Much of the early work on relevance feedback done on the SMART
project has now been reprinted in Salton16. Two other independentpieces of work on feedback are Stanfel17 and Bono18.
93

SEARCH STRATEGIES

References
1. KNUTH, D. E., T h e A r t o f C o m p u te r P ro g ra m m in g , Vol. 3, S o r tin g andS earching, Addison-Wesley, Reading, Massachusetts (1973)
2. SALTON, G., A u t o m a t ic I n fo r m a tio n O rg a n iz a tio n a n d R e trie v a l,
McGraw-Hill, New York (1968)
3. VAN RIJSBERGEN, C. I., ‘The best-match problem in document retrieval’,
C o m m u n ic a tio n s o f th e A C M , 17, 648-649 (1974)
4. VAN RIJSBERGEN, C. J., ‘Further experiments with hierarchic clustering in
document retrieval I n fo r m a tio n S to ra g e a n d R e trie v a l, 10, 1-14 (1974)
5. MURRAY, D. M., ‘Document retrieval based on clustered files’, Ph.D. Thesis,
Cornell University Report ISR-20 to National Science Foundation and to the
National Library of Medicine (1972)
6. Medline Reference Manual, Medlars Management Section, Bibliographic
Services Division, National Library of Medicine
7. BARRACLOUGH, E. D., MEDLARS on-line search formulation andindexing, T e c h n ic a l R e p o r t Series, No. 34, Computing Laboratory, Universityof Newcastle upon Tyne
8. NILSSON, N. J., L e a rn in g M a ch in e s - F o u n d a tio n s o f T ra in ab le P a tte rn
C lassifying System s, McGraw-Hill, New York (1965)
9. ROCCHIO, J. J., ‘Document retrieval systems - Optimization andevaluation’, Ph.D. Thesis, Harvard University, Report ISR-10 to National
Science Foundation, Harvard Computation Laboratory (1966)
10. VERHOEFF, J., GOFFMAN, W. and BELZER, J., ‘Inefficiency of the use ofboolean functions for information retrieval systems \ C o m m u n ic a tio n s o f th e
A C M , 4, 557-558, 594 (1961)
11. MILLER, W. L., ‘A probabilistic search strategy for MEDLARS’, J o u rn a l o f
D o c u m e n ta tio n , 27, 254-266 (1971)
12. RICKMAN, J. T., ‘Design consideration for a Boolean search system with
automatic relevance feedback processing’, P ro c e e d in g s o f th e A C M 1972
A n n u a l C o n fe re n ce , 478-481 (1972)
13. GOFFMAN, W., ‘An indirect method of information retrieval’, In fo r m a tio n
S to ra g e a n d R e trie v a l, 4, 361-373 (1969)
14. HYVARINEN, L., ‘Classification of qualitative data’, B IT , N o r d is k T id s k rift
f o r In fo rm a tio n s b e h a n d lin g , 2, 83-89 (1962)
15. NEGOITA, C. V., ‘On the decision process in information retrieval’, S tu d ii si
c e rc e ta ri de d o c u m e n ta re , 15, 269-281 (1973)
16. SALTON, G., T h e S M A R T R e trie v a l S y s te m - E x p e r im e n t in A u t o m a t ic
D o c u m e n t Processing, Prentice-Hall, Englewood Cliffs, New Jersey (1971)
17. STANFEL, L. E., ‘Sequential adaptation of retrieval systems based on user
inputs’, In f o r m a t io n S to ra g e a n d R e trie v a l, 7, 69-78 (1971)
18. BONO, P. R., ‘Adaptive procedures for automatic document retrieval’, Ph.D.
Thesis, University of Michigan (1972)94