Chapter 6iiRetrieval Refinements

0

PREVIEW

A number of advanced analysis and search techniques have been mentioned insome of the previous Chapters, including in particular the use of term weighting
methods for indexing and query formulation, the introduction of clustered filearrangements, the dynamic improvement of query formulations using rele­vance feedback techniques, and the use of bibliographic citations for content
identification and retrieval purposes. In the present chapter, these techniques
are examined in more detail, and methods are given for implementing the vari­
ous techniques in retrieval. W herever possible evaluation results are included
showing the usefulness of the various methodologies in retrieval.
Some of the procedures examined in this chapter should prove immedi­
ately useful in conventional and experimental retrieval situations. This is thecase notably of some term weighting systems that are easy to generate and ex­
ceptionally effective, and of the automatic query adjustment systems based onuser-system interaction during the course of the search process. Certain othertechniques, such as the dynamic document space modification and the autoT
matic thesaurus construction process using pseudoclassification, may prove
important in the long run. All the retrieval refinements described in this chapter
are conceptually simple and some of them have already been applied in infor­
mation retrieval under operational conditions.
199

200

CHAPTER 6

1 INTRODUCTION

Conventional retrieval operations use Boolean search requests and inverted filesystems. A search then produces two distinct document sets: those retrieved inanswer to a given query and those not retrieved. Relationships or similarities
between individual documents are not utilized and neither are relationships be­
tween keywords or query terms. The experimental retrieval systems describedin Chapter 4 are more advanced largely because some structure is imposed on
the retrieval environment. Thus, by recognizing relationships among the docu­
ments of a collection, items which appear to be related can be grouped into af­
finity classes, to permit browsing and to simplify searches dealing with particu­
lar subject areas. By making distinctions among the terms assigned to the
documents, some documents— normally those identified by highly weighted
terms— can be retrieved ahead of certain others identified by terms of lesser
importance. By using the occurrence characteristics of the terms assigned to acollection, it is possible to identify very broad terms assigned to a large propor­
tion of the documents as well as narrow terms assigned to few documents. The
former can be rendered less general by combining them into term phrases, andthe latter can be broadened by grouping them into thesaurus classes of wider
scope.
The foregoing processes produce a greater measure of discrimination
among the documents of a collection and among the terms characterizing docu­
ment content than is customary in conventional retrieval situations. When the
documents are clearly distinguished from each other, maximum recall and pre­cision may be obtained for a search, because each particular relevant item maythen be retrievable without also retrieving neighboring items that may not be
relevant. Furthermore, documents that are. distinguished from each other canbe ranked for output purposes in decreasing order of the similarity between
query and documents. This brings the most important items to the users’ atten­
tion early in a search when they are most easily used for the generation of im­proved search formulations in an interactive search mode.
The discrimination operations all depend on the assignment of importancefactors, or weights, to the content identifiers used for a document collection,and on the computation of similarity measures between documents, between
terms, or between queries and documents. In this chapter, the properties ofvector similarity functions are first outlined and some of the applications ofterm weighting and vector similarity computations previously mentioned forthe experimental systems of Chapter 4 are covered in greater detail. This in­cludes the generation of optimum term weights, the construction of document
clusters, and the generation of improved query formulations and better docu­
ment identifications. Normally, the affinities between document vectors aremeasured by comparing the terms attached to the respective items. In somecircumstances, the terms may be replaced by bibliographic citations. In partic­
ular, the structure of a document collection might be determined by the cita­
tions and bibliographic references relating the items. This possibility is further
examined at the end of this chapter.

RETRIEVAL REFINEMENTS

201*2 VECTOR SIMILARITY FUNCTIONSConsider a collection of objects in which each object is characterized by one ormore properties associated with the objects. In information retrieval, the ob­
jects might be documents and the properties could be the index terms assigned
to the documents. Alternatively, the objects could be index terms, and theproperties could be the document identifiers to which the terms are assigned.
Each property attached to a given object could be weighted to reflect its impor­tance in the representation of the given object. Alternatively, a property
characterizing an item may be considered to carry a weight of 1 when it is ac­
tually assigned to an item, or a weight of 0 when the property is not assigned. In
the former case one speaks of weighted indexing; in the latter case the indexing
is binary.
The similarity between two objects is normally computed as a function of
the number of properties that are assigned to both objects; in addition the num­
ber of properties that are jointly absent from both objects may be taken into
account. Furthermore, when weighted indexing is used, the weight of the prop­
erties appearing in the two vectors may be used instead of only the number ofproperties.
Consider as an example, two particular objects, say DOC, and DOC,, andlet TERM ik represent the weight of property (term) k assigned to document i. In
binary systems the value of TERM lk is restricted to either 0 or 1. Otherwise, one
may assume that the weights vary from some low er limit such as 0 to some pre­determined maximum weight for a given collection environment. If t properties
are used to characterize the objects, the following property vectors may be de­fined for two sample objects:
D O Q = (TERM,,, TERM i2, . . . , TERM,,)
DOC, = (TERM ,,, TERMj2, . . . , TERM,,)
To compute the similarity between two given vectors, the following vector
functions are of principal importance:
1t^ TERM,k, that is, the sum of the weights of all properties included in
k=la given vector (in this case, the vector for DOC,).
t2 ^ TERM,k • TERMjk, that is, the component-by-component vector
k=lproduct, consisting of the sum of the products of corresponding term weights
for two vectors. For binary vectors this reduces to the number of matchingproperties for two vectors (the number of properties with weight equal to 1 in
the two vectors).
t
3 ^ min (TERM,k, TERM,k), that is, the sum of the minimum component
k -1

weights of the components of the two vectors.

202

CHAPTER 6

4

V S (TERMik)2, that is, the length of the property vector (in this case,’ k=lthe one for DOQ) when the property vectors are consider as ordinary vectors.
Consider the following two vectors defined for a system using eight properties:
DOC, = (3,2,1,0,0,0,1,1)
D O Q = (1,1,1,0,0,1,0,0)
The four vector functions introduced earlier are then equal, respectively, to
1^

TERM * = ( 3 + 2 + l + 0 + 0 + 0 + l + l) = 8

k=l

2

2

TERMik • TERM * = [(3 • 1) + (2 • 1) + (1 • 1) + (0 • 0) + (0 • 0)

k=1
3

4

+ (0 • 1) + (1 • 0) + (1 • 0)] = 6^ min (TERM *,TERM *) = (min(3,l) + min(2,l) + m in(l,l)
k=1+ min(0,0) + min(0,0) + min(0,l)+ min(l,0) + min(l,0)= (1 + 1 + 1 + 0^ __________+ 0 + 0 + 0 +0) = 3

Vi (TERM *)2’

k=1= V(3 • 3) + (2 • 2) + (1 • 1) + (0 • 0) + (0 • 0) + (0 • 0) + (1 • 1) + (1 • 1)
= V9 + 4 + 1 + 0 + 0 + 0 + 1 + 1 = 4
The expressions under 2 and 3 are based on the manipulation of a particu­
lar vector pair; expressions 1 and 4 are single vector functions only. Hence theordinary vector product (expression 2) and the sum of the minimum compo­
nents (expression 3) could be used directly to measure the similarity between
the vectors. In practice, it is customary to include normalizing factors when
computing vector similarities. These factors ensure that the similarity coeffi­
cients remain within certain bounds, say between 0 and 1 or between - 1 and+ 1. The following similarity measures are all relatively easy to generate andhave been used in operational or experimental situations to compute term or
document similarities [1,2]:
2
SIM ^D O Q ,DOQ)(TERM* • TERM *)

L k=l

(i)

2 TERM* + £ TERM *
k=l

k=l

RETRIEVAL REFINEMENTS

203t

I CTERMik • TERMjk)
2 TERM * + 21 TERM* - 2s (TERM* • TERM *)2t

SIMjCDOC^DOCj)

t

k=i
t

t

k=l

k=l

2

k=l

( )

X (TERMik * TERMjk)
k = l _____________________________________

SIM3(DOCi ,DOCj) =(3)

X (TERMik)2 • X (TERMjk)2
k=l

k=l

X (TERMik • TERMjk)
k -l

SIl^CDOC^DOCj) =■(4)

m i n ( x TERMik, X TERM
vk = lk=l

X min(TERMik ,TERMjk)
SIM sOJOCl DOGj)

k=l

(5)

t

2 TERMi>k=l

For the two sample vectors previously used as an illustration, the simi­
larity functions SEV^ to SIM5 produce the following results:

SIM1(DOC1,DOC1) = | - ^ =1

SIM2(DOQ ,DOQ) = 8 + ^ _ 6 = 1
SIM3(DOC1,DOCj) = - j L ==^= | = 0.75

SIM4(DOCj ,DOCj) = | = 1.5
SIM5(DOCi ,DOCj) = | = 0.375
The first two coefficients, SIMj and SIM2, are known respectively as theDice and Jaccard coefficients. They are widely used in the literature to mea­
sure vector similarities. The third coefficient, SIM3, is the cosine coefficientthat was introduced earlier in this volume. The cosine is a measure of the angle
between two t-dimensional object vectors when the vectors are considered asordinary vectors in a space of t dimensions. Since the numerator in the cosine
expression must be divided by the product of the lengths of the two vectors,
long vectors with many terms and hence great length normally produce small
cosine similarities. The overlap measure, SIM4, does not have this property be­cause its denominator consists of the lower-weighted terms from the two vec-

204

CHAPTER 6

tors. In a retrieval environment, the query usually contains low-weighted
terms; hence the query-document correlations using the overlap measure SIM4
will be larger in magnitude than those of the cosine SIM3.
The last coefficient, SIM5, is an asymmetric measure; that is the similarity
between DOQ and DOQ is not in general equal to the similarity between DOC,
and DOQ. Indeed SIM5(DOQ,DOQ) = >/s whereas SIM5(DOQ,DOQ) =3/4. Asymmetric measures are useful to capture the inclusion relations between
vectors (vector B is included in vector A if all properties assigned to B are alsopresent in A). The inclusion properties between vectors can be used for thegeneration of hierarchical arrangements of objects (for example, hierarchicalterm displays) and for the comparison of queries with documents in retrieval[1].
A great many different similarity measures are discussed in the literaturedesigned to represent the associations between different property vectors.
Some of the functions reflect statistical theories, being designed to measure theagreement between two vectors over and above the coincidences that would be
expected if the properties were randomly assigned to the vectors [3,4]. In somesimilarity functions the absence of properties from a vector may be taken into
account as well as the presence. For instance the joint absence of a property in
two vectors may be weighted differently from the joint presence of a property[5].
All similarity measures exhibit one common property, namely that theirvalue increases when the number of common properties (or the weight of thecommon properties) in two vectors increases. Measures of vector dissimilarity
which are sometimes used instead of similarity measures have the opposite ef­
fect. Various evaluation studies exist in which the effect of different similarity
measures has been compared in a retrieval environment [1]. The Jaccard [ex­pression (2)] and the cosine measures [expression (3)] have similar characteris­
tics, ranging from a minimum of 0 to a maximum of 1 for nonnegative vector
elements. These measures are easy to compute and they appear to be as effec­
tive in retrieval as other more complicated functions. Both these measures
have been widely used for the evaluation of retrieval functions.
3

TERM WEIGHTING SYSTEMS

A

Principal Weighting Strategies

In principle, the retrieval environment is simplest when the information items
are characterized by unweighted properties and the indexing operation is bi­nary. In this case, the degree to which a given property (term) may be useful torepresent the content of an item is not a consideration. Any property that ap­
pears relevant is assigned to the information item and rejected when it appears
extraneous. While the indexing is simplified, the task of evaluating the output
of a search operation may be complicated because distinctions among the re­trieved items, or for that matter among the items that are not retrieved, aremore difficult to make for binary than for weighted vectors. When weighted

RETRIEVAL REFINEMENTS

205

properties are used, a similarity computation between the query and document
vectors makes it possible to retrieve the items in strictly ranked order accord­
ing to the magnitude of the query-document similarity coefficients. This should
improve the retrieval effectiveness and lighten the user effort required to gen­erate a useful query.
When users, indexers, or search intermediaries manually assign term
weights to document and query vectors, the weighting operation is difficult tocontrol. A satisfactory assignment of weights requires a great deal of know­
how about the collection and the operation of the retrieval system. For this rea­son, an effective term weighting operation is probably best conducted by using
objective term characteristics automatically to generate term weights.
Several automatic term weighting systems were introduced in Chapter 3 inthe discussion on automatic indexing. They are summarized here for conve­
nience:1
The term frequency (TF) weighting system is based on the notion that
constructs (words, phrases, word groups) that frequently occur in the text of
documents have some bearing on the content of the texts. Hence the weight ofterm k in document i, W EIGHTik might be set equal to the frequency of occur­
rence of word construct k in document i:
W EIGHTik = FREQik(6)

2
The term frequency system makes no distinction between terms that
occur in every document of a collection and those that occur in only a few
items. Experience indicates that the usefulness of a term for content represen­tation increases with the frequency of the term in the document but decreases
with the number of documents DOCFREQk to which the term is assigned. This
produces the inverse document frequency (IDF) weighting system:
WEIGHTik

FREQlkDOCFREQkay

3
The term discrimination theory depends on the degree to which the as­signment of a term to the documents of a collection is capable of decreasing thedensity of the document space (the average distance between documents). The
discrimination value of term k, DISCVALUEk is obtained as the difference be­
tween two measurements of document space density, corresponding to thedensities before and after assignment of term k. A typical weighting function
for term k in document i is then obtained as

WEIGHTik = FREQik • DISCVALUEk(8)

4
The probabilistic indexing theory states that the best index terms arethose that tend to occur in the relevant documents with respect to some query.
When the terms are assigned to the documents independently of each other, ameasure of term value is obtained from the term relevance TERM RELk. This

206

CHAPTER 6

is the ratio of the proportion of relevant items in which term k occurs to the
proportion of nonrelevant items in which the term occurs [expression (23) ofChapter 3]. A weighting system based on the term relevance is thus
W EIGHT* = FREQ* • TERM RELk

(9)

The term frequency, document frequency, and term discrimination
theories were previously examined in the discussion dealing with automatic in­dexing. The term relevance weighting system is theoretically optimal given cer­tain well-specified conditions. However the term relevance factor
TERM RELk = ^~ ^sk/(I - sk)cannot be computed unless relevance assessments are available of the docu­
ments with respect to certain queries. In particular, the number of relevant doc­
uments (rk) containing term k, the number of nonrelevant documents (sk) con­taining term k, as well as the total number of relevant documents (R) andnonrelevant documents (I) in the collection for some particular query sets must
be known in advance.
A similar situation arises for a weighting function based on the utility value
introduced in the discussion on system evaluation [expression (19) of Chapter
5]. The utility of a search is defined simply as the sum of the values achieved byretrieving relevant items and rejecting nonrelevant ones plus the sum of thecosts incurred by retrieving nonrelevant and rejecting relevant items. One may
assume that each relevant item that is correctly retrieved increases the useful­ness of retrieval by a specified value equal to Vj; similarly each nonrelevant
item that is properly rejected increases the system usefulness by a constantvalue of v2. Analogously, a constant cost of c xis incurred for each nonrelevant
item that is retrieved, and a cost of c2 arises for each relevant item missed by
the retrieval system. In these circumstances, appropriate transformations of
the utility value introduced in Chapter 5 produce a weighting function, known
as the utility weight for a given term k, or UTILITYk, defined as
U TILITY , = (Vl + c2)rk - (v2 + Cl)sk(10)

where rk and sk, respectively represent the number of relevant and nonrelevant
items containing term k [6]. A corresponding term weighting function for term k
in document i is then given by
W EIGHT* = FREQ* • UTILITY ,(11)

The utility and term relevance weighting systems of expressions (9) and(11) may be expected to be more powerful than the alternative weighting
schemes based on simple term frequency characteristics [expressions (6) andRETRIEVAL REFINEMENTS

207(7)]. In the utility and term relevance systems, a distinction is made between
term occurrences in the relevant and nonrelevant documents, respectively,
whereas in the frequency-based systems the term occurrences are used globallyover the whole collection irrespective of occurrences in the relevant and non­relevant documents. On the other hand, it remains to be seen whether for the
relevance-based weighting systems the term weights computed by using rele­vance data for certain queries and documents will prove robust enough to be
applied to new documents and queries for which no prior relevance data are
available. Procedures for so doing are suggested in the next section.
*B

Evaluation of Weighting Systems

Two collections of documents may serve as examples for the evaluation of theweighting systems introduced earlier. These are the Cranfield collection of 424
documents in aerodynamics, and the MEDLARS collection of 450 documents
in biomedicine. Each collection is used with 24 search requests. Table 6-1 con­tains evaluation output for term frequency weightings (6), inverse document
Table 6-1 Term Utility Weight and Relevance Weight Evaluation(Average Precision Values for Fixed Levels of Recall from 0.1 to 1.0)

RecallTermfrequency
a

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

Utility weightw = 20r - s(actual values)

Relevance weights
w = [r/(R - r)] + [s/(l - s)](actual values)

Cranfield aerodynamics collection (424 documents, 24 queries)

0.455
0.410
0.391
0.301
0.280
0.233
0.189
0.155
0.121
0.112

b

Inversedocument
frequency

0.566
0.530
0.476
0.421
0.364
0.301
0.254
0.195
0.150
0.132

+24%
+29%
+22%
+40%
+30%
+29%
+34%
+26%
+24%
+ 18%
+27.6%

0.568
0.540
0.503
0.474
0.416
0.328
0.272
0.211
0.162
0.143

+25%
+32%
+29%
+57%
+49%
+41%
+44%
+36%
+34%
+29%
+37.6%

0.571
0.558
0.479
0.479
0.434
0.352
0.324
0.220
0.199
0.164

+25%
+36%
+23%
+59%
+55%
+51%
+71%
+42%
+ 64%
+46%
+47.2%MEDLARS biomedical collection (450 documents, 24 queries)

0.543
0.528
0.467
0.421
0.384
0.346
0.316
0.211
0.171
0.120

0.611
0.601
0.541
0.467
0.438
0.396
0.347
0.245
0.193
0.154

+ 13%
+ 14%
+ 16%
+ 11%
+ 14%
+ 14%
+ 10%
+ 16%
+ 13%
+28%
+ 14.9%

0.676
0.676
0.639
0.609
0.558
0.510
0.459
0.374
0.277
0.204

+24%
+28%
+37%
+45%
+45%
+47%
+45%
+77%
+ 62%
+70%
+48%

0.707
0.707
0.705
0.672
0.633
0.616
0.573
0.462
0.354
0.259

+30%
+34%
+51%
+60%
+65%
+78%
+81%
+ 119%+ 107%+ 116%+74.1%

208

CHAPTER 6

frequency weights (7), utility weights (11), and term relevance weights (9). In
each case precision values are shown in Table 6-1 for 10 recall levels varying
from 0.1 to 1.0. These are averaged for the 24 search requests. The inverse doc­
ument frequency weights that are based on frequency characteristics over all
documents regardless of relevance produce average precision improvements ofabout 28 percent for the aerodynamics collections and 15 percent for the bio­
medical collection over the standard term frequency weights. When the utility
weights based on document relevance are used the average advantage in pre­cision increases to 38 and 48 percent, respectively, while an even greater ad­
vantage of 46 and 74 percent is obtained for the term relevance weights.
To generate the term relevance and term utility weights TERMRELk and
UTILITYk, respectively, it is necessary to identify the number of relevant andnonrelevant documents rk and sk in which the term occurs. Furthermore, for
the utility weights, values must be chosen for the value and cost parameters ofequation (10). The output of Table 6-1 is based on the assumption that the costand value parameters associated with the relevant documents (vt and c2) are
given a weight equal to 20 times the value and cost parameters associated with
the nonrelevant (v2 and C j) . The utility function of expression (10) is thus com­puted as 20rk - sk.
The problem of generating the rk and sk values was bypassed in the experi­ments of Table 6-1 by using the actual values found in the two sample collec­
tions for these parameters. That is, the unrealistic assumption was made thatthe characteristics of all terms in the relevant and nonrelevant documents were
known in advance for all queries. This, of course, accounts for the excellent
performance of the term utility and term relevance weighting systems in the
output of Table 6-1.
In practice, the occurrence characteristics of the terms in the relevant andnonrelevant documents are not available before a search is actually conducted.
However, the total number of documents DOCFREQk to which a given term is
assigned is given, and that in turn can be used to estimate the number of rele­vant documents (rk) having term k. Note that the document frequency of a term
varies from 0 for a term not assigned to any document in the collection to a
maximum of N for a term assigned to all N items in a collection. The parameterrk, on the other hand, varies from 0 for a term not assigned to any relevant
items to a maximum of R, the total number of relevant items which exists withrespect to a given query. Alternatively R can be interpreted in some circum­
stances as the number of documents which a user wishes to retrieve in response
to a given query.
Normally, the following relationships exist between the total document
frequency DOCFREQk of a term, and the frequency rk in the relevant docu­
ments:
1 As DOCFREQk increases, so will rk; thus given two terms TERMj andTERMk, DOCFREQj > DOCFREQk generally implies rj > rk.
2 For normal query terms, the number of relevant documents in which a

RETRIEVAL REFINEMENTS

209

term occurs is relatively larger for lower-frequency terms than for higher-fre­quency terms; mathematically, one can say that when DOCFREQ, > DOCFREQk, one finds that rk/DOCFREQk > r/DOCFREQ,. (For example, the one
document in which a frequency-one term occurs is more likely to be relevant
than the two documents for a term of frequency two.)
Several simple functions can be suggested that conform to these condi­
tions. One possible functional relationship between rk and DOCFREQk for agiven term k is shown in the graph of Fig. 6-1. Here for document frequencies
between 0 and R, one assumes that a straight-line relation exists between DOCFREQ and r given as r = (a • DOCFREQ) for some constant a < 1, and repre­
sented by line segment 0A. For frequencies DOCFREQ between R and N, an­other straight-line relation is assumed expressed as r = d + (e • DOCFREQ)
and represented by segment A B. It may be noted that in accordance with as­
sumption 2, the slope of line AB (represented by parameter e) is smaller
than the slope of line 0A (parameter a). As a result the proportion rk/DOCFREQk is relatively larger for terms of smaller frequency DOCFREQk than forterms of larger frequency. An alternative functional relationship between r and
DOCFREQ which also obeys assumptions 1 and 2 is r = a + b(log DOC­
FREQ). It can be shown that if the relationship between DOCFREQk and rk is
the one represented in Fig. 6-1, the best term weighting function has the shape
represented in Fig. 6-2 [7].
In particular, the optimum weight of a term starts with some constantvalue a for terms of frequency 1. The weight then increases as the document
frequency increases to R, the number of relevant documents which a user
wishes to retrieve in response to a query. As the document frequency increases
still further, the terms become less important and the term weight decreases.
Eventually, for terms of document frequency near the number of documents inthe data base (N), the weight decays to 0. The frequency spectrum of Fig. 6-2

Total number of documents(DOCFREQk) containing term k

Figure 6-1 Variation of number of relevant documents containing term k with total numberof documents containing term k.

CHAPTER 6

210

Figure 6-2

Optimum term weighting system assuming relationships of Fig. 6-1.

once again shows that the medium-frequency terms in a collection are the mostimportant for purposes of document indexing.
Consider now the evaluation results obtained for the utility and term rele­vance weighting schemes where the parameter values for rk and sk are no longer
assumed to be available, but rk (and hence sk = DOCFREQk - rk) is obtainedby using one of the functional relationships between DOCFREQ and r (forexample the one presented earlier in Fig. 6-1). Evaluation results for theterm utility and term relevance weighting systems based on estimated rk
values are included in Table 6-2 for the two document collections previously
used in Table 6-1. For the utility weights a logarithmic relationship was
assumed between r and DOCFREQ [that is, r = a + b log (DOCFREQ)
for suitably chosen parameter values a and b]. A hybrid function modeled
Table 6-2

Estimated Term Utility and Relevance Weight Evaluation(A ve ra g e P re c is io n V a lu e s fo r 24 Q u e rie s a t R e ca ll L e ve ls fr o m 0.1 to 1.0)

MEDLARS biomedical(450 documents, 24 queries)

Cranfield aerodynamics(424 documents, 24 queries)
Utility weight(estimated values)
0.531
0.501
0.450
0.388
0.332
0.288
0.234
0.184
0.138
0.128

+ 17%
+22%
+ 15%
+29%
+ 19%
+24%
+24%
+ 19%
+ 14%
+ 14%
+ 19.7%

Rejevance weight(estimated values)

Utility weight(estimated values)

Relevance weight(estimated values)

0.552
0.520
0.461
0.421
0.369
0.303
0.259
0.192
0.159
0.131

0.592
0.579
0.511
0.440
0.396
0.333
0.309
0.233
0.186
0.139

0.629
0.629
0.601
0.536
0.512
0.456
0.409
0.296
0.218
0.169

+21%
+27%
+ 18%
+40%
+32%
+30%
+37%
+24%
+31%
+ 17%
+ 27.7%+9% + 10%
+ 9%
+ 5%
+3%
-4 %
-2 %
+ 10%
+9%
+ 16%
+6.5%

+ 16%
+ 19%
+29%
+27%
+33%
+32%
+29%
+40%
+27%
+41%
+29.3%

RETRIEVAL REFINEMENTS

211

on the relationship of Fig. 6-1 is used to relate r and DOCFREQ for the rele­vance weight calculation: in particular, a straight line similar to line segment OAof Fig. 6-1 (r = a • DOCFREQ) is used for document frequency values up
to DOCFREQ = 8; for larger values of DOCFREQ a logarithmic relation­
ship (r = d + e log DOCFREQ) is assumed between r and DOCFREQ.
A comparison between the output of Tables 6-1 and 6-2 indicates that theutility and relevance weighting systems are not as powerful when the parametervalues must be estimated than when actual values are available. However the
relevance weighting system appears to be more effective than the inverse docu­
ment frequency even when the relevance parameters are estimated. Since theestimated relevance weights are based purely on the occurrence frequencies of
the terms in the documents of a collection, the results of Table 6-2 confirm that
substantially more information may be contained in the term frequency data
than is normally included in conventional retrieval. Additional work is needed
to produce good estimates of term relevance and justification for the curves ofFigs. 6-1 and 6-2.
**C

Term Weighting in Boolean Query Systems

It was mentioned earlier that systems based on Boolean query formulations arecapable of separating a document collection into two parts consisting of the re­trieved items on one hand and the rejected (nonretrieved) ones on the other.
Additional operations are sometimes carried out for the set of retrieved docu­
ments only in order to generate additional discrimination or ranking among
these documents. No term weights need to be introduced for this purpose andno changes arise in the interpretation of the normal Boolean operations. The
question arises whether the necessary discrimination among documents can beobtained directly by reinterpreting the standard Boolean operations to renderthem applicable to systems using weighted query terms, and possibly weighted
documents.
It is not possible in the present context to examine in detail the questions
relating to the processing of weighted Boolean queries [8,9]. It may be suffi­
cient instead to suggest some obvious approaches that lend themselves to apractical implementation. Consider two arbitrary index terms A and B, and let
A and B represent the set of documents indexed by terms A and B, respectively.
The Boolean operations normally receive the following interpretation:
1 The query “A OR B ” is designed to retrieve the document set (A U B)
consisting of documents indexed by term A or by term B or by both A and B.
2 The query “A AND B ” retrieves document set (A fl B) consisting of
documents indexed by both terms A and B.
3 The query “A NOT B” retrieves document set (A - B) consisting of
documents indexed by term A that are not also indexed by B.
Let a and b denote term weights varying from a minimum of 0 to a maxi­
mum of 1, and consider an extension of those operations that includes the use

212

CHAPTER 6

of weighted query terms. When the term weight is chosen equal to 1, the nor­mal Boolean operation is implied, whereas a term weight of 0 implies that thecorresponding operand may be disregarded. Thus one has
Aj OR B'i = A OR B
A t AND Bi = A AND B
Aj NOT Bi = A NOT B
and At OR B„ = A
Ax AND B0 = A
A t NOT B0 = A
When both the document and the query terms are weighted, a weighted
Boolean query now receives a simple interpretation. In response to a query
such as Aa OR B„, the set of retrieved documents consists of those having ei­
ther term A with a weight at least equal to a or term B with a weight at least
equal to b. The retrieved items can be ranked according to the sum of theweights a + b in the documents.
When only the documents are weighted, but not the queries, the full docu­
ment sets A and/or B are retrieved using the appropriate Boolean combination,and the ranking applies as before. This situation appears simple to implement in
operational retrieval because weights can be assigned to the document terms by
the expert indexers, or frequency-based weights can be automatically obtainedby the system. To assign weights to the query terms, some input is needed fromthe users, and reliable term weighting information of this kind may be difficult
to obtain.
In the unlikely situation where the query terms alone are weighted but the
document terms are not, it appears reasonable to suggest that each weighted
query term affects a partial set of documents instead of the full set. Consider as
an example, query statements of the form ( . . . ((Aa * Bb) * Cc). . . . * Zz),
where * stands for one of the operators AND, OR, NOT, and where a,b,j. . . , z represent weights attached to terms A, B, . . . , Z respectively,
such that 0 < a s 1, . . . , 0 ^ z < 1. The general case involving a multiplicity
of binary * operators may be reduced to that of a single binary operator with
two operands by assuming that the search process is carried out iteratively, one
operator at a time. The problem then consists of interpreting query statementsof the form (Aa * B), where * is a binary connective and a and b are the term
weights.
The operations of the three Boolean connectives may be described by con­sidering the special case where only one of the two operands carries a weightsmaller than 1, that is, where the queries have the form (Aj * Bb). Extensions to
the general case where both query terms carry weights less than unity will thenbe immediate. Remembering that query term B0 can be disregarded, whereas
B, covers the full set B of documents indexed by B, it becomes clear that query
A OR Bb expands the output document set from A to A U B as the weight of b

RETRIEVAL REFINEMENTS

213

increases from 0 to 1. A U B comprises the full set of items that are either A’s or
B ’s. A query such as (A OR B0 33) must then retrieve all the A’s plus a third of the
B’s. Correspondingly, (A AND Bb) shrinks the size of the output from A to
A fl B, that is, to the set of items that are both A’s and B’s as b increases from 0
to 1. This suggests that (A AND B0 33) covers all the A’s that are also in B plus
about two-thirds of the A’s that are not in B. Finally, (A NOT Bb) shrinks theoutput from A to A - B, that is, to the items in A that are not also in B. The
query (A NOT B„.33) would then cover all A’s that are not in B plus two-thirdsof the items in the intersection between A and B.
It remains to determine how the partial set of items that are either included
in or excluded from the answering document set is to be identified. The follow­
ing mode of operation suggests itself:
1 OR operation: as b increases from 0 to 1, the items in B not already in A
that are closest to the set A are successively added to A to generate A U B in
answer to query (A OR B).
2 AND operation: as b increases from 0 to 1, the items in A - B that are
farthest from A fl B are successively subtracted from A until only A fl B re­mains in answer to query (A AND B) when b is equal to 1.
3 NOT operation: as b increases from 0 to 1, the items in A fl B that are
farthest from A — B are successively subtracted from A until only A - B re­mains in answer to query (A NOT B).
To determine the closeness of a particular document to another document
or to a set of documents, the similarity coefficients previously introduced tocompare queries and documents [expressions (1) to (5)] can be used to obtainaffinity indicators between pairs of documents or between a particular docu­
ment and a set of documents. In the latter case, a typical document C is chosen
to represent the given set, such as, for example, the centroid of the documentset, and for each document DOCi, the size of the coefficient SIM(C,DOCj) isused to indicate whether DOCt is to be retrieved or not. The computation of acluster centroid is described in detail in the next section of this chapter.
Consider, as a typical example, the operations for query (A033 OR B0.66)
illustrated in Fig. 6-3 together with other examples. The following steps may be
used:
1 Compute the centroids of sets A and B.
2 Remove from set A two-thirds of the documents consisting of those ex­hibiting the largest distance to the centroid of B.
3 Remove from set B one-third of the documents consisting of those ex­hibiting the largest distance to the centroid of A.
4 The response set is then the union of the remaining items from A and B
Correspondingly, the output set for query (A0.33 AND B0 66) (see Fig. 6-3b)
is obtained by removing from set A one-third of the items not included in theintersection of A and B and situated farthest from the centroid of B ; at the same

214

CHAPTER 6
A

B

A

B

(b)

A

B

Figure 6-3 Interpretation of weighted
Boolean operations, (a) (A0.33OR B0.66). (b)( A 0 .3 3 AND Bnfi6) (c) (A0.33 NOT B0>50).

time, one removes from B two-thirds of the items that are most removed fromset A. For the query (A033 NOT B0 50) of Fig. 6-3c, two-thirds of the items in A
are removed from the answer set plus half of the items in the intersection be­
tween A and B.
To summarize, when weighted terms are used for queries that do not in­clude Boolean operators, a query-document similarity computation can be useddirectly to obtain a retrieval value, or ranking, for each document; documents
may then be retrieved in decreasing order of their retrieval values. When Bool­ean operators are included in the queries, a similarity computation is first car­ried out between certain documents and the centroids, or representatives, ofRETRIEVAL REFINEMENTS

215

certain document sets. The size of the corresponding similarity coefficientsthen determines which documents are to be added to (for the OR operation) or
subtracted from (for AND and NOT) the basic answering set. The use of term
weights in Boolean systems remains to be validated by appropriate retrieval ex­periments.

4

FILE CLUSTERING*A

Main Considerations

Most information retrieval work is based on the manipulation of large masses ofdata. The document files to be stored may be extensive, and the vocabularies
needed to represent document content may include tens of thousands of terms.
In these circumstances, it is useful to superimpose an organization on thestored information in order to simplify file access and manipulation. One way ofproviding order among a collection of stored records is to introduce a classifica­tion, or c l u s t e r i n g , among the items. Clustering is used to group similar or re­lated items into common classes. In a classified or clustered file, items appear­ing in a class can be stored in adjacent locations in the file so that a single fileaccess makes available a whole class of items. Such an approach is used inmost conventional libraries where the library items are placed on shelves ac­
cording to their subject content. By browsing among the shelves, the libraryusers can then retrieve a number of different items within a given subject area.
In information retrieval, classification methods are used for two main pur­poses:
1 To classify the set of i n d e x t e r m s , or keywords, into term classes ac­
cording to similarities in the keywords, or according to statistical characteris­tics of the terms in the documents of a collection
2 To classify the d o c u m e n t s into subject classes so that related items areaccessible to the user population
The k e y w o r d c l a s s i f i c a t i o n s lead to the construction of thesauruses and syn­onym dictionaries that can be used for document indexing and query formula­tion. These may also provide the associative indexing capability previously il­lustrated in Chapter 3. The d o c u m e n t c l a s s i f i c a t i o n s on the other hand may
serve as devices for the representation of knowledge, and in retrieval they may
provide efficient search strategies and effective search results. The efficiency is
produced by making it possible for the user to limit the search to specific sub­ject areas. The potential effectiveness of the cluster search process stems fromthe c l u s t e r h y p o t h e s i s , which asserts that closely associated documents tend to
be relevant to the same queries [2]. The use of clustered document files may
then lead both to high recall and to high precision searches [10].
The following two characteristics are generally considered important for
object classifications [11,12]:

216

CHAPTER 6

1 The classification should be stable in the sense that small alterations of
the data, because of either the addition of new items or changes in the old ones,
should cause only minor alterations in the classification.
2 The classification should also be well defined in that a given body ofdata should produce a single classification or at least one of a small set of com­
patible classifications.
As it will be seen, the second property is not always present in various heuristic
or single-pass classification systems constructed for actual objects. Rather, ex­amples exist where a variety of different classification systems all perform
equally well in practical applications. Stability, on the other hand, appears tobe essential if a classification is to operate satisfactorily.
Many different methods can be used to cluster a collection of items. If theclassification is to perform a useful ro}e, controls must normally be introduced
to limit the minimum and maximum number of classes that are generated, as
well as the size of the classes and the overlap between classes. Obviously, thenumber of classes generated should be greater than 1 but smaller than the total
number of objects to be classified. It is helpful if the various classes exhibit aroughly comparable size. Further, storage efficiency considerations make itnecessary to limit the overlap between classes, defined as the number or pro­portion of items jointly assigned to two or more classes.
The number, size, and overlap of the classes may be controlled during
cluster generation by parameter settings. An example is given in Fig. 6-4 for six
items labeled Dx to D6. The input to the clustering process is assumed to be asimilarity matrix giving similarity measures between all pairs of items as shownin Fig. 6-4a. The clustering process then consists in fixing a threshold T in thesimilarity coefficients, and grouping all pairs of items whose similarity exceeds
the chosen threshold. The illustration of Fig. 6-4b shows that when T = 0.95,
no clustering action is possible, and the file consists of 6 unclustered items. As
the threshold is lowered to 0.8, three pairs of items can be grouped including(Dj ,D5), (D x,D6), and (D2,D6); pairs of related items are identified by lines join­
ing the respective items in the graph of Fig. 6-4c. As the threshold value is fur­ther reduced to 0.60 and 0.50 additional pairs of items can be joined as shown in
Fig. 6-4d and e.
For purposes of the example, one may assume that each cluster of items isdefined as a connected component in the sense that in a graph representationsuch as that of Fig. 6-4, a path formed by lines exists from any item to all otheritems in the cluster. In these circumstances, the illustration of Fig. 6-4 demon­
strates that the number of clusters formed decreases and the size of the clusters
increases as the similarity threshold is decreased. The number of clusters pro­
duced by the four thresholds of Fig. 6-4b to 6-4e is, respectively, 6, 3, 2, and 1.
In information retrieval the cluster processing operation consists in taking
an item— for example, a new incoming document or an incoming user query—and comparing it with an existing cluster to determine the affinity of the itemwith that cluster. This operation is easily carried out by defining for each clus-

217

RETRIEVAL REFINEMENTS

d3

d4

0.3

0.5

0.6

0.8

0.9

-

0.4

0.5

0.7

0.8

0.4

-

0.3

0.5

0.2

0.5

0.3

-

0.4

0.1

0.8

0.7

0.5

0.4

-

0.3

0.9

0.8

0.2

0.1

0.3

-

D,

d2

D,

-

d2

0.3

d3

0.5
0.6

d5

d5

°6

(a)

o
V
Q

o

o

O

d3

d5

d2

o
D6

<b)

0*

DJ

d3

D°

d5

"°6

.

(d)

Figure 6-4 Role of threshold in item similarity for cluster formation, (a) Initial item-item simi­
larity matrix, (b) Threshold T = 0.95. (c) Threshold T = 0.80. (d) Threshold T = 0.60. (e)Threshold T = 0.50.

ter a cluster representative or centroid to represent the class during the cluster
manipulations. Comparisons between individual items and the cluster are thenperformed by computing the item-centroid similarity.
In principle, the centroid of a cluster might be represented by any docu­
ment located in that cluster. In practice it may be preferable to construct a spe­cial centroid vector that is centrally located in the cluster. Typically, the cen­troid may be defined as the average of the documents in a cluster. That is, theweight of a centroid term is computed as the average of the weights for thatterm over all items in a cluster, or
CTERMk = — j

TERMlk(12)

i= lwhere CTERMk is the kth term in the centroid, TERMik is the kth term in theith document in the cluster, and the cluster contains m documents in all.
A computation such as the one specified by expression (12) produces a
centroid vector that is reasonably representative of the items in a cluster. The

218

CHAPTER 6

most heavily weighted terms in the individual documents will be heavily
weighted in the centroid. The sample centroid derivation shown in Table 6-3
demonstrates that the two terms 3 and 6 best represent the clustered items.
These two terms also receive the highest weight in the centroid. The example ofTable 6-3 also shows that the standard centroid computation leads to full cen­troid vectors with few zero terms even when the individual document vectors
are sparse (that is, consist mostly of 0 terms). To improve the storage efficiencyof the centroid vectors, it is customary to add a thresholding operation which
eliminates centroid terms of excessively low weight. The reduced centroid
shown in Table 6-3 is obtained by eliminating centroid terms with weights
smaller than 1.
F/
The centroid averaging process suggested in expression (12) may overem­
phasize the importance of some terms that receive excessively high weights. In
some systems the final centroid term weights are therefore determined by using
rank values rather than actual weights. For example, a weight of 1 can be as­signed to the term exhibiting the lowest reduced weight; the next lowest term isgiven a weight of 2, and so on up until all nonzero terms are accounted for. The
rank value process produces term weights of 1 and 2 for terms 6 and 3 of Table
6-3, respectively, replacing the original weights of 3 and 4.
Additional cluster centroid definitions may be used to produce binary cen­troid vectors with centroid weights restricted to 0 and 1 only. Alternatively, theterm weights may be normalized to lie between 0 and 1 by dividing each term
weight by the length of the centroid vector [1,2,13]

Many cluster generation systems, including the method described in Chap­
ter 4 in connection with the SMART system description, produce a hierarchicalcluster tree where large clusters are analyzed and broken down into a numberof smaller clusters, which are themselves broken down into still smaller clus­
ters, until finally the lowest level clusters are (figuratively) broken down into
individual documents. A typical hierarchical cluster arrangement is shown in
Fig. 6-5.
Table 6-3 Cluster Centroid Formation for
Three Documents
DOCUMENT, = (1 , 0 , 3, 0, 0 , 4, 0 , 0 , 0 , 0)
DOCUMENT;, = ( 0 , 0 , 2, 0, 0 , 3, 1 , 1 , 0 , 0)
DOCUMENT, = ( 0 , 1 , 7, 0, 1 , 2, 0 , 0 , 1 , 1 )Standard= (1/3, 1/3, 4, 0, V3, 3, 1/3, 1/3, 1/ 3, 1/ 3)
centroid
Reduced= (0 , 0, 4, 0, 0, 3, 0, 0, 0, 0)
centroidCentroid using= ( 0 , 0 , 2 , 0 , 0 , 1, 0 , 0 , 0 , 0 )rank values

219

RETRIEVAL REFINEMENTS

Top cluster!____ _
representative jf/ Top cluster\ representative

Next level cluster!
representative I

Cluster
representative

Figure 6-5

N

Next level cluster!
representative I

I
Clusterl representative

Hierarchical cluster arrangement.

A cluster tree such as that of Fig. 6-5 can be searched in many different
ways. Intuitively the simplest method consists in proceeding from the top
downward in the cluster tree, by comparing the incoming query first with thecentroids of the topmost clusters, and continuing downward by next examining
the next level of centroids for the clusters that were sufficiently similar to thequery. This step is repeated by considering successively smaller clusters until
eventually the individual documents in some of the lowest-level clusters arecompared with the query. This is a top-down cluster search strategy based on
the availability of auxiliary files containing all cluster centroids.
An alternative bottom-up search strategy may be introduced that uses only
the clusters on the next to lowest level of the cluster tree. In that strategy, theincoming queries are compared with the centroids of the lowest-level clusters,
and the individual documents included in certain lowest-level clusters are thenconsidered [2,5,14]. The bottom-up search strategy reduces the storage cost for
the tree of centroid vectors and may lead to more rapid identification of docu­
ments actually relevant to a given query than the top-down search. Further­more, the likelihood of going down the wrong cluster path and winding up withuseless information is reduced when the comparisons with the top centroids are
eliminated. Since the number of low-level clusters may, however, be verylarge, an auxiliary index may be required to gain access to the low-levelclasses. This index may be conveniently implemented as an inverted file for all
low-level centroid terms. A typical search then proceeds by using the individ-

220

CHAPTER 6

ual query terms to access the inverted file of low-level cluster centroids. This
leads to the identification of one or more low-level clusters, and these in turnlead to the retrieval of individual documents located in these classes.
Additional details for cluster generation and searching are including in theremainder of this section.
*B

Classification Methods

One method for clustering a collection of objects uses similarity (or distance)measurements between each object and each other object in the collection. The
objects are grouped into classes when they exhibit sufficiently large similarities
or small distances. This process was illustrated earlier in Fig. 6-4, where an
item-item similarity matrix was used to generate several cluster arrange­ments depending on the threshold used.
The clustering methods based on the availability of item-item similarities
lead to a variety of graph-theoretical grouping strategies. Normally, rules are
imposed on the graph obtained by transforming the item-item similarity matrix
into a graph as shown in the example of Fig. 6-4. The following restrictions
could be imposed on the graph representing the object similarities:
1 The clusters are defined as the cliques of the graph, that is, as thegroups (maximal subsets) of items for which each item is connected to eachother item in the group.
2 The clusters could also be strings of items such that item a is connected
to b, and b is further connected to c, and so on until no further connected item
can be added to the string.
3 The clusters might also be defined as stars where some central item isconnected to all other items in the group.
4 Finally, the clusters could be connected components where an arbi­
trary path is found between each item in the component and each other item;the single-link method described in Chapter 4 is based on the use of connectedcomponents.
Consider, as an example, the connection graph of Fig. 6-4e obtained fromthe item-item similarity matrix of Fig. 6-4a using a similarity threshold of 0.50.
The following classes are obtained from Fig. 6-4e for the graph specifications
given earlier:
1 For the clique restriction, one finds one clique with three items and five
additional cliques each with two items (Dx,D3,D5), (Dx,D4), (D4, D6), (D2, D5),
(D2,D6), (D2,D4).
2 Several subdivisions into strings are possible for the graph of Fig. 6-4e.
Assuming that the strings to be produced are nonoverlapping, the following two
strings will cover the graph: (D3,DX,D4) and (D5,D2 ,D6); another string subdivi­
sion would be (D3,DX,D4,D2 ,D5) plus the single-item string (D6).
3 Various nonoverlapping stars can be generated from Fig. 6-4e such as(Dj ,D3,D5,D4) and (D2,D6).

RETRIEVAL REFINEMENTS

221

4
Finally for the connected component strategy, a single cluster is ob­
tained consisting of all six documents under consideration.
The example of Fig. 6-4 illustrates that even for the graphical clustering
methods that exhibit all the theoretically desirable characteristics such as being
stable and well-defined, many different cluster structures can be constructed
depending on various param eter settings and clustering requirements. The con­nection pattern between objects is uniquely determined by the threshold cho­sen for the item-item similarities. However, the final cluster arrangement also
depends on the graph representation used to define the clusters, and on addi­
tional rules that may be specified concerning the permitted size and overlap of
the clusters (the number of items included in a cluster and the number of items
jointly assigned to more than one cluster).
The graph-theoretical clustering algorithms tend to be expensive to imple­
ment when the number of objects to be grouped is large. In fact, the construc­tion of the item-item similarity matrix alone requires a comparison of each itemwith each other item, that is, the computation of about n2/2 similarity coef­
ficients for n items. A number of heuristic clustering methods have therefore
been developed for which the construction of an item similarity matrix is not
required.
Most of the heuristic methods are based on the prior availability and subse­
quent use and refinement of an initial set of clusters. In some cases, the prob­
lem under consideration may simply require that a set of new or unknown ob­
jects be added to an already existing cluster structure. Alternatively, when
initial clusters are not available, some easily identified property of the objects
might be used to define an initial set of trial clusters— for example, all objects
that have a given property or term in common could be entered into a common
trial class. Another possibility consists in taking a small subset of the objects to
be clustered and using these to construct a set of so-called core clusters. The
remaining parts of the collection that are not originally handled are then subse­
quently assigned to the existing core clusters.
Assuming the existence of an initial set of clusters, the heuristic methods
next proceed by constructing cluster representatives for the existing clusters.
The clustering operation itself is again based on similarity measurements be­
tween the objects to be clustered and the already existing cluster centroids. A
typical iterative cluster refinement process involves the following steps:
1 Compare each document D with all existing cluster centroids, and ob­
tain similarity coefficients SIM(D,Ck) for all clusters in the cluster structure.
2 Determine the cluster for which SIM(D,Ck) is largest for each given
document D and place D into that cluster (alternatively, if overlapping clusters
are desired, place D into all clusters for which the corresponding centroid simi­
larity is larger than some arbitrary threshold).
3 Recompute the cluster centroids based on the new document assign­ments, and return to step 1.

222

CHAPTER 6

4
Stop the process after a fixed number of iterations through steps 1 to 3
or alternatively stop after all document movements from one class to anotherhave ceased.
Such an iterative cluster reassignment process is normally less expensive
to perform than the graph-theoretical process described earlier, because thesimilarity coefficients are not computed for all pairs of items but only for all
items with respect to all cluster centroids. If one assumes that log n clusters
exist for the n items, the number of centroid-document comparisons is of ordern log n (instead of n2 as before). However, the heuristic clustering methods
are theoretically less satisfying than the graph-based methods because the final
cluster structure obviously depends on the initially available cluster arrange­
ment. This undesirable property also characterizes the one-pass clustering
methods described in Chapter 4. In that case, the documents are processed se­quentially one at a time, and each item potentially forms a new class if it does
not exhibit sufficient similarities with already existing clusters. The order inwhich the items enter into the centroid comparison process will then determine
the shape of the final clusters.
The two types of classification methodologies can be combined into a sin­gle process by using the less expensive n log n process (for example a simple
one-pass clustering system) to generate an initial set of trial clusters, and re­serving the expensive graph-theoretical method to refine and subdivide eachtrial cluster. Each trial cluster of size m (m being much smaller than the totalcollection size n) could then be broken down into several smaller clusters usinga graph-theoretical method requiring on the order of m2 vector comparisons.
Such a hybrid clustering process could generate useful low-level clusters thatare as effective as clusters produced by graph-type methods applied to the com­plete collection.
*C

Cluster Search Evaluation

Because of the substantial expense involved in clustering large document col­lections, a thorough evaluation of cluster search methods has never been per­formed. Only fragmentary results are available obtained with a few typical clus­
tering arrangements and a few sample document collections [14-17]. In
principle, the.tradeoff involved in using a clustered document collection for in­formation retrieval purposes, as opposed, for example, to using a standard in­verted file, is simple to describe: on the one hand, one may expect that im­proved recall and precision are obtainable from a search when related
documents are collected into common classes because the retrieval of a partic­
ular document then automatically leads to the retrieval of additional related
items; on the other hand, the clustered organization produces a good deal ofsystems overhead because of the cost of the clustering operation itself and therequirement to store an auxiliary file of cluster centroids. Furthermore, as will
be seen, the comparison of incoming queries with the centroid structure may in

RETRIEVAL REFINEMENTS

223

fact identify marginal search paths when the centroids appear to be similar tothe queries but the corresponding clusters contain few relevant documents.
It was seen in the preceding section that many different methodologies areavailable to cluster a given document collection. Moreover, given a particularclustering arrangement the comparison of user search queries with the avail­able cluster centroids and the identification of the relevant document clusters
can also be carried out in many different ways. Thus given a cluster structuresuch as the one in Fig. 6-5, one can proceed from the top down, choosing at
each level the most likely cluster centroid until eventually the documents in asingle cluster on the lowest clustering level are reached. Such a search, known
as depth-first, is likely to produce high precision searches that may, however,be deficient in recall. Higher recall may be obtained by following several paral­
lel paths of the cluster structure, leading to the eventual identification of several
low-level document clusters. Unfortunately no obvious search strategy exists
which will necessarily lead to the retrieval of most useful materials.
One problem arising in cluster searching is the difficulty of obtaining anunequivocal result from a comparison between a user query and a cluster cen­troid. Normally, an attempt must be made given a particular user query to esti­
mate the probability that a given cluster is a useful cluster. Such an estimate
can be based on the frequency of occurrence (or on the weight) of the individual
query terms in the corresponding cluster centroid. When the query terms col­lectively exhibit high occurrence frequencies in a cluster centroid, the pre­sumption may be that the corresponding cluster is useful for retrieval purposes.
Unfortunately, the higher level centroids normally represent broad subject
classes and the query-centroid comparisons may not identify any particular
centroid that is clearly preferable to the other centroids. Such a situation ob­
viously complicates the cluster searching task.
As an example of the efficiencies attainable in cluster searching, consider
some sample searches performed for several sets of search requests with a col­lection of 2,000 documents in computer science. A hierarchical cluster arrange­
ment was generated for the document collection using the one-pass clusteringsystem described in Chapter 4. The hierarchy consisted of four levels, illus­
trated in the scheme of Fig. 6-5, including 200 clusters on the lowest clusteringlevel with an average of 10 documents each. This arrangement was used withfour different search strategies [18]:1 A standard inverted file search, using an inverted term directory for all
terms occurring in the documents of the collection; the documents themselves
are entered into the document file in arbitrary order.
2 A standard inverted file search for which the document file is stored incluster order, that is, one access to the document file retrieves a cluster of re­lated documents.
3 An inverted file constructed for the centroids on the lowest cluster level
only, providing access to a number of low-level document clusters for eachquery term.

224

CHAPTER 6

4
A top-down search of the full cluster hierarchy based on a stored file of
all cluster centroids.
The auxiliary inverted term files and the cluster centroid files cannot nor­mally be stored in internal machine memory. In order to carry out the required
query-centroid comparisons, it is therefore necessary to transfer various por­tions of the centroid directory from external bulk storage to internal memory.
Such transfers from one type of memory to another are usually carried out for
fixed size blocks of data, known as pages. For the experiments under discus­sion, a page is defined as 4,096 characters of storage. A normal page transfer
process would transfer into internal storage the particular data page containing
the centroid needed at each particular time. To make room for a new page ofdata, an old page no longer in use must be transferred back to external storage
from internal memory. The standard way for doing this is the “least recently
used” (LRU) page replacement method which transfers out the page that hasremained unused for the longest time.
When only a single page is brought into storage at any one time, a complete
disk seek operation is needed for each page (that is , for each centroid) transferred
into internal memory. Such a strategy appears ill suited to the processing of hier­archical tree structures, because the need for a particular centroid vector nor­mally implies the simultaneous need for its descendants on a lower level of thetree or for its brothers on the same level of the tree. This suggests that a com­plete set of centroids ought to be brought into internal memory at the sametime, preferably consisting of the originally needed centroid together with its
immediate descendants and possibly its brothers. By using a so-called prefetch
strategy, the pages containing the descendants or brothers of a given centroid
can be prepared for transfer while the initial page is being sought. In these cir­
cumstances, a complete disk seek operation is still required for the initial page
to be transferred. The pages containing descendant and brother centroids can,however, be transferred at much lower cost amounting to only about one-tenth
the time required for a complete disk seek operation.
The file storage requirements for the several search systems are sum­
marized in Table 6-4. The document file itself requires 71 pages of data. The
Table 6-4

Storage Requirements for Cluster Searches(2,000 D o c u m e n ts in C o m p u te r S c ie n c e ; P age S ize = 4 ,0 9 6 B ytes)

Standard searchusing inverted filefor document terms
Search using the
low-level document
clusters only
Full top-down searchthrough cluster
hierarchy

Inverted term index
without weights
Document file
Inverted index to lowlevel centroids
Document file
Full centroid file (400terms per centroid)
Document file

110

84

146

1rI 39 pages
Il 71 pages
Ir 13 pages
I( 71 pages|f 75 pages
I^ 71 pages

225

RETRIEVAL REFINEMENTS

standard inverted term file (using as entries all terms occurring in the docu­
ments) uses 39 additional pages. Thirteen pages are needed to store an inverted
index for the short centroids on the lowest level of the cluster hierarchy; fi­nally, 75 pages are used to store the full hierarchy of cluster centroids. A clus­
ter storage search Using only the low-level centroids appears therefore to pro­
duce better storage efficiency than a standard inverted file search or a top-down
search through the full store of cluster centroids.
The average search precision and the average number of page faults re­quired to reach a given level of recall using the single-page replacement
process are shown in Table 6-5 for three of the four search methods previously
described [18]. The averages of Table 6-5 are computed for 23 short Boolean
queries containing an average of 4.8 search terms per query. Next to each sta­tistic, Table 6-5 also contains the percentage improvement or deterioration
over the standard inverted file search method.
A valid comparison of the search runs can be made only if the total numberof retrieved items over the 23 queries is approximately the same for all
methods. Since no choice is possible for the number of items retrieved by a
Table 6-5 Short Boolean Queries— Precision and Page Faults(23 Queries— Separate Relevance Assessments)
RelativerecallInverted document
terms (clustered)

Inverted low-level
centroids

Tree searcha Average precision comparison

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.900
0.888
0.847
0.845
0.838
0.830
0.828
0.824
0.817
0.815
b

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.406
0.406
0.403
0.393
0.388
0.385
0.356
0.346
0.329
0.329

-55%
-54%
-52%
-53%
-54%
-54%
-57%
-58%
-60%
-60%
-55.7%

0.277
0.277
0.255
0.212
0.203
0.192
0.183
0.162
0.149
0.141

-69%
-69%
-70%
-75%
-76%
-77%
-78%
-80%
-82%
-83%
-75.9%

Average page fault comparison (no prefetch)

4.89
5.54
5.87
7.44
8.53
10.26
11.21
12.21
12.94
12.94

3.00
3.50
4.20
4.20
4.45
4.50
4.50
4.65
4.65
4.95

-39%
-37%
-28%
-44%
-48%
-56%
-60%
-62%
-64%
-62%
-50%

14.90
14.90
14.85
16.55
16.43
17.83
18.96
21.17
21.83
21.83

+205%
+ 169%+ 153%+ 122%
+93%
+ 74%
+ 69%
+ 73%
+69%
+69%
+ 109.6%

226

CHAPTER 6

conventional Boolean search, that number must necessarily be used as a stan­
dard for all methods. For the query collection used in the experiments, a totalof 341 documents were retrieved by the conventional inverted file method overthe 23 queries. The threshold used for the clustered searches was therefore
chosen to retrieve approximately 15 documents per query (15 • 23 = 345).
Separate relevance assessments were available of each document with re­spect to each query (that is, the inverted file searches were not automaticallyassumed to produce perfect search output). Furthermore, the recall level ex­hibited in Table 6-5 is computed separately for each search method rather thanglobally. That is, relative rather than absolute recall levels are shown, definedas the proportion of relevant items retrieved at a given level out of the total
relevant that can be retrieved by each particular method.
The results of Table 6-5 indicate that the full cluster tree search is not com­
petitive with the conventional inverted file process either in precision or in thepage fault rate when short Boolean queries are processed. In that case only a
few lists of document references must be processed in the inverted file system,
corresponding to the few terms included in each query. The cluster tree must,however, always be traversed from top to bottom. The low-level cluster inver­sion is much more attractive in that case, since only about half as many pagefaults are needed as in the inverted file process. Both cluster search systems
do, however, produce substantially lower precision than the inverted file sys­tem.
The amount of work required by an inverted file search increases as thequery length and to some extent the number of documents to be retrieved in­crease. The experimental conditions of Table 6-5 thus favor the inverted filetechnology. When longer, vector-type queries are processed, the evaluation re­sults become very different. Table 6-6 contains both average precision and av­
erage page fault rates averaged over 33 long queries (16.8 terms per query)using page replacement methods with and without prefetch [18].
The results in Table 6-6a show that the standard inverted file search again
produces the best search precision. However, the cluster searches are now
more competitive than before: the tree search shows a deterioration of 15 per­cent in precision; for the inverted low-level centroids the precision loss is 19
percent, compared with the earlier losses of 76 and 56 percent, respectively.
The page fault rates which apply to the cluster searches conducted for the long
queries are much improved over the equivalent runs using the shorter queries.
Even with the unfavorable page-at-a-time (no prefetch) page replacement
method, the full tree search is nearly competitive with the inverted file list pro­cessing. Table 6-6c shows that with a prefetch page replacement, the tree
search is 30 percent better than the document inversion.
The results of Table 6-6 indicate that for the long, vector-type queries, acluster search method seems preferable to the conventional inverted list manip­
ulations. Even more clear-cut results in favor of the top-down cluster search
are obtained when a larger number of documents are retrieved in each searchthan the 15 used in the experiments of Tables 6-5 and 6-6 [18].

227

RETRIEVAL REFINEMENTS

Table 6-6 Long Weighted Vector-Type Queries— Precision and Page Faults(33 Queries; 15 Retrieved Items per Query)
Inverted document terms
RelativerecallClusteredstorageRandomstorage
a

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

14.8
15.7
17.5
18.7
19.9
21.1
22.1
23.2
24.5
25.5

**D

10.12
11.00
12.54
13.58
14.80
15.83
16.90
17.87
19.12
20.08

0.783
0.746
0.702
0.679
0.664
0.656
0.623
0.612
0.610
0.582

-12%
-14%
-17%
-19%
-20%
-20%
-23%
-24%
-22%
-23%
-19.4%

0.837
0.775
0.748
0.734
0.721
0.682
0.670
0.639
0.612
0.607

-6 %
-11%
-11%
-12%
-13%
-17%
-17%
-20%
-22%
-20%
-14.9%

14.9
17.4
18.2
19.2
21.0
23.2
24.5
26.8
29.5
31.8

+ 1%
+ 11%
+4%
+ 3%
+6%
+ 10%
+ 11%
+ 16%
' +20%+25%+ 10.7%

6.44
7.62
8.16
8.76
9.81
11.06
11.87
13.17
14.79
16.06

-36%
-31%
-35%
-35%
-34%
-30%
-30%
-26%
-23%
-20%
-30%

Average page fault comparison (no prefetch)
15.2
16.1
18.2
19.4
20.6
21.8
23.2
24.3
26.0
27.4
c

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

Complete tree
searchAverage precision comparison

0.893
0.871
0.844
0.835
0.827
0.817
0.812
0.803
0.784
0.757
b

Inverted low-level
centroids

+2%
+2%
+4%
+4%
+4%
+4%
+ 5%
+ 5%
+6%
+9%
+4.5%

18.1
19.4
22.9
24.4
25.9
28.2
31.7
34.7
36.7
37.9

+23%
+23%
+31%
+30%
+30%
+34%
+44%
+50%
+50%
+49%
+36.4%

Page fault comparison (with prefetch)
10.55
11.47
13.29
14.48
15.66
16.84
18.18
19.19
20.78
22.05

+4%
+4%
+6%
+7%
+ 6%
+6%
+6%
+7%
+9%
+ 10%
+6.7%

12.97
14.02
17.09
18.23
19.59
21.36
24.01
26.28
27.99
28.80

+28%
+27%
+36%
+34%
+32%
+35%
+42%
+47%
+46%
+43%
+37%

Automatic Pseudoclassification

It was mentioned earlier that automatic classification techniques can be used toconstruct affinity classes for either documents or terms. In the former case, theprincipal aim is to impose structure on the search system in the hope of gaining
search efficiencies during the comparison between user queries and stored doc-

228

CHAPTER 6

uments. When terms are clustered, the result is a term class arrangement, or
thesaurus, that can be used for the construction of expanded search requests
and document descriptions by inclusion in the vectors of synonyms and otherterms related to those originally available. It is generally accepted that the useof a thesaurus in the indexing and search formulation process can enhance re­trieval effectiveness [19,20].
The use of thesauruses in retrieval was briefly illustrated in Chapter 3 aspart of the discussion on automatic indexing. Thesauruses are normally con­structed manually by subject experts, although automatic classification proce­dures are usable in principle based, for example, on use of similarity informa­tion for term pairs. The similarity between terms might be based on thefrequency distribution characteristics of the terms across the documents of acollection. Thus, if two or more terms co-occur in many documents of a given
collection, the presumption is that these terms are related in some sense andhence can be included in common term classes. Alternatively, when term dis­tribution information is not available, term classifications can be automaticallyconstructed by adapting an existing document classification and assuming thatterms which occur jointly in the document classes could be used to form thedesired term classes [21-26].
Even though considerable effort has been devoted to the development of
automatic thesaurus construction methods, a really viable thesaurus generation
process is still lacking. One problem is the difficulty of identifying representa­
tive document collections which could guarantee that the resulting term distri­bution characteristics would be applicable to other collection environments.
Unfortunately, there is no obvious way for obtaining such representative docu­
ment samples, short of using large comprehensive collections. However, large
collections cannot be processed at a reasonable cost. In some studies, termclasses have been generated from locally defined, small subcollections of docu­
ments, such as the set of documents retrieved in response to a given searchrequest [27]. Whether such procedures will prove generally viable remains tobe seen.
Since document retrieval environments normally operate in an on-line
mode, permitting users to communicate directly with the retrieval system, thequestion arises whether information obtained from the user population during
the retrieval effort might be used as an aid in constructing term classifications.
Such a consideration forms the basis for the so-called pseudoclassification pro­
cess where the normal use of term frequency information and term probability
distributions is replaced by user relevance information of documents with re­spect to search requests. Since the term classification obtained by a pseudo­classification process depends on particular user queries and specified subject
areas, the term classes that are obtained may be applied to other documents inrelated subjects only if the input data are comprehensive enough to make themapplicable to other user groups in different collection environments. The pseu­
doclassification process is based on the existence of four distinct types of infor­
mation: (1) a collection of documents in a given subject area, (2) a set of infor-

RETRIEVAL REFINEMENTS

229

mation requests addressed to that collection, (3) a retrieval threshold T whichleads to the retrieval of a given document in answer to a particular query when­ever a similarity measure between the document and query exceeds T, and (4) aset of user relevance assessments specifying the relevance of individual docu­
ments with respect to the available queries [28].
Consider, in particular, a given collection of n documents and m queries in
a topic area. The previously specified information can be used to construct twobinary n by m matrices specifying the retrieval status and the relevance proper­
ties, respectively, for each document-query pair (DOC,,QUERY,). Specifi­
cally, let VAL and REL represent the retrieval and the relevance matrices for agiven collection of documents and queries. Thus VAL,, may be defined to beequal to 1 whenever DOC, is retrieved in response to QUERY,, that is, when­ever SIM (D O Q ,QUERYj) > T ; otherwise VALjj is set equal to 0. Correspond­
ingly RELij is defined as 1 when DOQ is specified as relevant to the QUERYj
and as 0 otherwise. The relevance and retrieval matrices are represented in Fig.
6-6 for typical document and query collections.
Consider now the results of a retrieval operation. It is obvious from thedefinition of the VAL and REL matrices that four different situations can arise
for a given document-query pair (D O Q , QUERYj):
1 Both VALjj and R E LUare defined equal to 1, implying that the relevant
document D O Q is retrieved in response to QUERYj.
2 Both VALjj and RELjj are defined equal to 0, implying that the nonrelevant document D O Q is rejected in response to QUERYj.
QUERY,QUERYmquery2DOC,

VA L,,

v a l ,2••

V A L ,mdoc2

v a l 2,

VAL^

••

VAL2m

DOC„

VALn,

V A Ln2••

V A LnmVAL(a)
QUERY,QUERYmquery2

DOC,

REL,,

REL,2

doc2

r e l 2,r e l 22

REL2m

D0C„

REL„1

RELn2

RELnm

••

REL,m

REL

•(b)
Figure 6-6 Retrieval and relevance matrices, (a) Retrieval m atrix VAL. (VAL,, implies that
DOCj is retrieved in response to QUERYj.) (b) Relevance m atrix REL. (REL13implies that DOCj
is judged relevant to QUERYj.)

CHAPTER 6

230

3
and 4 VALy = 1 and RELy = or vice versa VALy = 0 and RELy =1, implying either that a nonrelevant document is retrieved or that a relevant
item is rejected.
From the viewpoint of retrieval effectiveness, cases 1 and 2 represent afavorable outcome, whereas 3 and 4 constitute system failures. A perfect sys­
tem will produce VAL and REL matrices that are identical, implying that all(DOCi,QUERYj) pairs fall into classes 1 or 2, being either correctly retrievedor correctly rejected. Correspondingly, the number of (DOQ,QUERY]) pairs
falling into classes 3 and 4 may be used as a measure of system inadequacy or
failure.
To improve the operations of a retrieval system it is necessary to introduce
methodologies capable of shifting some of the (DOC],QUERY]) pairs fromclasses 3 and 4 to classes 1 or 2, while ensuring at the same time that
(DOCj,QUERY]) pairs that are already correctly classified are left undisturbed.
Two different situations may arise:

3 When a document is incorrectly retrieved (VAL]] = 1 and RELy = 0),
it becomes necessary to decrease the similarity coefficient SIM with the queryso that eventually SIM(DOC],QUERY]) < T, thus ensuring the rejection of
DOC] in response to QUERY].
4 On the other hand, for documents that are incorrectly rejected(VALy = 0 and RELy = 1), the similarity coefficient with the query must be
correspondingly increased to achieve SIM(DOC],QUERY]) > T, causing the
document to be retrieved.
The size of the similarity coefficients for query-document pairs can be al­tered by introducing refined automatic indexing methods designed to change
the original term assignment to queries and documents. Alternatively, sophisti­
cated term weighting strategies could be introduced. A third possibility consists
in utilizing term relationship information. This last strategy forms the basis forthe pseudoclassification process. Consider in particular a given term classifica­tion or thesaurus, in which p different classes are used to group the terms into
affinity or similarity classes. The term classification is represented in matrix
form in Fig. 6-7. The document and query vectors can now be represented bylengthened constructs as follows
DOC] = (dj^dij, . . . ,dit,Cu ,ci2, . . . ,C]P)QUERY] — (qji,qj2, • • • >qjtjCji>Cj2> • • ■ ,Cjp)
where dlk represents the assignment of term k to document i and qjk represents
the assignment of term k to query j. The elements clk and cjk represent theterm class assignments to the respective vectors. In each case cik (or cjk) is set
equal to 1 whenever class k pertains to document i (or to query j). To in­crease the size of the similarity measure between a given document-query231

RETRIEVAL REFINEMENTS

CLASS.

CLASS,p

0

TERM
TERM.

CLASS.

0

1

GROUP
TERM,

Figure 6-7
CLASS,.)

0

0

Classification m atrix GROUP. (GROUPy = 1 im plies that TERM, occurs in

pair, it suffices to place into a common term class two or more terms that did
not originally produce a term match in the respective vectors. This operation
adds one or more common class identifiers to both vectors, thereby increasing
the similarity between them. Analogously, the similarity coefficients can be
decreased by appropriately reducing the number of matching term classes.
Consider, as an example, two typical vectors consisting of six terms each(where a 0 entry is used to denote a term that is absent):
D O Q = (0, 0, lift, propeller, roll, wing)
QUERY, = (aileron, drag, 0, propeller, 0, wing)
In their original form, two terms (propeller and wing) are present in both vec­
tors. If the document is now assumed to be incorrectly rejected (RELU = 1 and
VALU = 0), the size of the matching coefficient can be increased by placing
into a term class two or more initially nonmatching terms. Specifically for thetwo sample vectors, aileron and lift could be placed into a common class k (oralternatively, drag and lift, or roll and aileron, or roll and drag); in each case,the identifier for class k would be added to both vectors thereby increasing thesimilarity between them. For example, placing terms aileron and wing intoclass k adds the indicator for class k to the DOC, vector because of the pres­ence of lift in DOC,, and the class k indicator to QUERY, because of the pres­ence of aileron in the original query vector. This operation on the term classifi­
cation produces the following lengthened vectors exhibiting one additional
matching identifier:
DOCi = (0, 0, lift, propeller, roll, wing, “ class k” )QUERY, = (aileron, drag, 0, propeller, 0, wing, “ class k ” )When a document is incorrectly retrieved (VALtj = 1 and RELy = 0), thereverse operation is performed and certain terms are removed from the thesau­
rus classes so as to decrease the number of matching classes assigned to both
vectors.
The assignment of terms to classes (or the eventual removal of terms fromclasses) presents no difficulty in principle when the number of document-term

232

CHAPTER 6

pairs is small and when a large number of thesaurus classes can be introduced.
Unfortunately, in practice it is necessary to operate with a large number of(DOC,QUERY) pairs and a restricted number of term classes (small p), and thetask consists in constructing the best possible term classification which places a
maximum number of (DOC,QUERY) pairs into the correctly retrieved or cor­
rectly rejected groups.
Since a given (DOC,QUERY) pair does not occur in isolation in the re­trieval system, an operation on the term classification undertaken to help re­trieve (or reject) a given document may have unfortunate effects on other docu­
ments in the collection. Thus, a given operation such as placement of TERM,
and TERMj into class k may properly raise the similarity measure for a particu­lar (DOC,QUERY) pair and shift that pair from class 4 to class 1; at the sametime that same operation may carry a large number of (DOC,QUERY) pairs outof the 1 and 2 classes and place them into the undesirable 3 or 4 classes. Henceit becomes necessary to check the applicability of a proposed thesaurus opera­tion by determining its effect on all (DOC,QUERY) pairs in the system, and tocarry out a given operation only when its overall effect is judged to be benefi­cial.
The standard pseudoclassification process which is designed to produce an
optimal term classification in which the maximum possible number of(DOC,QUERY) pairs satisfy assessment (that is, belong to classes 1 and 2) isthen burdened with a number of substantial disadvantages:
1 To prove the optimality of a given term classification for a particularquery and document collection, it is necessary to evaluate each perturbation of
the classification by checking its effect on all other (DOC,QUERY) pairs in thesystem; thus each classification step necessarily involves all (DOC,QUERY)
pairs.
2 The sequence in which the individual (DOC,QUERY) pairs are consid­
ered and the structure of the term classification available at the beginning of theprocess may complicate the classification process.
3 A given thesaurus operation may have to be considered many times in agiven pass through the (DOC,QUERY) pairs, because although undesirable ata given moment in time, that same operation may be useful at a later time after
additional changes have been introduced in the classification.
A variety of heuristic procedures have thus been proposed for the con­struction of acceptable term classifications. These methods differ from the pre­viously described situation in that convergence of the procedures can normallybe proved, but not optimality of the result.
In the standard pseudoclassification method the changes made to the termclassification may lead to oscillations because a change once introduced maylater have to be reversed. Alternatively, sequences of classification changes
may be developed which are repeated indefinitely, so that the process runs for­ever. To avoid this possibility, on-the-spot global decisions can be introduced
to ascertain whether a given operation on the classification should be carried

RETRIEVAL REFINEMENTS

233

out at any given time. The idea is to process the (DOC,QUERY) pairs in se­quence and to make the applicability of a given thesaurus operation dependent
only on the (DOC,QUERY) pairs previously processed in the current pass.
Furthermore, the whole process must be guaranteed to terminate. The follow­
ing two strategies have been shown to be effective in practice [29,30]:
1 A proposed change in the term classification is accepted if no essential
deterioration is produced for any other previously processed document-query
pair. By essential deterioration is meant that the document-query similarity fora relevant document currently retrievable is not decreased so far as to render
the item nonretrievable; similarly, the correlation measure for a nonrelevant
item currently rejected is not increased so much that the item is eventually re­trieved.
2 A proposed change in the term classification is accepted if the numberof document-query pairs that exhibit improvements as a result of the change
exceeds the number of pairs exhibiting deteriorations. Improving means in­creasing the similarity for relevant documents, and vice versa for nonrelevant
items. Deterioration is the reverse of improvement. This strategy uses a global
condition in which correctly retrieved or rejected pairs are allowed to cross theretrieval threshold provided only that overall the gains exceed the losses.
Several small-scale evaluations of these strategies were carried out withexperimental document collections. In each case, the first strategy appears
most effective in increasing the number of (DOC,QUERY) pairs that satisfy therelevance assessment (correctly retrieved or correctly rejected pairs), while thesecond strategy should be used in order to obtain the best recall and precision
results.
The normal pseudoclassification process builds a complete term classifica­tion matrix which specifies for each term one or more classes to which the term
may be assigned during the course of the operations. However, the termclasses themselves are never used for retrieval purposes. Instead relations be­
tween term pairs are used by adding special identifiers to the document andquery vectors whenever a particular term pair is included in a common class.
This suggests that the construction of a full-term classification could be re­placed by a simple determination of term pair relationships followed by the in­corporation of term pair relationship indicators (instead of term class indica­tors) in the query-document similarity computations. Furthermore, thedetermination of the relationships between term pairs might depend on the
global occurrence characteristics of each particular term pair in the documents
and queries of a collection. Such considerations have led to the construction ofterm-term similarity matrices used for pseudoclassification purposes in which
the term relationships are derived from the term occurrence frequencies in the
documents of a collection [31-32],
Consider, in particular, the collection of term pairs (TERMk ,TERMh) ob­
tainable from a collection of queries and documents with the property that oneof the terms in each pair occurs only in a given DOCi while the other occurs

234

CHAPTER 6

only in QUERYj for a given (DOCi,QUERYj) pair. Alternatively, one of thetwo terms might be assigned to both DOQ and QUERYj, while the other isassigned to either query or document alone. Such a term pair is called an ac­
ceptable pair. Clearly a full term match does not exist for an acceptable termpair when a standard vector matching process is used, because the assignmentof the two terms differs for the components of a given (DOCt,QUERYj) pair.
If one assumes that the acceptable term pairs occur principally in docu­
ment-query pairs that already satisfy assessment, that is (DOQ,QUERYj) pairsthat are either correctly retrieved or correctly rejected, then no particular ac­tion is warranted. On the other hand, if the term pairs occur mainly in(DOCj,QUERYj) pairs for which DOQ is relevant to QUERYj (RELjj = 1) but
the document is not retrieved (VALjj = 0), then one might conjecture that apositive semantic relationship exists between the respective terms and that thisterm relationship has not in fact been taken into account in the query-document
match. Analogously, if the term pairs occur in query-document situations
where the documents are retrieved even though they are not identified as rele­vant (RELjj = 0 but VALjj = 1), then a negative semantic relationship may be
assumed to exist between the corresponding terms.
This suggests the following term matching strategy. For each acceptableterm pair (TERMk,TERMh) a term relationship factor is computed as a directfunction of the number of document query pairs containing the term pair forwhich RELjj = 1 and VALjj = 0, and as an inverse function of the number of
document-query pairs containing the terms such that RELjj = 0 and
VALjj = 1. The term relationship factor may then be incorporated into thequery-document matching process in an attempt to increase the similarity coef­
ficients for documents that are incorrectly retrieved or incorrectly rejected.
The term relationship factors can be computed in a single pass through the(DOCj,QUERYj) pairs to construct a term-term relationship (TTR) matrix ofdimension t by t containing for each acceptable term pair (TERMk,TERMh) the
corresponding number of (DOCj,QUERYj) pairs for which RELjj — 1 andVALjj = 0 as well as the number of (DOCj,QUERYj) pairs for which
RELjj = 0 and VALjj = 1. In particular, for a given (TERMk,TERMh) pair(k > h), the below diagonal (k,h)th element of the term-term relationship ma­trix may be used to store the positive count, Pos(k,h), of term-pair occurrencesin (DOCj QUERYj) pairs for which the term pair is acceptable while the docu­
ment is incorrectly rejected. Analogously, the above diagonal (h,k)th matrix
element stores the negative count, Neg(k,h), of term pair occurrences in(DOCj,QUERYj) pairs where the document is incorrectly retrieved. An appro­
priate term relationship function T(k,h) for terms TERMk and TERMh might bedefined asn ,)_ Pos(k,h) - a Neg(k,h)
Pos(k,h) + a Neg(k,h)

for some constant a.

RETRIEVAL REFINEMENTS

235

Aileron

Drag

Lift

QUERYk

0

1

0

1

0

1

DOC,

1

1

1

0

0

1

DOC,

1

0

0

1

1

1

Propeller

Roll

Wing

(a)

(DOC„ QUERY*): RELik = 1, VAL,k = 0(DOCj, QUERYk): REL|k = 0, VAL]k = 1(b)(DOC;, QUERYk)(aileron, drag), (aileron, propeller), (aileron, wing), (drag, lift)(drag, propeller), (lift, propeller), (lift, wing), (propeller, wing)(DOCj, QUERYk)(aileron, drag), (aileron, propeller), (aileron, wing), (drag, propeller)(drag, roll), (drag, wing), (propeller, roll) (roll, wing)(c)

Aileron

Drag

L ift

Propeller

Roll

Wing

Aileron
Drag
TTR

L ift
Propeller
Roll
Wing

Term relationshipformulaNull relationship-r,,.
_ Pos (k, h) - Neg (k, h)
IIK' n' Pos (k, h) + Neg (k, h)Positive relationship

Negative relationship

Tlaileron, drag) = 0

Tldrag, lift) = 1

Tldrag, roll) = -1

T(aileron, propeller) = 0

Tldrag, wing) = -1

Tlaileron, wing) = 0

T (lift, propeller) = 1
T (lift, wing) = 1

Tldrag, propeller) = 0

Tlpropeller, wing) = 1

Tlpropeller, roll) = -1
T(roll, wing) = -1(e)Figure 6-8 Term relationship com putation, (a) O riginal term vectors, (b) Relevance charac­
teristics. (c) Acceptable term pairs, (d) Term-term relationship matrix, (e) Term relationshipfactors.

CHAPTER 6

236

The single-pass construction of the term-term relationship matrix consists
in processing each (DOQ,QUERYj) pair in turn, identifying the acceptableterm pairs, and increasing the count stored in the (k,h)th or (h,k)th matrix ele­ments depending on whether the term pair (TERMk,TERMh) is associated withan incorrectly rejected or an incorrectly retrieved document-query pair [3132], An example is given in Fig. 6-8 for two document vectors DOQ, DOQ andquery QUERYk, where DOQ is assumed incorrectly rejected and DOQ incor­
rectly retrieved. The acceptable term pairs are listed in Fig. 6-8c. The corre­
sponding term-term relationship matrix is given in Fig. 6-8d and the term rela­tionship computations are included in Fig. 6-8e.
It remains to define a vector similarity function incorporating the normal
similarities between the term vectors DOQ and QUERYj, as well as the added
term relationships derived from the term-term relationship matrix. Let
SIM(DOQ,QUERYj) represent the matching function used to compare the
DOQ and QUERYj vectors, and let SIM^TERMk ,TERMh) andSIM2(TERMk,TERMh) represent similarity functions based on the occurrence
counts of positively [T(k,h) > 0] and negatively [T(k,h) < 0] related termpairs, respectively. Then an appropriate composite similarity function could be
defined as

NEWSIM(DOQ,QUERYj) = a0SIM(DOQ,QUERYj)+ 2 ajSIMj(TERMk,TERMh)k.h+ 2 a2SIM2(TERMk,TERMh)
k.h

(13)

for properly chosen constants a0, at , and a2, similarity functions SIM, SIM ,,and SIM2, and acceptable term pairs (TERMk,TERMh) contained in the appro­
priate query-document vectors. The summation signs preceding the second andthird terms of expression (13) indicate that the term pair similarity factors need
to be summed for all acceptable (TERMk,TERMh) pairs contained in a given
pair of query-document vectors.
Experimental evaluation results available for small document collectionsof several hundred documents and several dozen queries show improvements
for the composite similarity function NEWSIM over the standard cosine simi­
larity measure ranging from 10 percent in the precision values to over 30 per­cent in precision for fixed recall levels [32].
5

DYNAMIC QUERY ADJUSTMENT

A

General Considerations

Most operational retrieval systems offer an interactive search environment inwhich users, or search intermediaries, communicate directly with the searchsystem and responses are furnished more or less instantaneously following sub­mission of the search requests. Two kinds of interactive manipulations may be

RETRIEVAL REFINEMENTS

237

carried out during the course of an information search: the first relates to thesubmission of queries (search terms) and to the viewing of displayed responses;
the other is the construction of the query formulations, sometimes aided by dis­
plays of thesaurus contents.
In some of the more sophisticated on-line systems it is possible to list for agiven term all alphabetically related terms, or terms included in the same the­saurus category as the original term. In constructing an effective query state­ment, information about the number of items retrieved in response to earlier
query formulations (known as the number of “hits”) could then be useful; al­ternatively, the display of portions of retrieved documents or of documents re­lated to those retrieved earlier can also be used for query reformulation pur­poses. Typically, the number of documents retrieved furnishes some idea about
the specificity of the search terms used in the current query formulation: theterms can then be either broadened if the aim is to increase the number of re­trieved items, or they can be narrowed in the opposite case. The display of therelated search vocabulary or of previously retrieved document texts immedi­
ately suggests additional or alternative query formulation possibilities.

Stop

Figure 6-9 Typical interactive retrieval
sequence.

CHAPTER 6

238

Currently available evidence indicates that the query reformulation pro­
cess is easier to manage by the user when the feedback information utilized forthe formulation of query statements consists of previously retrieved document
excerpts or surrogates rather than of vocabulary displays [33-36]. This reflects
the fact that the display of retrieved documents furnishes indications of how thesystem has interpreted the user queries, but vocabulary displays do not. How­ever, vocabulary displays can be produced inexpensively before performing
any searches at all, but document displays are dependent on a prior search.
The more sophisticated, existing interactive search systems simplify thealteration of query statements by maintaining in storage various stages of ear­lier query formulations, thereby enabling the user to perform only selective al­
terations at each step. Appropriate tutorial features may also be used during thesearch process, including the display of multiple-choice response frames thatgive the user a choice of processing steps to perform next, as well as backtrack
methods capable of returning to earlier displays. A typical interactive search
process is illustrated in the chart of Fig. 6-9 [37].
*B

Feedback Theory

The query reformulation methods mentioned earlier are designed to generate
query statements capable of retrieving the relevant items and of rejecting thenonrelevant ones. When the query modification is carried out manually, theprocess is difficult to control, first because the characteristics of the relevant
and nonrelevant items are known imperfectly, and also because document
characteristics are not easily transformed into correct query formulations.
The relevance feedback process described in Chapter 4 relieves the user,
or search intermediary, by automatically generating new query formulations
based on relevance assessments obtained from the users during earlier search
operations. More specifically, a newly constructed query will exhibit a highsimilarity with the document set previously identified as relevant and a low sim­
ilarity with the nonrelevant document set. Assuming that the set of relevant
documents DR with respect to a query is known, and hence also the set ofnonrelevant documents DN_R, the best query Q is one that maximizes a func­tion F defined as the difference between the average query-document similarity
for all relevant items and the average query-document similarity for the nonre­
levant ones. That is, a query vector Q is wanted which maximizes F, where
F = SIM (Q A ) - SIM (Q A )
Dl€DR

(14)

DteDN_R

SIM represents the average similarity coefficient between the query and the setof all documents included in the relevant and nonrelevant document subsets,
respectively. When the similarity between vectors is measured by the cosine
coefficient, the optimal query has term weights proportional to the difference
between the average weights of the terms in the relevant and the average

RETRIEVAL REFINEMENTS

239

weights of terms in the nonrelevant items [expression (5) in Chapter 4] [38,39,
40].
In practice the relevant and nonrelevant document sets DRand DN_Rare ofcourse not known in advance— if they were, no search would have to be con­ducted to identify them. Instead a query statement is used to retrieve a numberof documents. The user then identifies some subset DR/ of relevant items andsome subset DN, of nonrelevant items. A new query can then be constructedproportional to the difference between the average of the R' relevant items pre­viously identified and the N' nonrelevant items [expression (6) of Chapter 4].
This query will not, however, perform well unless the subsets DR. and D,r are
representative of the actual relevant and nonrelevant sets DRand DN_Rfor the
given query.
Consider as an example the situation of Fig. 6-10 where the original queryis assumed to have retrieved three relevant and four nonrelevant items (locatedinside the dashed line of Fig. 6-10). The feedback query actually constructed by
the normal relevance feedback system (open triangle in Fig. 6-10) will lie in thecenter of the set of relevant items where the average distance to the relevant issmallest. When that query is actually used for retrieval, a great many nonrele­vant items located outside the original retrieval perimeter will then be re­trieved. The ideal feedback query (filled triangle in Fig. 6-10) would be situatedmuch closer to a set of relevant items not previously retrieved and farther awayfrom the relevant items retrieved earlier. The retrieval failure illustrated in Fig.
6-10 can be avoided in part by deemphasizing the role of the previously re-.
trieved items in constructing a feedback query and assigning greater impor-:tance to the original query statement. In other words, the feedback query is
expected to be reasonably close to the original query statement, and in addi-1
tion, it should exhibit a greater resemblance to the items previously identified
as relevant than to the nonrelevant ones. A typical formula used to construct an :Figure 6-10

Unfavorable relevance feedback situation.

240

CHAPTER 6

improved query statement Q' from an original query Q, a set of R' documents
previously identified as relevant, and a set of N' documents identified as nonrelevant is given by<15)
where a, (3, and y are constants, and the terms in parentheses represent theearlier query statement, and the average relevant and average nortrelevant pre­viously identified documents.
The relevance feedback operation is most effective when the relevant doc­
uments are tightly clustered and hence exhibit large pairwise similarities, andthe nonrelevant documents are also tightly clustered. At the same time the dis­
tance between the relevant and nonrelevant items should be large; that is, thesimilarities between them should be small (see Fig. 4-14a for a schema repre­
senting such an ideal document space).
*C

Feedback Variations

The relevance feedback process can be implemented in a variety of different
processing modes. The formal feedback equation [expression (15)] makes pro­visions for the incorporation of both relevant and nonrelevant documents in the
feedback process. However, the role of the two document types is basicallyunequal: when the relevant items are used to update the query, certain terms
are added to the query and the weight of other terms is increased; the query isthen forced to move in the direction where other relevant items may be ex­pected to be located. When nonrelevant items are used for feedback purposes,
certain terms are deleted from the query, and other term weights are decreased.
The negative feedback operation diminishes the affinity of the query with someitems but does not provide alternative directions to control the query move­
ment. Thus a positive feedback strategy, where relevant documents are used to
update the query serves to construct new queries that will exhibit greater re­semblance with the items Originally defined as relevant. A negative strategy
using the nonrelevant items for query updating decreases the query similarity
with these nonrelevant items but may not provide a positive direction toward
which to move.
The relevance feedback process can then be executed in the following
modes [41,42]:
1 A positive mode where relevant documents are available for feedback
purposes
2 A negative mode where nonrelevant documents are used to update thequery
3 A mixed mode incorporating both positive and negative modes
In each case, the number of documents used to update the query can be varied.

241

RETRIEVAL REFINEMENTS

Among the strategies that have been formally evaluated are the standard mixed
strategy [equation (15)], a strategy using all relevant items that may be avail­able but only one nonrelevant document (normally the one retrieved earliest ina search providing ranked output), and a system which emphasizes the original
query statement and deemphasizes the role of the feedback documents [the aparameter in expression (15) receives a large weight].
A positive relevance feedback operation is illustrated in the example ofTable 6-7. The initial query vector is shown in Table 6-7a. The term weights arelisted under the corresponding terms in each case. The updated query (Table
6-7c) contains terms from document 102 originally retrieved and identified as
relevant to the query. Two document vectors (numbers 80 and 81) are shown at
the bottom of Table 6-7 whose retrieval rank in order of query-document simi­
larity improves from 14 to 7 and from 137 to 6, respectively, as a result of the
feedback operation. A comparison of the vectors in Table 6-7b, d, ande reveals
that the feedback operation for document 102 is directly responsible for the re­trieval improvement of documents 80 and 81.
The positive feedback strategy is obviously not applicable when no rele­vant documents are retrieved by the original query vector. Furthermore theTable 6-7

Positive Relevance Feedback Illustration
Illustration

Vector typea

Initial query vectorb

Relevant document 102
retrieved with rank 2(partial vector)

cQuery modified bydocument 102d

Relevant document 80(improves from rank 14 torank 7; partial vector)
Relevant document 81(improves from rank 137 torank 6; partial vector)eairplane available blast dynamic
12
12
12
12
gust information regime response
12
12
12
12
subsonic
12
gust lift oscillating penetration
48
48
12
12
response subsonic sudden
24
12
12
airplane available blast dynamic
12
12
12
12
gust information lift oscillating
60
12
48
12
penetration regime response subsonic
12
12
36
24
sudden12
gust lift penetration sudden
24
72
12
12
lift
84

oscillating
12

sudden12Adapted from reference 13.
Q uery Q146: W hat in fo rm a tio n is available fo r dynam ic response o f airplanes to gusts o r blasts in
subsonic regim e?

242

CHAPTER 6

strategy must fail when dissimilarities are evident in the set of retrieved docu­
ments. In that case, the new query is in principle required to approach several
different directions at once, and the effect of the feedback operation becomes
unpredictable. A negative feedback operation then becomes mandatory.
A comparison of the positive and mixed retrieval strategies indicates that,on the average, the performance of queries that do retrieve some relevant docu­
ments in the initial search is not hindered by incorporating some nonrelevant
documents in the feedback operation. However, the amount of perturbation in
the query vectors is normally larger for the mixed feedback system than for thepurely positive one. The mixed strategy must therefore be used with care be­cause of the greater potential for improper query disturbance.
The purely negative feedback strategy is even more difficult to control.
Consider the case of Table 6-8, where the most important query term (“dataset”) is subtracted out because that term happens to have been present in someof the nonrelevant items previously retrieved. Various solutions can be devised
which will avoid the predicament illustrated in Table 6-8. One possibility con­sists in leaving original query terms intact in a negative feedback situation; theupdated query will then consist of the original query terms plus additional nega­tively weighted terms taken from the nonrelevant documents previously re­trieved. Alternatively, a thesaurus could be used to add related terms to theoriginal query vector prior to the negative feedback operation. An illustrationof such a modified negative feedback system is shown in Table 6-9 for the query
previously used as an example in Table 6-8. A comparison of the final query
statements shows that the problem exhibited in Table 6-8 is avoided by the pro­
cess of Table 6-9 [13,42,43].
Several variants of the basic relevance feedback system have been de­scribed in the literature. These include a query splitting system designed to gen­erate several subqueries from a given original query whenever the set of rele­vant items retrieved by a given query is not sufficiently homogeneous. Each of
the subqueries is then expected to retrieve a different set of relevant items [44].
Another feedback variant, known as “ cluster feedback,” constructs separate
feedback queries from the relevant and/or nonrelevant documents located indifferent document clusters in a clustered collection [13]. This last process thus
performs the feedback operations separately in each document cluster. The
feedback refinements remain to be thoroughly evaluated.
Table 6-8

Example of Inadequate Negative Feedback

Type of vector

Illustrationa

Initial query vectorb

Sum of retrieved
nonrelevant documents
Standard negative
feedback result

available current data set specification
12
12
12
12
access data set file list structure
24 24
48
60
84
available current specification
12
12
12

c

Adapted from reference 13.
Query: Please give spe cifica tio n fo r all curre ntly available data sets.

RETRIEVAL REFINEMENTS

Table 6-9

Negative Feedback with Related Concepts for Query of Table 6-8Type of vectoraInitial query vectorbConcepts related to “ data set”
with correlation strengthcRelated concept vector (top 5
concepts with weight of 24)
Query vector with related concepts

d

e
t

243

Sum of retrieved nonrelevant
documents
Updated query vector (computed by d - e with initial query
terms intact)

Illustration
available current data set specification
12
12
12
12
access bandwidth file interface line list
77
28
50
47
58
52
retrieval sort structure transmission
49
40
49
30
access file interface line structure
24
24
24
24
24
access available current data set file
24
12
12
12
24
interface line specification structure
24
24
12
24
access data set file list structure
60
24 24
84
48
access available current data set interface
-2 4
12
12
12
24
line list specification structure
24 -2 4
12
-60

The basic relevance feedback process may be expected to produce between
10 and 20 percent improvement in precision for fixed recall levels. When a sec­
ond feedback iteration is added, that is, when a modified query is itself modi­
fied a second time by a feedback process, additional improvements of a few
percentage points may be gained.
An evaluation of the relevance feedback process raises complex problems
that are not normally met in the evaluation of single search systems. In particu­
lar, it is unclear how documents should be treated that were originally retrievedby a given query and are retrieved once more by the modified feedback query.
Some of these documents may well be relevant to the queries. However, a user
may not be interested in seeing for a second time items that were already re­trieved in an earlier search iteration, and the repeated retrieval of such relevant
items should not be included in the recall-precision computations.
Several feedback evaluation systems have been proposed in the literature.
The most effective of these known as the “test and control” evaluation, is rep­resented in simplified form in Fig. 6-11 [45]. The idea is to break up a collection
into two parts with roughly equal relevance properties. The first subcollection,
known as the “test collection,” is used in a relevance feedback situation to
generate a set of modified feedback queries from the originally available
queries. The second, so-called control collection, is then processed in two dif­ferent searches first against the original queries and later against the modified
queries. Recall-precision measurements are used in each case to compare therespective performance. Under experimental conditions, improvements of up
to 10 percent in precision for fixed recall levels have been noted for the modi­
fied feedback queries compared with the original ones.

244

Figure 6-11

CHAPTER 6

Test and control feedback evaluation.

D Dynamic Document SpaceIt was noted earlier that in some circumstances it becomes useful to modify not
only the query statements during the course of the retrieval process, but also
the document vectors themselves. For example, when the user population isfairly homogeneous and many queries of the same type are expected to be sub­mitted to the retrieval system, a dynamic document modification process maylead to easier retrieval of relevant documents and a more useful document
space for search purposes.
Consider, for example, the document modification system represented insimplified form in Fig. 6-12a. The process consists in modifying the documents
retrieved with respect to a given query and identified as relevant by the user so
as to render them somewhat more similar to the query that was used to retrieve
them. This can be done by adding certain query terms to the various document
vectors, or by increasing the weight of query terms that already occur in the
document vectors. By making the document vectors more similar to a common
query, they are also made more similar to each other. Hence when a new query
is submitted that resembles the original one, the modified documents become
more easily retrievable.
The document space modification process of Fig. 6-12b is an extension of
the earlier one, because documents identified as nonrelevant by the user popu­
lation are also altered in Fig. 6-12b so as to make these items less similar to theoriginal query, while at the same time, the relevant documents are moved
closer to the query as before. In each case, the idea is to perform only minor

RETRIEVAL REFINEMENTS

245

A Relevant document

Figure 6-12 Docum ent space m odifica­tion. (a) Relevant docum ent m odification,(b) Relevant and nonrelevant docum ent
m odification.

adjustments in the document vectors in response to any particular user-systeminteraction. Significant document movements will then occur only after a con­sensus has been reached among several different users concerning the useful­ness of particular items in response to a number of different queries. Following
many small individual moves of the document vectors, an equilibrium space
may eventually be produced where no major additional document alterations
occur. Such a conjecture remains to be proved [46],When the user population of the retrieval system is not sufficiently homo­
geneous, few queries may be submitted that are similar to each other. In thatcase, it may not be possible to construct an improved document space. How­ever, a document space modification method may nevertheless be useful inorder to handle document growth and retirement. In particular, when a collec­
tion grows indefinitely through the addition of new items, limitations in theavailable storage space may make it necessary to retire from the active storage
area those items that are least likely to be useful for retrieval purposes. The
problem then consists in identifying items as candidates for possible retire­
ment. A number of strategies suggest themselves for this purpose: items may
be retired if they have never been retrieved in response to earlier queries or,
having been retrieved, if they are always identified as nonrelevant to the re­spective user queries o r if they are always retrieved late in a search.
Some of the foregoing retirement strategies involve a document spaceCHAPTER 6

246

modification step, followed by the retirement of items that will have moved tothe periphery of the document space. Preliminary evaluations indicate that au­
tomatic document retirement methods can usefully be incorporated into a doc­
ument retrieval system [47].
The concept of document collection modification remains to be tried out inreal user environments. In principle, it appears natural that the relationship be­
tween items should be altered as science advances, new applications emerge forold ideas, and the use of the collection changes. On the other hand, whenchanges are introduced into the stored data, searches that are repeated periodi­
cally will not necessarily retrieve the same information as before. This loss ofstability may be disturbing to some users. Furthermore, the effort to alter the
document representations of many items of a transitory nature may hardly beworth the effort. Because of the connection between collection modification on
the one hand and collection management (growth and retirement) on the other,
the document space modification process may be expected to attract increased
attention in the future.

6

CITATION PROCESSINGA

Basic Citation Properties

The use of bibliographic references and citations in document processing has
not yet been considered. Citations and references between documents are us­
able for many types of literature studies. References and citations attached toindividual literature items may provide alternative expressions of document
content. Citation and reference counts can also be used to assess the impor­tance of individual documents or of complete document collections, by assum­
ing that citation frequencies reflect the influence of bibliographic items in a fieldof study. By extension this argument may also be applied to authors of docu­
ments or to selected groups of authors; in particular, author influence might bemeasured by using the citation frequencies of documents written by a given au­
thor. Finally, citations and references can be followed from item to item, andthe resulting “network” of papers can serve as a basis for a variety of historicstudies and for an examination of the development of individual disciplines[48-53].
A distinction must be made between bibliographic references and cita­
tions. A reference for a given document is a bibliographic item mentioned in the
bibliography of that document. Thus the phrase “A refers to B ” implies that
document B is included as an entry in the bibliography of document A. Cita­
tions between documents specify additional relationships between biblio­
graphic items. A citation is an inverse reference: when a document A refers to
document B, the latter is cited by document A. For a particular document, it isthen possible to identify a set of references obtainable by consulting the bibliog­
raphy of that document, as well as a set of citations made by other documents
to the document in question. To identify the citations it is necessary to use a

RETRIEVAL REFINEMENTS

247

Luhn

Figure 6-13

Citation terminology: Stiles

refers to Luhn, or Luhn is cited by Stiles,

i
Stiles(Luhn is contained in Stiles’s reference
list.)

citation index or, alternatively, to process the reference lists using appropriate
sort and merge operations. The dual relationship between references and cita­
tions is represented graphically in Fig. 6-13— a reference by an outgoing arrow
and a citation by an incoming arrow. When document B refers to document A,
B may be expected to postdate A; hence vertical displacement from top to bot­
tom in a citation graph represents increasing time.
The occurrence of bibliographic citations is a comparatively rare phenom­
enon. For example, about 25 percent of all published papers are never cited atall. Of the archive of citable papers in a particular field of endeavor, about one
half are not cited in any given year. Of those that are cited in a particular year,
72 percent are cited once in that year, and 18 percent are cited twice. Thus only
about 5 percent of the archive of citable papers is cited at least three times in agiven year [54], From these statistics, it is not difficult to conclude that when agiven document attracts many dozens of citations— and, of course, such
papers are not hard to find— the very rarity of the phenomenon carries signifi­
cance. A long list of studies have also shown that citation counts for papers,
journals, authors, etc., correlate highly with peer judgments concerning the im­portance and influence of documents and document authors.
*B

Main Citation Usage

In order to make use of bibliographic reference and citation data, it is first nec­
essary to collect citations for a given corpus of documents. This can be done bytaking a number of source documents and following either references or cita­
tions to new documents. These new documents can then be used as sources for
new searches that discover still other documents. Two possible search strate­
gies are represented graphically in Fig. 6-14.
The search of Fig. 6-14a is a pure citation search which uses as a source awell-known (historical) document in a given area (Luhn). A citation index isthen used to identify a number of more recent documents all of which cite
Luhn. One of these citing items (Cleverdon) is then used to produce still newer
documents which cite Cleverdon (documents Lancaster, Keen, Salton of Fig.
6-14a). The search could continue to cover many generations of documents,
thereby using connections between documents over long periods of time.
The search of Fig. 6-14b, on the other hand, covers documents that remain
more or less stationary in time. The source document (Luhn) is used as before
to uncover the citing items Stiles, Cleverdon, and Sparck Jones. One of these(Sparck Jones) is then used in a backward search by taking the references for
Sparck Jones (documents Luhn, van Rijsbergen, Harter) and obtaining further

CHAPTER 6

248
Luhn

(a)

van Rijsbergen

Luhn

StilesCleverdon

SparckJones

Robertson

HarterHarperBookstein

K raft(b)

Figure 6-14(a) Citation search forward in time, (b) Citation search forward and backward.

citations for some of these referenced items. Such a lateral search stays withina relatively narrow time frame, as opposed to the vertical search of Fig. 6-14a.
Citation and reference tracing methods of the kind illustrated in Fig. 6-14
may be used to generate complete citation networks for individual subject
areas. Such citation networks are then used as a basis for historical researchesof various kinds. A typical citation network is illustrated in Fig. 6-15, whereonce again downward displacement of the page implies increasing time.
Each reference or citation between two items represents a relationship in­
dicator for the items. However, a direct reference (item A refers to item B)
does not imply identity in the subject areas covered by the items. A stronger
indication of congruence in subject matter is furnished by the so-called biblio­
graphic coupling and cocitation counts. Two items are coupled bibliographically when they share certain references, that is, when their bibliographies con­tain various items in common. The coupling strength between two items may infact be defined as the number of references in common for both items [55,56].
One may expect that when the coupling strength between documents is suffi­
ciently large, the subject matter of the items exhibits strong similarities.
Two documents may also be related by common citation patterns fromother documents. In particular, a cocitation link is said to relate two items
when these items are jointly cited by a third document. The number of cocita­
tions for two documents, that is, the number of documents that jointly cite thetwo items, is believed to be more significant than the bibliographic couplingstrength in pointing to subject matter similarities. Cocitations have thus been
widely used to study the development of individual fields of science as well as

RETRIEVAL REFINEMENTS249

the structure of science as a whole [57-59]. Figure 6-16 presents a sample con­tour map in which individual documents are grouped, based in part on thestrength of their cocitation links. In particular, the diameter of the circles
around each document is related to the total number of citations attracted by!
the documents and hence to the importance of the documents. The distance
between two documents, on the other hand, is inversely related to the cocita­tion strength between them, that is, the closer the items in the map, the higher

Figure 6-16 Typical contour map basedon cocitations.

250

CHAPTER 6

the number of cocitations between them. Maps such as that of Fig. 6-16 havebeen constructed at different periods in time for certain subject areas thereby
describing the development of a given field of study [50,59].
If citations and references attached to documents carry subject signifi­
cance, it appears reasonable to use them for content representation in addition
to, or instead of, the normal index terms. In particular, if the citation and refer­ence patterns are known for a collection of documents, a particular document
could be represented by a bibliographic attribute vector of the form
DOC,

(Tii)Ti2> • • • Tin ,C[x ,C[2 , . . . ,C]m)(16)

where ry is an identifier representing the jth reference attached to DOQ and cik
the kth citation to the document. The normal vector similarity computations
between pairs of documents or between queries and documents, can then be
performed using the standard term vectors or alternatively, the bibliographic
attribute vectors of expression (16). The two vector forms can also be com­bined by adding the bibliographic information to the normal index terms.
Studies in which bibliographic indicators have replaced the standard terms
and keywords for content identification have shown that bibliographic indica­
tors represent more specific content identifications than normal keywords [55,60,61]. Furthermore, precision improvements have been noted in searches car­ried out with bibliographic vectors replacing the normal term vectors [62]. In
some retrieval environments the bibliographic identifiers may be immediately
available as a by-product of the computer composition of the documents,
whereas the terms and keywords might have to be generated by a more or lesscomplicated indexing process. One may expect an increased utilization of bibli­
ographic data for retrieval purposes in the immediate future [63].
7SUMMARY

The standard information retrieval operations may be refined by using sophisti­
cated automatic indexing methods that are capable of assigning weighted, in­stead of binary, terms to the documents of a collection. The term weights may
be based on the term occurrence characteristics in the documents of a collec­
tion— for example, terms occurring mostly in documents identified as relevantto the user queries may receive higher weights than terms occurring in thenonrelevant documents.
Improved search efficiency may be obtained by clustering the document
collection and placing into common classes all documents that appear to be suf­
ficiently similar to each other. Various automatic classification methods areavailable for this purpose, and efficient top-down or bottom-up cluster searchmethods have been devised.
T h e m a n ip u la tio n o f w e ig h te d q u e r y a n d d o c u m e n t te r m s a ls o le a d s tom e th o d s fo r g e n e r a tin g im p r o v e d q u e r y s ta te m e n ts b a s e d o n in fo r m a tio n Ob­
ta in e d fro m th e u s e r p o p u la tio n in th e c o u r s e o f th e r e tr ie v a l O p era tio n s. T h e

RETRIEVAL REFINEMENTS

251

relevance feedback operations have been shown experimentally to lead to sub­stantial improvements in retrieval effectiveness. Relevance information ob­
tained from the users about the importance of certain documents in the collec­
tion can also lead to improvements in the document descriptions themselves,
and to modern collection management strategies capable of accommodating
growing or shrinking document collections. Furthermore, relevance data areneeded for the construction of improved term weighting measures: indeed therelevance feedback process represents an obvious possibility for the estimationof the term relevance factor. Finally, relevance information may be used togenerate trial or starting clusters in various heuristic clustering systems.
Improvements in search and retrieval performance may be obtainable byincorporating bibliographic citations instead of only content terms in the docu­
ment descriptions. There are indications that at a time when document texts are
increasingly available in machine-readable form, the latter possibility may beespecially attractive.
REFERENCES[1] G. Salton, A utom atic Inform ation Organization and R etrieval, M cGraw-H ill B ook
C om pany, N e w Y ork, 1968.
[2] C .J. van R ijsbergen, Information R etrieval, 2nd E dition, Butterw orths, L ondon,
1979.
[3] H .E . S tiles, T he A ssociation Factor in Information R etrieval, Journal o f the A CM ,V ol. 8, N o . 2, April 1961, pp. 2 7 1 -2 7 9 .
[4] M .E . Maron and J.L . K uhns, On R elevan ce, Probabilistic Indexing and Informa­tion R etrieval, Journal o f the A C M , V ol. 7, N o . 3, July 1960, pp. 21 6 -2 4 4 .
[5] W .B . Croft, Organizing and Searching Large F iles o f D ocu m en t D escriptions, D o c ­toral T h esis, U n iversity o f Cambridge (England), 1978.
[6] H . Wu and G. Salton, A Term W eighting M odel B ased on U tility T heory, in Infor­
mation R etrieval R esearch, R .N . O ddy, S .E . R obertson, C.J. van Rijsbergen and
P.W . W illiam s, editors, B utterw orths, L ondon, 1981, pp. 9 -2 2 .
[7] C .T . Y u, K . Lam , and G. Salton, Term W eighting in Information Retrieval U sing
the Term Precision M odel, Journal o f the A C M , V ol. 29, N o . 1, January 1982,
pp. 152-170.
[8] A . B ook stein , F u zzy R equests: A n A pproach to W eighted B oolean Searches, Jour­nal o f the A S IS , V ol. 31, N o . 4, July 1980, pp. 24 0 -2 4 7 .
[9] A . B ook stein , On the Perils o f M erging B oolean and W eighted Retrieval S ystem s,
Journal o f the A S IS , V o l. 29, N o . 3, M ay 1978, pp. 156-158.
pp. 156-158.
[10] W. Goffm an, A n Indirect M ethod o f Information R etrieval, Information Storageand R etrieval, V ol. 4 , N o . 4, D ecem b er 1968, pp. 36 1 -3 7 3 .
[11] N . Jardine and R. Sibson, A M odel for T axonom y, M athem atical B io scien ces, V ol.
2, N o . 2 - 3 , M ay 1968, pp. 4 6 5 -4 8 2 .
[12] K . Sparck Jones, Som e Thoughts on C lassification for R etrieval, Journal o f D o cu ­m entation, V ol. 26, N o . 2, June 1970, pp. 8 9 -1 0 1 .
[13] G. Salton, D ynam ic Information and Library P rocessing, Prentice-H all, In c., E n­
glew ood C liffs, N e w Jersey, 1975.

252

CHAPTER 6[14] W .B . Croft, A M odel o f Cluster Searching B ased on C lassification, Information
System s, V ol. 5, N o . 3, 1980, pp. 189-195.
[15] G. Salton, C luster Search Strategies and the Optim ization o f Retrieval E ffectiv e­n ess, in The Smart Retrieval S ystem , G. Salton, editor, Prentice-H all, In c., E n gle­
w ood C liffs, N e w Jersey, 1971, Chapter 10.
[16] R .T. Grauer and M . M essier, A n E valuation o f R o cch io ’s Clustering A lgorithm , inT he Smart Retrieval S y stem , G. Salton, editor, Prentice-H all, In c., E nglew ood
C liffs, N e w Jersey, 1971, Chapter 11.
[17] R .T . D attola, E xperim ents with a F ast Algorithm for A utom atic C lassification, in
The Smart R etrieval S ystem , G. Salton, editor, Prentice-H all, In c ., E n glew ood
C liffs, N e w Jersey, 1971, Chapter 12.
[18] G. Salton and H . W u, A C om parison o f Inverted F ile Searching with Cluster Tree
Search O perations, T echnical R eport, Computer S cien ce Departm ent, Cornell U n i­
versity, Ithaca, N e w Y ork, 1981.

[19] C.W. Cleverdon and E.M. Keen, Factors Determining the Performance of Indexing
Systems, Aslib Cranfield Research Project, Volumes 1 and 2, Cranfield (England),1968.
[20] G. Salton and M .E . L esk , Computer E valuation o f Indexing and T ext P rocessing,
Journal o f the A C M , V ol. 15, N o . 1, January 1968, pp. 8 -3 6 .
[21] V .E . Giuliano and P .E . Jones, Linear A sso cia tiv e Inform ation R etrieval, in V istas
in Information H andling, P. H ow erton , editor, Spartan B o o k s, R och elle Park, N e w
Jersey, 1963.
[22] B. L itofsky, U tility o f A utom atic C lassification S ystem s for Information Storageand R etrieval, P h .D . dissertation, U n iversity o f P ennsylvania, Philadelphia, P en n ­sylvania, 1969.
[23] A .R . M eetham , Graph Separability and W ord Grouping, Proceedings o f 1966 ACM
N ational C onference, A ssociation for Computing M achinery, N e w Y ork, 1966, pp.
513-514.
[24] K . Sparck Jon es, A utom atic K eyw ord C lassification for Inform ation R etrieval,
B utterw orths, L ondon, 1971.
[25] G. Salton, E xperim ents in A utom atic Thesaurus C onstruction for Information R e­trieval, Inform ation Processing-71, N orth H olland Publishing C om pany, A m ster­dam, 1972, pp. 115-123.
[26] P .K .T . V asw ani and J.B . C am eron, T he N P L E xperim ents in Statistical Word A s­sociations and Their U se in D ocu m en t Indexing and R etrieval, Computer S cien ce
R eport N o . 42, N ational Physical Laboratory, T eddington, England, April 1970.
[27] R. Attar and A .S . Fraenkel, L ocal F eedback in Full-T ext R etrieval S ystem s, Jour­nal o f the A C M , V ol. 24, N o . 3, July 1977, pp. 3 9 7 -4 1 7 .
[28] D .M . Jackson, T he C onstruction o f R etrieval Environm ents and P seudoclassifica­tion B ased on E xternal R elevan ce, Inform ation Storage and R etrieval, V ol. 6, N o .
2, June 1970, pp. 187-219.
[29] C .T. Y u, A Form al C onstruction o f Term C lasses, Journal o f the A C M , V ol. 22,
N o . 1, January 1975, pp. 17 -3 7 .
[30] C .T. Y u, A M ethodology for the C onstruction o f Term C la sses, Information Stor­
age and R etrieval, V ol. 10, N o s. 7/8, July/August 1974, pp. 2 4 3 -2 5 1 .
[31] C .T. Yu and V .V . Raghavan, Single-P ass M ethod for Determ ining the Sem antic R e­lationship betw een T erm s, Journal o f the A S IS , V ol. 28, N o . 5, N o v em b er 1977,
pp. 3 4 5 -3 5 4 .
[32] V .V . Raghavan and C .T. Y u, E xperim ents on the D eterm ination o f the R elation-

RETRIEVAL REFINEMENTS

253

ships betw een T erm s, Proceedings o f First Annual SIGIR C onference, A ssociation
for Computing M achinery, N e w Y ork, M ay 1978, p. 150.
[33] M .E . L esk and G. Salton, Interactive Search and R etrieval M ethods U sin g A u to ­m atic Inform ation D isp lays, A FIPS C onference P roceedings, V ol. 34, M ontvale,N e w Jersey, 1969, pp. 4 3 5 -4 4 6 .
[34] R .N . O ddy, Inform ation Retrieval through M an-M achine D ialogue, Journal o f D o c ­um entation, V ol. 33, N o . 1, M arch 1977, pp. 1 -1 4 .
[35] C. V ernim b, A utom atic Query A djustm ent in D ocum ent R etrieval, Information
P rocessing and M anagem ent, V o l. 13, N o . 6 , 1977, pp. 3 3 9 -3 5 3 .
[36] J.H . W illiam s, Jr., F unctions o f a M an-M achine Interactive Information Retrieval
S ystem , Journal o f the A S IS , V ol. 22, N o . 5, S ep tem b er-O ctob er 1971, pp. 311—
317.
[37] P.C . M itchell, J.T . Rickman, and W .E . W alden, S O L A R — A Storage and O n-Line
A utom atic Retrieval S y stem , Journal o f the A S IS , V ol. 25, N o . 5, S ep tem b erO ctober 1973, pp. 3 4 7 -3 5 8 .
[38] J.J. R occh io, Jr., R elevan ce F eed b ack in Information R etrieval, in The Smart R e­trieval S y stem — E xperim ents in A utom atic D ocum ent P rocessing, G. Salton, ed i­tor, Prentice-H all, In c ., E n glew ood Cliffs, N e w Jersey, 1971, Chapter 14.
[39] G. Salton, R elevan ce F eedback and the Optimization o f R etrieval E ffectiv en ess, inT he Smart Retrieval S y ste m — E xperim ents in A utom atic D ocum ent P rocessing, G.
Salton, editor, Prentice-H all, In c., E n glew ood Cliffs, N e w Jersey, 1971, Chapter
15.
[40] J.J. R occh io, Jr., D ocum ent R etrieval S y ste m s— Optim ization and E valuation, R e­
port ISR -10 to the N ational S cien ce Foundation, Harvard C om putation Laboratory,
Cambridge, M assach u setts, M arch 1966.
[41] E. Ide, N e w E xperim ents in R elevan ce Feedback, in The Smart Retrieval S ystem ,G. Salton, editor, Prentice-H all, In c ., E n glew ood C liffs, N e w Jersey, 1971, Chapter
16.
[42] E. Ide and G. Salton, Interactive Search Strategies and D ynam ic File Organization,in T he Smart R etrieval S ystem , G. Salton, editor, Prentice-H all In c., E n glew ood
C liffs, N e w Jersey, 1971, Chapter 18.
[43] J. K elly, N eg a tiv e R esp on se R elevan ce Feedback, in T he Smart Retrieval S ystem ,G. Salton, editor, Prentice-H all In c ., E n glew ood C liffs, N e w Jersey, 1971, Chapter

20 .
[44] A . B orodin, L . Kerr, and F. L ew is, Query Splitting in R elevan ce F eedback S y s­
tem s, in T he Smart Retrieval S ystem , G. Salton, editor, Prentice-H all In c., E n gle­
w ood C liffs, N e w Jersey, 1971, Chapter 19.
[45] Y .K . Chang, C. Cirillo, and J. R azon, E valuation o f F eedback R etrieval U sin g M od­
ified Freezing, R esidual C ollection s, and T est and Control Groups, in T he Smart
Retrieval S ystem , G. Salton, editor, Prentice-H all, In c., E nglew ood Cliffs, N ew
Jersey, 1971, Chapter 17.
[46] T .L . Brauen, D ocu m en t V ector M odification, in The Smart R etrieval S y stem — E x ­perim ents in A utom atic D ocum ent P rocessing, G. Salton, editor, Prentice-H all,In c., E nglew ood C liffs, N e w Jersey, 1971, Chapter 24.

[47] K. Sardana, Automatic Document Retirement Algorithms, Scientific Report No.
22, Section 12, Computer Science Department, Cornell University, Ithaca, New
York, 1974.
[48] E. Garfield, C itation Indexing— Its T heory and A pplications in S cien ce, T ech n ol­
ogy and H um anities, John W iley and S o n s, N e w Y ork, 1979.

254

CHAPTER 6[49] D .J. deS olla Price, N etw ork s o f Scientific Papers, S cien ce, V ol. 149, N o . 3683,
1965, pp. 5 1 0 -5 1 5 .
[50] E. Garfield, Citation M easures as an O bjective Estim ate o f Creativity, Current C on­
tents, N o . 34, A ugust 16, 1970, pp. 4 - 5 .
[51] J.R. C ole and S. C ole, The Ortega H y p o th esis, S cien ce, V ol. 178, N o . 4059, O cto­ber 27, 1972, pp. 3 6 8 -3 7 5 .
[52] E. Garfield, Citation A nalysis as a T ool in Journal E valuation, S cien ce, V ol. 178,
N o . 4060, N ovem b er 3, 1972, pp. 4 7 1 -4 7 9 .
[53] J.H . W estbrook, Identifying Significant R esearch, S cien ce, V ol. 132, N o . 3435, O c­tober 18, 1960, pp. 1229-1234.
[54] D .J. deSolla Price, The Citation C ycle, in K ey Papers in Inform ation S cien ce, B. C.
Griffith, editor, K n ow led ge Industry Publications In c., W hite Plains, N e w Y ork,
1980, pp. 195-210.
[55] M .M . K essler, Com parison o f R esults o f Bibliographic Coupling and A nalytic Sub­je c t Indexing, A m erican D ocum entation, V ol. 16, N o . 3, July 1965, pp. 2 2 3 -2 3 3 .
[56] M .M . K essler, Bibliographic Coupling b etw een Scientific Papers, A m erican D o cu ­m entation, V ol. 14, N o . 1, January 1963, pp. 10 -2 5 .
[57] E. Garfield, ISI Is Studying the Structure o f S cien ce through C ocitatioii A n alysis,
Current C onten ts, N o . 7, February 13, 1974, pp. 5 -1 0 .
[58] H . Small and B .C . Griffith, The Structure o f Scientific Literature, I. Identifying andGraphing S pecialties, S cien ce S tu d ies, V ol. 4 , 1974, pp. 1 7 -4 0 .
[59] H . Small, C o-citation in the Scientific Literature: A N e w M easure o f the R elation­
ship b etw een T w o D ocu m en ts, Journal o f the A S IS , V ol. 24, N o . 4, J u ly -A u g u st
1973, pp. 2 6 5 -2 69 .
[60] E. Garfield, S cien ce Citation In d ex — A N e w D im ension in Indexing, S cien ce, V ol.
144, N o . 3619, M ay 8, 1964, pp. 6 4 9 -6 5 4 .
[61] E. Garfield, T he Citation Index as a Subject Index, Current C ontents, N o . 18, M ay
1, 1974, pp. 5 - 7 .
[62] G. Salton, A utom atic Indexing U sin g Bibliographic C itations, Journal o f D ocu m en ­tation, V ol. 27, N o . 2, June 1971, pp. 9 8 -1 1 0 .
[63] E. Garfield, IS I’s O n-Line System M akes Searching So E a sy E ven a Scientist Can
D o It: Introducing M E T A D E X A utom atic Indexing and ISI/B IO M E D Search, Cur­rent C ontents, N o . 4, January 26, 1981, pp. 5 -8 .

BIBLIOGRAPHIC REMARKS

Additional coverage of query formulation and query modification in informa­tion retrieval is provided by
H .S . H eap s, Inform ation R etrieval— C om putational and T heoretical A sp ects, A c a ­dem ic P ress, N e w Y ork, 1978.
G. Salton, D ynam ic Information and Library P rocessing, P rentice-H all, In c., E n gle­
w ood C liffs, N e w Jersey, 1975.

Clustering algorithms are examined in many texts. The second reference
below (Hartigan) provides actual computer programs for several clustering
methods and the third (Sparck Jones) specializes in term classification

255

RETRIEVAL REFINEMENTS

P .H .A . Sneath and R .R . Sokal, N um erical Taxonom y: T he Principles and Practice o f
N um erical C lassification, W . H . Freem an, San F rancisco, California, 1973.
J. A . Hartigan, Clustering A lgorithm s, John W iley and S on s, N e w Y ork, 1975.
K . Sparck Jones, A utom atic K eyw ord C lassification for Inform ation R etrieval, Butterw orths, L ondon, 1971.

A thorough coverage of citation processing is provided by
E. Garfield, Citation Indexing— Its T heory and A pplications in S cien ce, T echnology andH um anities, John W iley and S o n s, N e w Y ork, 1979.

EXERCISES
6-1

Consider the follow in g similarity matrix b etw een objects

1
2
3
4
5
6
7
8
9

a

6-3

6-4

2

3

4

5

6

7

8

9

0
0
1
0
1
1
1
0
0

0
0
0
0
0
0
0
0
1

1
0
0
0
1
0
1
0
0

0
0
0
0
0
1
0
1
0

1
0
1
0
0
0
0
0
0

1
0
0
1
0
0
0
1
0

1
0
1
0
0
0
0
0
0

0
0
0
1
0
1
0
0
0

0
1
0
0
0
0
0
.0
0

Find all the cliq u es,
Find all the con n ected com ponents.
c State the algorithm used to determ ine the clusters using a single-link m ethod,d G ive a list o f desirable clustering properties for a docum ent collection leading toan effective and/or efficient retrieval system . U nder w hat circum stances w ould
it be preferable to u se cliques rather than connected com ponents to search acollection o f ob jects, and v ice versa? W hat are the tradeoffs b etw een the tw om ethods?
e D o the cliques listed under part a exhibit the desirable properties listed underpart d? Sam e question for the con n ected com ponents listed under part b. If not,h ow could the cliques or the con n ected com ponents be modified to produce
an im proved classification?
What is the main idea behind the pseudoclassification process? W hat are the differ­en ces betw een a standard term classification and the notion o f pseudoclassifica­tion? W ould you ex p ect the results o f a pseudoclassification to remain unchanged
w hen the user population o f a retrieval system changes?
H ow can a citation index be used in retrieval? Suppose the cocitation strength w ere
available for all docum ent pairs in a collection o f docum ents. H o w could that fact
be utilized to design an effective retrieval service? A re there obvious similaritiesb etw een the u se o f citations and the u se o f pseudoclassification in retrieval?
Consider the docum ent output obtained for a given query by an initial search and a
feedback search based on user relevance assessm en ts for the top three retrieved
item s.

b

6-2

1

256

CHAPTER 6

Initial search
Rank

Document
number

1
2
3

680
425
430

4
5

129
320

Initially
retrieved

Feedback search
Relevant

Document
numberRelevant

425
430
129

X

X

X

680
529

X

a

6-5

C om pute the recall-precision pairs follow ing the retrieval o f each docum ent for
both searches.
b Are the differences in recall-precision m easures reflective o f the im provem ents
actually obtained b y the feed b ack process?
c D esign a feed b ack evaluation system w hich em phasizes the retrieval o f relevant
item s not previously seen by the user.
d U s e the sam ple search to com pare the n ew feedback evaluation derived underpart c with the original evaluation under part a.
C onsider the follow ing docum ent collection indexed by three term s A , B , and C:

A
B
C
a

D,

d2

D3

D„

d5

1
1
0

0
1
1

1
0
0

0
0
1

1
1
0

Exhibit the docum ents retrieved by the follow ing queries(A OR B ) A N D C(A A N D B) OR C
A NOT Bb

H o w m any docum ents w ould you exp ect to retrieve using the follow ing
w eighted B oolean queries for the sam ple collection?
OR B 0.66
A N D B 0 66
A 0.33 N O T B 0 50
A o.33

A o.33c

D o any com m on docum ents appear in the resp on ses to the three w eighted B o o l­ean queries o f part b? Carefully explain your reasoning.