Chapter 4

The SMART and SIRE
Experimental Retrieval
Systems0

PREVIEW

This chapter deals with analysis, file organization, search, and retrieval metho­
dologies that may be used with the advanced information retrieval systems of
the future. The SMART system is perhaps the best known of the experimental
systems that are not based on a standard inverted file technology. The SMART
system design is described in detail in this chapter, including the automatic in­dexing methods, the clustered file organization, which collects related records
into common classes; and the interactive search process which is used to con­struct improved query formulations based on relevance information suppliedby the users to the system.
Various other experimental retrieval systems, including SIRE, also utilize
novel features that are not common in conventional retrieval. Some of these
extensions are examined at the end of this chapter. The use of local clustering
methods and the incorporation of weighted terms in Boolean retrieval are con­sidered in this connection together with additional user feedback and query re­formulation methods.
1 INTRODUCTION

Conventional retrieval systems are based for the most part on a common set ofprinciples and methodologies. The documents are normally indexed manually118

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

119

by subject experts or professional indexers using a prespecified, controlled vo­
cabulary; alternatively, some systems use the words included in document
texts or text excerpts as index terms. Users or search intermediaries formulate
search statements using terms from the accepted vocabulary together with ap­
propriate Boolean operators between terms. The main file search device is an
auxiliary, so-called inverted directory which contains for each accepted con­tent identifier and for some of the objective terms a list of the document refer­ences, or markers, to which that term has been assigned. In a free text searchsystem, the inverted directory contains the text words from the documents andthe references to all documents containing each given word. The documents tobe retrieved in response to a given search request are then identified by obtain­
ing from the inverted directory the document reference lists corresponding toeach query term, and performing appropriate list comparison and merging op­
erations in accordance with the logical search term associations contained in
the query statements. An exact match retrieval strategy is used which consistsof retrieving all items whose content description contains the term combination
specified in the search requests. Furthermore, all retrieved items are consid­
ered by the system to be equally relevant to the user’s needs, and normally no
special methods are provided for ranking the output items in presumed order ofgoodness for the user.
The existing methodology has certain obvious advantages. In some cases,
the indexers and search intermediaries may become expert in assigning usefulcontent indicators to the stored documents and incoming user queries. The re­trieval system will then exhibit a high level of effectiveness. The inverted filedesign also produces rapid response times, because the inverted file manipu­
lations will identify all matching documents before the main document file isever used. The document file must then be accessed only for those documents
which will be shown to the user in response to. the query.
The benefits of the conventional retrieval designs are available only under
special circumstances, however. In particular, when the indexing and search
operations are not carried out consistently by the several intermediaries, theeffectiveness of the retrieval operations will suffer. If, for example, one indexer
uses “ search” when another would use “ retrieval,” some documents may not
be retrieved when wanted. The use of controlled vocabulary lists can minimize
this problem, but cannot eliminate it. In practice, the required degree of index­
ing consistency cannot be guaranteed when similar information items aretreated by different indexers and searchers. In such circumstances, the various
documents pertaining to a common subject area may be identified very dif­ferently, and many of these items may not be retrievable when wanted.
The inverted directory of index terms is most useful in situations where thesearch vocabulary remains static over long periods of time and is limited to a
relatively small number of terms. In such cases, the directory size will remain
manageable and relatively little updating may be needed. In practice, the index­
ing vocabulary is often large, consisting of several tens of thousands of terms
for each subject area, and the vocabulary is not stable. The inverted directories

120

CHAPTER 4

to be stored may then become very large, and these directories must be kept up
to date when new documents are added to the file or new vocabulary terms are
introduced.
The customary library file organization which places in related or adjacent
file positions all items that exhibit similar subject content is not followed by theexisting inverted file systems. Instead, the main document file is often kept inarbitrary order, and it becomes difficult, given the location of a particular useful
document, to determine the location of other related documents. This compli­
cates the file search process, which ideally consists in locating certain useful
items, and then proceeding from there to identify additional items resembling
the ones found earlier. For the same reason, the inverted file strategy is not well
suited to the processing of approximate queries designed to approach a given
subject area in small steps, and to the kind of browsing which proves so usefulin conventional libraries. Instead, it becomes necessary to formulate complete
and specific queries, in the hope of retrieving the entire set of relevant items
from the start.
The standard inverted file technology is difficult to change because of thelarge investments already made in the existing commercial systems. Neverthe­less, substantial improvements are possible in the operations of the conven­tional systems. Thus, in some partly experimental systems, term weighting fa­
cilities have been superimposed on the standard Boolean query formulations
and inverted file search procedures, leading to the ranking of retrieved docu­
ments in accordance with the weights of the matching query and document
terms. This makes it possible to present the retrieved documents to the user indecreasing order of the sum of certain term weights. Presumably the user willfind it easier to prepare improved query formulations when the items judged by
the system to be most relevant are retrieved ahead of other more marginalitems.
Systems have also been developed that are based on totally new concep­
tions of the retrieval task. One of the best known of these, the SMART system,
is described in the remainder of this chapter together with certain other non­standard retrieval system designs.

2

THE SMART SYSTEM ENVIRONMENT*A

Vector Representation and Similarity Computation

The SMART system distinguishes itself from more conventional retrieval sys­
tems in the following important respects: (1) it uses fully automatic indexing
methods to assign content identifiers to documents and search requests; (2) itcollects related documents into common subject classes, making it possible tostart with specific items in a particular subject area and to find related items inneighboring subject fields; (3) it identifies the documents to be retrieved by per­forming similarity computations between stored items and incoming queries,
and by ranking the retrieved items in decreasing order of their similarity with
the query; and finally, (4) it includes automatic procedures for producing im-

121

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMSTERM ,TERM 2

TERM ,DOC,

T E R M ,,t e r m ,2

T E R M ,,D0C2

t e r m 2,

t e r m 22

T E R M 2,

□0Cn

_ T E R M n,

T E R M n2.. .

T E R M „ ,_Figure 4-1

T e rma s s ig n m e n t

a rra y(nd o c u m e n ts , t te rm s ).

proved search statements based on information obtained as a result of earlier
retrieval operations [1,2,3,4].
In the SMART system each record, or document, is represented by a vec­
tor of terms. That is, a particular document, DOC,, is identified by a collectionof terms TERM ,!, TERMi2, . . . , TERMit, where TERM;j is assumed to rep­resent the weight, or importance, of term j assigned to document i. By “ term ” ismeant some form of content identifier, such as a word extracted from a docu­
ment text, a word phrase, or an entry from a term thesaurus. A given document
collection may then be represented as an array, or matrix, of terms where eachrow of the matrix represents a document and each column represents the as­signment of a specific term to the documents of the collection. A sample term
assignment array is shown in Fig. 4-1. In the SMART system, positive term
weights are chosen for terms actually assigned to the documents (that is, TERMU
is a positive number when term j actually occurs in document i); and TERM Uis
set equal to zero when term j is not present as an identifier of document i.
A particular query, say QUERY,, can be similarly identified as a vector
QTERM jj , QTERMj2,
QTERMjt, where QTERMjk represents theweight, or importance, of term k assigned to query j. Instead of insisting
on a complete match between all nonzero query and document terms before adocument is retrieved by the system, the retrieval of a stored item can be madeto depend on the magnitude of a similarity computation measuring the simi­
larity between a particular document vector and a particular query vector as afunction of the magnitudes of the matching terms in the respective vectors. A
similarity measure often used with the SMART system is the cosine measure,defined as

2 (TERMlk • QTERMjk)
COSINE(DOCi,QUERYj) =t k=1
t ....
V 2 (TERM*)2 • X (QTERMjk)2
k=l

(1)

k=l

The cosine correlation measures the cosine of the angle between docu­
ments, or between queries and documents, when these are viewed as vectors in
the multidimensional term space of dimension t. In three dimensions, when
only three terms identify the documents, the situation may be represented by
the configuration of Fig. 4-2. Each axis corresponds to a different term, and theposition of each document vector in the space is determined by the magnitude

122

CHAPTER 4

TERM,

Figure 4-2

Vector representation of docum ent space.

(weight) of the terms in that vector. The similarity between any two vectors isthen represented as a function inversely related to the angle between them.
That is, when two document vectors are exactly the same, the corresponding
vectors are superimposed and the angle between them is zero.
The numerator of the cosine coefficient gives the sum of the matchingterms between DOC, and QUERY, when the indexing is binary, that is, when
TERMjk is assumed equal to 1 whenever term k actually occurs in document i.
When the indexing is not binary, the numerator represents the sum of the prod­
ucts of the term weights for the matching query and document terms. The de­nominator acts as a normalizing factor (by dividing the expression by the prod­
uct of the lengths of the query and document vectors). This implies that each
item is represented by a vector of equal length. If the angle between vectors issmall and the normalized vectors are used, the cosine of the angle between thevectors may also be approximated by the distance between the tips of the cor­
responding vectors.
When a numeric measure of similarity is used for documents and queries,
it is no longer necessary to retrieve all documents that exactly contain all thequery terms. Instead the retrieval of a document can be made to depend on aparticular threshold in the similarity measure or on a specific number of items
to be retrieved. Assuming, for example, that a threshold of 0.50 is used, allitems are retrieved for which the value of expression (1) is greater than or equal
to 0.50; alternatively the top n items may be retrieved, where n is the number of
items originally wanted. The retrieved documents may be conveniently pre­sented to the user in decreasing order of their similarity values with the respec­tive search requests. This is of special importance in an interactive retrieval
situation where users are directly tied into the retrieval system, because new
improved query formulations can then be constructed by utilizing information

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

123

extracted from previously retrieved documents. Since the first few documents
retrieved in response to a search request are those exhibiting the greatest
query-document similarity, they are also the ones most likely to be relevant tothe users’ information needs. Hence they may be most important for query re­formulation purposes.
*B

Vector Manipulation

The query reformulation process incorporated into the SMART retrieval sys­
tem is known as “ relevance feedback” because relevance assessments sup­plied by the users for previously retrieved documents are returned to the sys­
tem and used to construct new query vectors. The reformulated queries canthen be compared with the stored documents in a new search operation. The
aim is to construct new queries exhibiting a greater degree of similarity with the
documents previously identified as relevant by the user than the originalqueries; at the same time, the new queries are expected to be less similar to the
documents identified as nonrelevant by the user than the originals. The as­
sumption is that the reformulated queries will retrieve more items resembling
the relevant ones previously retrieved, and fewer items resembling the nonrele­vant ones.
The query reformulation process is then based on the following comple­
mentary operations:
1 Terms that occur in documents previously identified as relevant by theuser population are added to the original query vectors, or alternatively theweight of such terms is increased by an appropriate factor in constructing
the new query statements.
2 At the same time, terms occurring in documents previously identified
as nonrelevant by the users are deleted from the original query statements, orthe weight of such terms is appropriately reduced.
Obviously, the query reformulation process can be carried out automatically by
the retrieval system, given only an indication of relevance or nonrelevance of
certain previously retrieved items obtained from the user population.
The effect of the relevance feedback operation is represented in the illus­
tration of Fig. 4-3. In Fig. 4-3 and the related diagrams that follow, each docu­
ment is identified by a point representing the tip of the corresponding vector,
and the distance between two points is assumed to be inversely related to therespective cosine similarities between the vectors. Thus when two points ap­
pear close together in the space of Fig. 4-3, a substantial similarity exists be­
tween the vectors; the reverse is true for two points that appear far apart in thespace. In Fig. 4-3, an original query vector (represented by an open triangle)
appears with three retrieved documents of which one was identified as nonrele­vant and two as relevant. Following the previously mentioned changes in theoriginal query, a new query (the closed triangle) is constructed which appears
shifted in the space: the distance to the relevant items is now smaller than be-124

Figure 4-3

CHAPTER 4xdocument identified
as nonrelevantodocument identified
as relevantA

original query

A

reformulated query

Relevance feedback illustration.

fore, and the distance to the nonrelevant one has increased. The relevance
feedback process can be repeated several times in the hope of eventually ob­
taining adequate search output.
The cosine coefficient was introduced earlier to obtain a measure of simi­
larity between a query vector and the various documents in a collection. The
same measure also lends itself to the determination of similarities between pairsof documents. Thus, given the term vectors for two documents, DOCj andDOCj, the similarity between them may be defined as
2(TERM* • TERM *)(2)

By determining the similarity between various pairs of documents, it now be­comes possible to construct a clustered document file, consisting of classes orclusters of documents such that the documents within a given class exhibit sub­stantial similarities with each other. A clustered file resembles in concept thenormal classified document arrangement used in conventional library situa­
tions, where items dealing with related subject areas are placed together in acommon subject class. The clusters are, however, derived automatically andthe construction method may be adapted to the particular collection environ­ment under consideration. Thus, it is possible automatically to construct clus­
tered files incorporating a large number of small clusters or a small number oflarge clusters; the classes may also overlap in the sense that certain documents
may appear in more than one class. This last feature represents a substantial
advantage over conventional library classification systems.

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS•

Figure 4-4

125

centroid vector

Sample clustered docum ent collection.

A clustered document file is represented schematically in Fig. 4-4, where
each x represents a document vector, and the distance between two particularx ’s is again assumed inversely proportional to their similarity. The large circulargroupings in the figure identify the document clusters. It may be seen that someoverlap exists between the clusters: certain documents located near the periph­
ery of some classes actually appear in several classes. In order to render possi­
ble the manipulation of a clustered collection, it is convenient to use a specialclass vector, or centroid, to represent a given cluster. The centroids are similar
to the centers of gravity of a set of points, and are represented by heavy dots in
the illustration of Fig. 4-4. Given a set of m documents constituting a certain
document class p, a given centroid vector CENTROIDp = CTERMpl,
CTERMp2, . . . , CTERMpt may be computed as the mathematical average ofthe document vectors included in the pth class. Thus, following the model usedin the previous chapter for the construction of term classes, the weight of termk in the centroid for class p can be computed as the average of the weight ofterm k in all m document vectors incorporated into class p. That is,
1 m
CTERMpk = — X TERMlk
m

(3)

i= l

where the summation covers the m documents of class p.
Given a clustered collection of the type shown in Fig. 4-4, a document
search is now carried out in two main steps. Each query is first compared withthe various centroid vectors by computing the corresponding centroid-query
similarity coefficients. For classes whose centroids exhibit a sufficiently highsimilarity with the query, the individual documents are next compared with thequery, using the formula of expression (1), and documents showing sufficiently
high similarities with the query are retrieved for the user’s attention. Assumingthat n documents exist in a collection which is divided into x clusters each con-

126

CHAPTER 4

taining approximately n/x documents, the number of vector comparisonsneeded to compare a query with the best cluster is x + n/x (instead of the ncomparisons needed in an unclustered file). The number of needed vector com­
parisons is minimized when the number of clusters x equals V n .
For large collections involving many heterogeneous documents, a great
many clusters may need to be defined. In that case, the number of required
query-centroid comparisons may become excessively large. The search effi­
ciency may then be increased by taking the set of centroids and applying theclustering methodology previously used for the document vectors to compare
pairs of centroid vectors. Centroids that are sufficiently similar are thengrouped into superclasses identified by supercentroids, as shown in Fig. 4-5,
where two superclasses are represented. The file search now requires threesteps: first a comparison of the query with the supercentroid vectors; then forsome supercentroids, a comparison with the individual centroids included in
the corresponding superclusters; finally, for certain centroids, a comparison
with the individual document vectors located in the respective document clus­
ters.
The clustered file organization is adaptable to a growing collection en­
vironment, because new incoming documents can be treated just like incoming
queries. The new items are compared with the existing supercentroids and cen­troids, and eventually they are included in those clusters for which the docu­
ment-cluster similarity is sufficiently large. As in the standard inverted file or­
ganization, two distinct files are needed for the file search process:
1 The main document file, arranged in order by clusters such that allitems included in a common cluster are retrievable in a single access to themain file
2 The auxiliary file of cluster centroids, and supercentroids arranged in ahierarchical tree format where each supercentroid contains pointers specifying
the locations of the individual centroids for that superclass, and each centroid
in turn points to the locations of the individual document vectors for that class

Figure 4-5•

centroid vector■

supercentroid vector

Introd uction of superclusters.

127

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMSSUPERCENTROIDk

SCTERMk1, SCTERMk2........ SCTERMktCENTROIDPOINTER i •CENTROID,t

DOCPOINTER i2

C T E R M j , , C T E R M j 2 ...........C T E R M jt
D O C P O IN T E R j1

Figure 4-6.

CTERMm, CTERMi2........ CTERMitDOCPOINTER il

C E N T R O ID ,CENTROIDPOINT jt

D O C P O IN T E R j2

DOC„

TERMm ,TERM i12........ TERMm

DOCi2

TERMi21, TERMi22........ TERMi2t

docm

TERM,,,, TERMjl2 , . . . . TERM,,,

DOCj2

TERMj21,TERMj22.........TERMj2t

Hierarchical vector arrangement fo r clustered file.

The file arrangement is illustrated in simplified form in Fig. 4-6.
C Vector Generation

Consider now the document indexing process, that is, the method used to con­struct the document vectors. The basic function of an indexing system is thesegregation of the subset of documents relevant to some query from the re­mainder of the collection. Preferably, all the relevant items might then occur in
one or more document clusters, whereas the nonrelevant items would beplaced in separate clusters. A situation of this type is shown in Fig. 4-7. Such an
ideal document space might be constructed by assigning to the relevant docu­
ment set the terms utilized by the user population to formulate the correspond­
ing search requests. Unfortunately, it is difficult to know in advance what terms
will be considered useful for query formulation purposes, and even in inter­
active systems where information can be generated about the usefulness of cer­tain terms with respect to certain topic areas, it is still necessary to make thesomewhat hazardous assumption that all users interested in specified subject
areas would choose the same query terms to express their information needs.
Similarly, one would have to assume that all such users would accept the same
set of documents as relevant to their queries.

CHAPTER 4

128x

Figure 4-7

nonrelevant documentwith respect to a query

Ideal docum ent space.

In practice, it is not possible to find a single clustering which is ideal for all
subject areas and all users, even given full relevance information in advance.
Furthermore, hew documents that are added to the collection must necessarily
be processed without the use of document relevance information. The best pol­icy may then lead to the use of index terms capable of distinguishing each par­ticular document from the remainder of the collection. This can be achieved byusing as a controlling criterion the document frequency of each term in the col­lection, that is, the number of documents to which a term is assigned. The term
discrimination theory examined in the previous chapter indicates that the terms
to be preferred are medium-frequency terms that are assigned to a few docu­
ments but not to the rest of the collection.
In the SMART system, the text of the document abstracts (or the text ofthe query statements obtained from the user population) is analyzed automati­
cally. Terms whose document frequency is neither too large nor too small areincorporated directly into the document or query vectors for indexing pur­poses. Terms whose document frequency exceeds a given threshold are consid­
ered too broad and unspecific; they are rendered more specific by being com­bined with other terms into term phrases before assignment to the document
and query vectors. On the other hand, terms with a very low document fre­quency that are assigned to one or two documents only are considered too spe­cific; they can be broadened by grouping them into term classes of the kindfound in a thesaurus of terms. The thesaurus class identifiers are then incor­
porated into the term and document vectors instead of the individual rareterms. These operations are described in more detail in the next section, where
the SMART procedures are treated more thoroughly.
A simplified flowchart of the SMART processing chain is shown in Fig.
4-8. The processes represented on the left side of the chart consisting of theTHE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

Figure 4-8

129

Sim plified SMART system flow chart.

initial construction of term vectors for the documents and the generation ofclustered files are carried out only once, or in any case at infrequent time intersvals. The query-processing operations, on the other hand, including the genera­tion of query vectors, the clustered .file search, and the relevance feedback op­
erations are performed for each query. Only the query-handling operations
heed to be done in real time while the user is present.
The SMART system is designed to make available a large variety of ex­
perimental methods, including many different automatic indexing procedures,query-document similarity functions, cluster file generation methods, andquery-reformulation processes. The system can then serve as a test vehicle tovalidate the various experimental procedures. For this reason evaluation
methods have been incorporated into the system which produce recall and pre­cision information following the retrieval operations.
The following assumptions are implicit in the model used by the SMART
environment for the representation of document and query operations:1
Each document is represented by a particular vector, that is, a particu­
lar position in a t-dimensional vector space, where t is the number of permissi­
ble terms available for indexing purposes.

130

CHAPTER 4

2
Each term included in a given document or query vector is assumed to
Be unrelated (orthogonal) to the other terms, and all terms are consideredequally important (except for distinctions inherent in the assignment of weights
to the individual terms).
^--The assumptions are in fact only first-order approximations to the true sit­uation because documents exhibit not only subject content but also extent, or
scope. A survey or tutorial text normally has greater scope than a research arti­cle. This suggests that the subject matter of a document be represented by apoint in a certain location of the subject space as suggested by Figs. 4-3 to 4-5,
and that an area of space surrounding the subject points be used to denote
scope and extent. The document scope might be determined by using the fre­quencies with which individual documents are cited in the literature. Thus doc­
uments attracting many citations could be assumed to have wide scope.
^ The second area of simplification in the SMART model is the orthogonality
assumption for the various index terms. In the SMART system, each term rep­resents a separate coordinate in the vector space, and no term relationships are
assumed to exist. In actual fact, words do not, however, occur independentlyof each other in the document texts, and neither do the index terms assigned toa collection of items. In recent years, a great deal of work has been devoted tothe study of retrieval models which take into account certain term dependen­cies. These models tend to be complex and difficult to use. The available ex­perimental evidence suggests that the greatest deviations from independence
arise for the very rare terms that occur in a few documents only. The discrimi­
nation value theory indicates that these terms are not very important for re­trieval purposes. For the vast majority of the medium- and high-frequency
terms, the independence assumption is not in fact unreasonable.
Perhaps in a few years, some experimental retrieval systems will makeprovision for the representation of document scope and impact and for the useof term dependencies. At the present time efforts in this direction are in a very
preliminary state.
3 SMART SYSTEM PROCEDURES*A Automatic Indexing

When the SMART system was originally designed in the middle 1960s the ex­perts generally felt that sophisticated language analysis procedures would be
required in a machine indexing system to replace the intellect normally appliedby the human indexer. Accordingly, the original SMART indexing system wasbased on the following language analysis tools:
1 Synonym dictionaries, or thesauruses, would be used to group the indi­vidual terms into classes of synonymous or related terms. When a thesaurus isavailable, each original term can be replaced by a complete class of related
terms, thereby broadening the content description.
2 Hierarchical term arrangements could be constructed to relate the con-THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

131

tent terms in a given subject area. With such preconstructed term hierarchies,
the standard content descriptions can be “expanded” by adding to a given con­tent description hierarchically superior (more general) terms as well as hierar­
chically inferior (more specific) terms.
3 Syntactic analysis systems would serve for the specification of the syn­tactic roles of the terms, and for the formation of complex content descriptions
consisting of term phrases and larger syntactic units. A syntactic analysis sys­
tem can be used to supply specific content identifications, and it prevents con­fusion between compound terms such as “blind Venetian” and “ Venetianblind.”
4 Semantic analysis systems might supplement the syntactic units byusing semantic roles attached to the entities making up a given content descrip­
tion. Semantic analysis systems utilize various kinds of knowledge extraneousto the documents, often specified by preconstructed “ semantic graphs” andother related constructs.
The early test results obtained with the SMART system showed that somecomplicated linguistic methodologies that were believed essential to attain rea­
sonable retrieval effectiveness were in fact not useful in raising performance[5,6]. In particular, the use of syntactic analysis procedures to construct syn­tactic content phrases and the utilization of concept hierarchies could not be
proved effective under any circumstances. It may be that these failures were
attributable not to the actual processes themselves but rather to the particular
implementations used in the test situations. The fact is that linguistic theories
were not sufficiently well understood 15 years ago to permit the construction ofeffective semantic maps and hierarchical term arrangements, or to design accu­
rate and complete syntactic analysis systems. Some progress has been made inthis area in the last few years. However, versatile linguistic methodologies thatwould be applicable to a wide variety of subject areas are still not easily incor­
porated into an unrestricted language processing environment at the present
time. For this reason the standard SMART indexing procedures are based on
simpler language process considerations that are by now well understood.
These simple automatic methods can be shown to be superior to conventional
indexing methodologies in laboratory test situations [6,7]:
1 The individual words that make up a document excerpt (abstract) or aquery text are first recognized.
2 A stop list, comprising a few hundred high-frequency function words,
such as “ and,” “of,” “or,” and “but,” is used to eliminate such words fromconsideration in the subsequent processing.
3 The scope of the remaining word occurrences is broadened by reducing
each word to word stem form; this can be done by using relatively simple suffix
removal methods together with special rules to take care of exceptions, as pre­viously explained [8,9].
4 Following suffix removal, multiple occurrences of a given word stem
are combined into a single term for incorporation into the document or query
vectors.

132

CHAPTER 4

At this point, the standard query-document vector matching methods in­troduced in the previous section could be used to identify all documents whose
word stem vectors are sufficiently similar to the query vectors. The SMART
system retains a much larger number of content indicators than is customary inconventional systems, and the larger number and greater diversity of the terms
compensate to some extent for the lack of precision in the term selection.
Nevertheless, the foregoing process would provide inferior search results inmany cases, because some word stems are obviously more important for the
representation of document content than others. Two main operations areneeded to transform the word stem vectors into useful term vectors: first a term
weight can be assigned to each term reflecting the usefulness of the term in thecollection environment under consideration; and second, terms whose useful­ness is inadequate as reflected by a low term weight can be transformed into
better terms [10-13].
As explained earlier, it is convenient to separate the term weighting task
into two parts: first, one must take into account the term characteristics withina given document or document excerpt; second, it is important to consider also
the function of the term in the remainder of the collection. The considerations
detailed in Chapter 3 favor terms that exhibit high importance in the documents
to which they are assigned, as measured, for example, by their occurrence fre­quencies in the individual documents. At the same time, the best terms must beable to distinguish the documents to which they are assigned from the remain­
der of the collection; hence their importance factor in the document collection
as a whole ought to be low. The importance of a given term k in an individual
document i is conveniently measured by the frequency of occurrence in the
document FREQik. The usefulness of the term in the collection as a whole may
be reflected by the term discrimination value DISCVALUEk, or alternatively
by an inverse function of the document frequency DOCFREQk (that is, thenumber of documents to which the term is assigned). Two possible term
weighting functions reflecting the usefulness of term k in document i are
WEIGHT* =FREQ*
DOCFREQk(4)

and WEIGHT* = FREQ* • DISCVALUEk
Terms with a low weight according to expression (4) could in principle bedeleted from the indexing vocabulary. In practice, the deletion of broad, highfrequency terms is likely to cause losses in recall, and the elimination of spe­cific, low-frequency terms may impair the precision. It is then preferable toalter such terms completely. The most obvious methods available for this pur"■pose consist in creating specific term phrases incorporating the high-frequency“-terms that are originally considered too broad, and forming thesaurus classesof the low-frequency terms that may be too specific to be used by themselves.
Consider first the phrase-formation process. Ideally, a phrase is a language
construct with specific syntactic and semantic properties. Because a full syn-THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

133

tactic and/or semantic analysis of document and query texts is not currently
possible for normal information retrieval purposes, a simple phrase-formation
process must be used. The following phrase-formation criteria are of greatest
importance:
1 The phrase components should occur in a common context within the
document or query to which the phrase is assigned as a content identifier.
2 The phrase components should represent broad concepts, and their fre­quency of assignment to the documents of a collection should be sufficiently
high.
In the SMART system a phrase is defined as a pair of two distinct wordstems not contained on the stop list, such that the components occur in thesame sentence within a document or query text, and at least one component
has a document frequency in the collection exceeding a given threshold. A
more stringent phrase-construction process is obtained by also taking into ac­
count the distance in the text between potential phrase components, that is, thenumber of intervening words between them. The following phrase-construction
process can be used in practice:
1 Start with the query and document texts; use a stop list to eliminate
common function words; generate word stems by using a suffix deletion pro­
cess to reduce the original words.
2 Take pairs of the remaining word stems, and let each pair define aphrase provided that the distance in the text between components does not ex­
ceed n words (at most n - 1 intervening words), and that at least one of the com­ponents of each phrase is a high-frequency term; this frequency cutoff is manip­ulated to reduce the number of generated phrases to manageable size.
3 Phrases for which both components are identical are eliminated, as are
duplicate phrases where all components match an already existing phrase.
4 Phrase weights are assigned as a function of the weights of the individ­
ual phrase components; if the term weights are restricted to values between 0
and 1, the phrase weight can be defined as the product of the individual compo­
nent weights.
The phrase-generation process is illustrated for a sample sentence in Table
4-1. Some of the original words, such as “in,” “need,” “of,” and “require,” aredeleted following a comparison with the entries contained in a stop list. The
remaining words are transformed into word stems: this generates INFORM
from “information” and RETRIEV from “retrieval.” A maximum distance offour is assumed between phrase components in the text, leading to the genera­tion of the seven phrases listed in Table 4-lc.
The phrase-formation process increases the specificity of the content iden­tifiers attached to queries and documents. The converse operation consists inusing thesaurus classes for content identification. A thesaurus contains group­
ings of similar or related terms into term classes. The use of thesauruses is

134

CHAPTER 4"People in need o f inform ation require effective
retrieval services"(e)"PEOPLEINFORM

EFFECTRETRIEVSERVICE"(b)

PEOPLEINFORM

EFFECTRETRIEVINFORM

EFFECT

EFFECTSERVICEINFORMRETRIEVRETRIEVSERVICEINFORMSERVICE(c)

Table 4-1

Phrase-generation process, (a) Original sentence, (b) Word stems generated fromoriginal sentence, (c) Word pairs (phrases) generated assuming maximum component dis­
tance of four.

often advocated for purposes of synonym recognition: when the query specifies“manufacture” and the document contains “production,” a term match is ob­
tainable by including both terms in a common thesaurus class. Because the fre­quency of assignment of a thesaurus class is approximately equal to the sum of
the frequencies of the individual terms in the class, thesauruses are most usefulfor the classification of the low-frequency terms that need to be broadened.
Since the automatic term classification (thesaurus) construction methods are allbased in one way or another on the computation of similarities between terms,
thesauruses are not easily generated automatically. Normally, the term similar­
ities would be obtained by computing similarity coefficients between the term
vectors (columns) of the term assignment array (see Fig. 4-1). In effect the simi­
larity between two terms will then depend on co-occurrences of the terms in the
documents of a collection. Unfortunately, the terms of most interest for thesau' rus construction purposes are those whose overall occurrence frequency in acollection is low. These terms do not co-occur very often in the same docu­
ments, and their computed similarity measure must be expected to be very low
and may not then furnish an accurate indication of term relationship.
In practice, it becomes necessary either to use a manually constructed the­saurus that obeys the thesaurus construction principles described in the previ­
ous chapter, or else to use an automatic thesaurus construction method in-which the grouping criteria are relatively weak [14,15]. The well-known single­
link classification method appears to be most useful in this connection [16]. The
single-link process is based on a computation of the term-term similarities for
all term pairs. The process then proceeds iteratively as follows:

135

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

1 For each term pair (TERMj, TERM,) whose similarity exceeds a given
threshold, an attempt is made to add a third term, TERMk, to the group bycomputing the similarity between TERMk and each of the original terms; thenew term is added whenever its similarity with at least one of the original terms
exceeds a stated threshold.
2 The process is then repeated for term triples, quadruples, etc., by add­
ing a new term whenever its similarity with one of the original terms exceeds
the stated threshold.
An example of this process is shown in Fig. 4-9. The significant term-pairsimilarities are shown in Fig. 4-9a in tabular form. Figure 4-9b presents thesame information in graph form, where the nodes of the graph designate terms,
and the branches between nodes represent the corresponding term similarities.
The final term clusters are given in Fig. 4-9c. The initial cluster is obtained byfirst forming the class {Tx,T2}. To this are added terms T3 and T7 because of thesimilar term pairs (T2,T3) and (T2,T7). This produces a new class {T4,T2,T3,T7}.
This group can be increased to its full size by adding Tg because of the connec­
tion between T3 and T8. A second class is formed of terms T4, T5, and T6 in view

< i)(T ,,T 2)( iiM T j.T ,)(iii)(T 3, T2 )(Iv)(T4 , T 5)

(T 2, T 3 )(t 3 , t 8)

(T4 , T 6 )(vii)(T 7, T 2)

(v iii)(T 8 , T 3 )<t2, t7)(v )(T 6, T 4 )(vi)(T6 , T 4 )(a)

IAAAIIII

t2

t,

t3

t7

t2

t8

t5

t6

t4

t4

t2

t3

(b)

i

(0
Figure 4-9 Single-link cluster example, (a) Initially available term pairs, (b) Corresponding
graphical representation, (c) Corresponding single-link clustering.

136

CHAPTER 4of the existence of the similar pairs (T4,T5) and (T4,T,j). For the example underconsideration the thesaurus classes produced are as follows: {T4,T2,T3,T7,TJ
and {T4,T5,T6};
The single-link cluster process requires of the order of n2 term com­
parisons to classify n terms, since each term is associated with at most (n - 1)other terms. This method has been used to cluster large collections of items[17], and it may be applicable to the general term classification problem be­cause the number of terms does not normally exceed several tens of thousands.
For document clustering, where the file size may Comprise hundreds ofthousands or even millions of items, less expensive methods may turn out to be
more appropriate. A summary of the SMART automatic indexing system ispresented in the flowchart of Fig. 4-10.
i

Use remaining single terms, term phrases,
and thesaurus classes w ith appropriate
term weights to construct document andquery vectors

Figure 4-10 Typical SMART automatic
indexing process.

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS137*B Automatic Document Classification

It was seen earlier that the preferred file organization in the SMART environ­ment is a clustered collection where the incoming queries are compared firstwith the centroids of certain document classes and then with the individual doc­
uments for those classes whose centroid similarity with the queries is suffi­
ciently large. The clustered file organization lends itself to rapid collection
searches and to fast and possibly effective retrieval strategies because all the
related documents in a given class are in principle retrievable in a single fileaccess. Furthermore, a clustered file is updated easily, because new documents
can be treated like incoming queries in that comparisons with the existing cen­troids lead to the incorporation of new items into the most closely fittingclasses.
The available clustering methods fall into two main types according towhether an initial set of classes already exists or on the contrary new classes
must be constructed for a given collection of items. When document sets are to
be clustered, a prior classification is not generally available; it is then necessary
to construct a new classification for the given set of items. A second clustering
criterion distinguishes the hierarchical grouping methods which utilize a full"document-document similarity matrix specifying the similarity for all document
pairs, from the iterative partitioning procedures where a rough classification—'
is first generated which is then refined in several steps.
The hierarchical grouping methods which include the previously men­tioned clique and single-link procedures are theoretically more satisfying than
the alternative partitioning methods because in these methods each item is ef­
fectively considered as a possible “ seed point” around which a new class is tobe built, whereas the classes formed with the iterative partitioning process de­pend on the strategy used for the initial cluster generation. A form of iterative
partitioning is nevertheless used with the SMART system because the numberof required document comparisons to cluster n items is of the order of n log n,
whereas n2 comparisons may be needed to obtain the document pair simi­
larities needed by the hierarchical grouping strategies. When the collections arelarge, a relatively inexpensive clustering method seems essential.
The SMART ’’single-pass” clustering proceeds in a bottom-up fashion byconsidering the records one at a time in arbitrary order, while attempting togroup them into clusters [18,19]. The first item is initially identified with cluster
one. The next item is compared with cluster one and merged with it if found tobe sufficiently similar. If the new item is hot similar to any already existing clus­
ter, a new cluster is generated. Subsequent items are compared with all existingcluster centroids and entered into classes whenever the centroid similarity is
sufficiently large. When a new item is entered into a cluster, the corresponding
cluster centroid must be redefined by incorporating terms from the new term
vector into the original cluster centroid.
In principle, the single-pass clustering process should serve to assign each
item to at least one cluster, and the classification should be complete after one

138

CHAPTER 4

pass through the file. In practice, the resulting classes may not be usable forsearch purposes without additional refinements. Several problems may arise:
1 The number of clusters produced by the initial pass may become exces­
sively large, implying that a query submitted to the system may have to be com­pared with a very large number of centroids before access to the individual rec­ords is actually obtained.
2 The size of certain clusters may become too large, particularly if a great
many records in a collection cover fairly homogeneous subject areas.
3 Alternatively, the cluster size may be very small, and could indeed belimited to a single record in cases where so-called loose records exist that do
not match any other records in the collection.
4 The overlap among clusters, that is, the number of items jointly con­tained in more than one cluster may be too large or too small.
To respond to these eventualities, controls must be introduced to regulate
cluster size, cluster overlap, and number of clusters generated, and to handle
any “loose” items remaining at the end of the first pass. The loose items ac­
tually present no severe problem, since they can naturally be merged with theclosest existing clusters. To control the size and the number of clusters, a clus­
ter splitting operation is carried out whenever a given cluster size exceeds
some preestablished threshold. This is done by generating a term-term simi­
larity matrix for all terms located in the excessively large clusters, and using a
new local clustering operation to produce two or more new centroids replacing
each centroid originally attached to a cluster that had grown too large.
The cluster splitting operation is illustrated in the example of Fig. 4-11
where the assumption is that no class may contain more than four elements.
The initial state consists of four clusters, each containing between two and four
records. These four centroids are themselves grouped into a supercluster withsupercentroid S as shown in Fig. 4-1 la. If a new record is added to cluster A, anillegal situation arises, since the cluster size is assumed limited to four ele­ments. The A centroid must then be split thereby creating two new centroids A'
and A ” as shown in Fig. 4-1 lc. At this point the supercluster S is no longer
viable since it now contains five elements. This is remedied by splitting S into
S' and S” , thereby creating a new hypercluster H included in Fig. 4-1 Id. The
cluster splitting process thus propagates upward in the “cluster tree,” startingwith the lowest level clusters and moving upward as shown in the example.
A simplified flowchart of the single-pass cluster generation and search pro­
cess is shown in Fig. 4-12. Generation and search differ in substance only forthe lowest-level centroids: during cluster generation a new record must be
added to the lowest level of the cluster tree and the cluster splitting routine mayneed to be invoked; during normal searching, on the other hand, the low-levelclusters simply lead to the individual records on the lowest level. The programof Fig. 4-12 maintains a list of centroids to be split. When that list is not empty,
the splitting routine is invoked following the placement of each incoming item.

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

139

S

s

Figure 4-11 Example of cluster splitting process, (a) Initial state of cluster structure, (b) Ad­
dition of one more item to cluster A. (c) Splitting cluster A into two pieces A' and A". (d) Split­ting supercluster S into two pieces S' and S".

The cluster generation method may be adapted to special retrieval require­ments: when a premium is placed on search precision and the retrieval ofnonrelevant items must be avoided, the cluster structure should consist of alarge number of small, disjoint clusters on the lowest level of the search tree.
When the recall proves more important a smaller number of larger, partly over­lapping clusters should prove more effective. Suitable adjustments in thethresholds that control the clustering process can be used to satisfy varying re­trieval requirements.

140

CHAPTER 4

EXIT(To cluster splitting)Figure 4-12

*C

Cluster generation and search. (Adapted from reference 18.)

Relevance Feedback Operations

Most modern on-line search and retrieval environments make provisions forthe utilization of flexible search procedures that can generate satisfactory query
statements and useful retrieval output in several small steps. An iterative
search system is typically implemented by initially submitting a tentativeTHE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

141

query, and then using system facilities to improve these query statements andthe resulting set of retrieved items.
The methods used to construct improved query formulations fall into two
broad classes: those which are applied before a file search is actually carriedout, and those which depend on the prior retrieval of some retrieved items. In
the former case, it is possible to use displayed vocabulary excerpts, term fre­quency information, and citations to so-called source documents previously
identified as relevant by the user to construct improved queries. More specifi­
cally, a stored thesaurus of terms can be used to obtain synonym lists for theterms originally included in a search formulation. In addition, frequency data
about the number of documents to which a term is assigned can also be stored
in the thesaurus to provide an indication of the potential effect of the term forsearch purposes. When relevant source documents are known in advance, aquery might simply be replaced by the terms assigned to such documents in thehope of retrieving additional documents similar to those originally identified as
relevant.
An alternative query alteration process is based on the execution of an ini­tial search operation and an initial retrieval of certain stored documents. The
display of information relating to these items such as the titles or abstracts ofthe previously retrieved documents is then used to modify the query state­ments, normally by adding terms from documents that appear relevant to theuser and by deleting terms included in the items that appear useless. This pro­duces new queries whose resemblance to the relevant documents is greaterthan before while their resemblance to the nonrelevant items is smaller, as sug­gested in the example of Fig. 4-3. In the SMART system, this process has beencalled “relevance feedback.” It has been shown experimentally that the rele­vance feedback process can account for improvements in retrieval effective­
ness of up to 50 percent in precision for high-recall (broad) searches, and of
approximately 20 percent in precision for low-recall searches [20],Consider first the unrealistic situation where the complete set of relevant
documents DRis known in advance, and hence also the complete set of nonrele­vant documents DN_R = N - DR. (In such a case, there is no point in submitting
a search request because the known relevant documents can then simply be re­trieved from the file without performing a file search.) It can be shown that insuch a situation the optimal query which is best able to distinguish the relevantfrom the nonrelevant documents is a vector obtained by taking the difference
between the set of relevant and the set of nonrelevant documents, respectively.
More formally, if TERMik represents the value, or weight, of term k in docu­
ment i as before, then the average value of term k in the set of R relevant docu­
ments is^

TERMikj . Similarly, the average value of term k in the setof N - R nonrelevant documents is

r)

^ ^

term k in the optimal query Qopt is then defined as

TERMikj . The value of

142

CHAPTER 4(5)
where C is a constant [21]In practice the sets of relevant documents DR and of nonrelevant items
D n,_r are not known in advance. However, the relevance judgments obtained
from the user population for previously retrieved relevant documents furnish
approximations to the sets DR and DN_R. The assumption is then made that anear-optimal query can be obtained by taking the difference between the sub­sets of relevant and of nonrelevant items known at any particular time. By re­peating the relevance feedback operation several times, and retrieving at eachpoint a new set of documents with an improved query formulation, one may
eventually obtain a reasonable approximation to the actual set of relevant andnonrelevant items.
Several formulations are now possible for a new improved query vector
Q', starting with an initial query formulation Q and a set DR- of R' documents
identified as relevant as well as a set Dv of N' nonrelevant documents, where
Dv and DR>are initial representations of the actual set of nonrelevant and rele­vant documents, respectively. First it is possible by analogy to the optimal for­mula of expression (5) to define the new query as simply the difference between
the known sets of relevant and nonrelevant items, respectively:( 6)

DOCi again represents the vector for the ith document. In formula (6) the infor­
mation contained in the original query Q is not used. In practice the original
query formulation may contain important information; hence an improved
feedback strategy may be produced by using the original query and adding
terms from the relevant documents, and/or deleting terms from the nonrelevant
ones:
Q' = aQ + p

2
i€DR'

D 0 C i)

" 7 ( |J 7

S

DOC,)

(7)

ieDN,

where a , (3 , and y are suitable constants. Expression (7) specifies a new queryas the vector sum of the old query plus the weighted difference between the
average of the known relevant and the average of the known nonrelevant items.
The operations specified by expression (7) are illustrated in the example ofFig. 4-13, where a query Q comprising five terms is shown together with a rele­vant document Dx and a nonrelevant document D2. The constants a , j8 , y are
assumed to take on values of 1, V2 , 74, respectively. The new query derived inFig. 4-13c exhibits increased weights for terms 1 and 3, a decreased weight forterm 5, and a new term (term 2) not present in the original query. Correspond-

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS
Term 1

Term 2

Term 3

Term 4143

Term 5

1

)

0

)

2

)

t
AssumeSIQ.D,) = 2(Qj, D,))

j=1

Figure 4-13 Relevance feedback operation, (a) Originally available query Q, relevant docu­
ment D,, nonrelevant document D2. (b) Query alteration, (c) Query-document similarities.

.

ingly, the query-document similarity obtained with the new query Q' is larger
than before for document D t and smaller than before for D2.
In practice one finds that the information contained in the relevant docu­
ments is more valuable for query reformulation purposes than the terms which
originate in the nonrelevant items. The reason is that the set of relevant docu­
ments with respect to a given query may be expected to be located in a reason­
ably homogeneous area of the document space, as in the example of Fig. 4-7.i
The addition to the query of terms from these relevant items will then produce adefinite movement of the query in the direction of these relevant items (see Fig.
4-3). The set of nonrelevant items, on the other hand, is normally much moreheterogeneous. The average nonrelevant item may therefore be located almost
anywhere in the document space, and subtraction of the corresponding terms

144

CHAPTER 4o relevant document
x nonrelevant document* average item

Figure 4-14 Relevance feedback en­
vironment. (a) Ideal relevance feedback
situation, (b) Tight relevant document set,
but loose nonrelevant set. (c) Intermin­
gled relevant and nonrelevant docu­
ments.

removes the query from that area of the space without specifying a definite al■—“-'ternative direction. The feedback equation, [expression (7)] should then be usedwith a smaller weight for y than for (3. Alternatively y might be specified as 0,
thereby creating &positive feedback strategy. A third alternative consists inusing only a small set of nonrelevant documents by including in the feedback
equation only one or two documents— for example, the nonrelevant docu­
ments retrieved earliest in a given search (those exhibiting the lowest ranks
when the documents are arranged in decreasing order of the query-document
similarity).

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

145

Since the difference between the average relevant and the average nonrelevant documents is equivalent to the distance between the corresponding vec­
tors in the vector space, it is not surprising that the formal as well as experi­mental test results show that the retrieval operation is most effective when the —relevant documents as well as the nonrelevant documents are tightly clustered,and the difference between the two groups is as large as possible. Such a situa­tion is represented in Fig. 4-14a.
The relevance feedback operation is less favorable in the more realistic
case where the set of nonrelevant documents covers a wider area of the space.
The corresponding distance between the average relevant and nonrelevant
items is much smaller in Fig. 4-14b than in Fig. 4-14a. Finally, the situation is
distinctly unfavorable when relevant and nonrelevant are intermixed as shownin Fig. 4-14c. That situation represents a failure of the basic assumption of the
SMART document analysis, namely that document content can be represented
for retrieval purposes by the term occurrence vectors. Additional informationmust then be added to the document vectors to distinguish those which are use­
ful from the others. Some approaches to this problem are mentioned in thenext section.
The experimental evidence available for relevance feedback indicates that —=one or two feedback operations are quite effective in raising retrieval perform­
ance. Following the second query reformulation a state of diminishing returns
sets in and not much further improvement can be expected.
*D

Dynamic Document Space

The query alteration process described in the previous subsection was based on
information obtained from the user population in the course of the normal re­trieval process. In a system where customer intelligence is available, an at­
tempt can also be made to improve the document vector representation (in­stead of only the query vectors) by incorporating into the document
representations new information obtained from the users during the search op­
erations. One possibility consists in adding to the originally available document
terms new information derived from relevance assessments furnished by theusers in the course of a retrieval operation.
Specifically, when a number of documents retrieved in response to a given
query are labeled by the user as relevant, it is possible to render these docu­
ments more easily retrievable in the future by making each item somewhat
more similar to the query used to retrieve them. Analogously, retrieved docu­
ments labeled as nonrelevant are rendered less easily retrievable by being
shifted away from the query. Following a large number of such interactions,documents which are wanted by the users will have been moved slowly into theactive portion of the document space— that part in which a large number ofuser queries are concentrated, while items which are normally rejected will belocated on the periphery of the space. Eventually, such items could be dis­carded.
By analogy to the relevance feedback operations, the dynamic document

146

CHAPTER 4

vector alteration can be carried out by constructing a new document represen­tation DOC; from the old document representations DOQ and the terms con­tained in query Q. The query terms are added to the original document vector
using the positive weighting factors a, (3, y, 8, and e:
1 For documents designated as relevant, which must be rendered more similar
to query Q:
a A query term not present in the document is added to the document witha weighting factor of a.
b A query term also present in the document receives increased impor­tance by incrementing its weight by a factor (3.
c A document term not present in the query is decreased in weight by afactor —y.
2 For documents designated as nonrelevant which must be rendered less simi­
lar to the query:a Document terms also present in the query are rendered less importantby decreasing their weight by a factor of - 8.
b Document terms absent from the query are increased in weight by a fac­
tor e [22,23].
Several laboratory tests were carried out to test the foregoing dynamic
document space alteration methods. In each case, a collection of user queries
was first used to generate a modified document space. A new query set, distinct
from the original one, could then be processed against both the originally avail­able document space and the modified space. Improvement in recall and pre­cision of from 5 to 10 percent could be detected for the modified space com­pared with the original space. One would expect that the document vector
modification process carried out for a given time period with a particular user
population would eventually produce an equilibrium position where documents
important to the users could become easily retrievable whereas extraneous
documents would be easily rejected. Such a conjecture remains to be verified inpractice.
4 AUTOMATIC ENHANCEMENTS OF CONVENTIONALRETRIEVAL*A

Document Ranking and Term Weighting

Various retrieval systems and procedures have been implemented over the last
few years that are based in one way or another on the SMART model [24,25].
Possibly the most useful of these from a practical viewpoint are systems that
preserve as much as possible the conventional processing methodology while
adding enhancements to simplify the retrieval operations and to improve sys­
tem effectiveness. The main characteristics of currently existing retrieval tech­
nologies are the inverted file organizations and the use of Boolean query formu­
lations. This suggests that improved retrieval services could be obtained by
combining the basic inverted file systems with SMART-like “back-end” proce-

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

147

dures, designed to overcome some of the disadvantages of conventional sys­tems.
Among the methods usable for improving the output produced by conven­tional file systems are the incorporation of weighted instead of binary terms andthe presentation of the retrieved output in decreasing order of the query-docu­
ment similarity. The generation of ranked document output increases user sat­
isfaction and retrieval precision. Furthermore, the ranked retrieval can sub­stantially enhance the chances of success of the relevance feedback process bybringing the relevant items to the user’s attention early in the search; this in turnleads to the construction of useful feedback queries.
Ranked retrieval and relevance feedback can in principle be implemented
in binary indexing systems where the index terms are either present or absent
from the document and query vectors. However, the documents are easier torank when weighted terms are assigned to the queries, and possibly also to the
documents, because a composite query-document similarity coefficient canthen be computed for each query-document pair based on the weights of match­ing query-document terms.
In a system such as SMART where each document is represented by a vec­
tor of terms and each vector is stored as a complete entity, the use of term
weights presents no conceptual problem, because a term weight can simply belisted with each term identification in the corresponding term vector. Thus aparticular document i dealing with “fruit” might be listed as
DOQ = (APPLE,4; PEAR,3; . . . ; PLUM,1)
to indicate that the document deals rather more with pears than with plums,
and even more with apples. In inverted file systems, the term weighting infor­
mation must be included in the various inverted lists. Thus the term list for agiven term k must now be expanded to include not only the document refer­ences for documents to which term k is assigned but also the particular weights
for that term in the various documents. A sample inverted file of that kind isshown in Table 4-2.
Given some particular query Qj, a file organization such as that of Table
4-2 now makes it possible to compute a similarity measure between the queryand the document terms. For each term k included in query j, the correspond­
ing term list is extracted from the inverted file, and the weights of terms that
occur in both query j and document i are appropriately combined to produce asimilarity measure between the given query j and each document that shares
Table 4-2 Typical Inverted Term Lists with Weights
TERM,
TERM.,

DOChWTh ; DOCj.WTj, ; . . . ; DOCm,WTm1
DOC|,WT|2; DOCk,WTk2; . . . ; DOCn,WTn2

TERMS

DOC,,WTIs; DOCm,WTms; . . . ; DOCp,WTps

148

CHAPTER 4

terms with the query. Consider a query consisting of three terms r, s, and t, andlet the similarity measure between the query j and document i be defined as thesum of the products of the matching terms [that is, the numerator of the cosine
formula of expression (1)]. To compute the similarity measure between thegiven query and document, it suffices to enter first the inverted list for term r
and pick out TERMir representing the weight of term r in document i. This
leads to the computation of the product QTERMjr • TERMir. A subsequent ac­cess to the inverted lists for terms s and t makes it possible to add to the earlier
product the terms QTERMjs • TERMls and QTERMjt • TERMit.
To compute the cosine measure of expression (1) an additional normaliza­tion factor consisting of the sum of the squares of all term weights included ineach document and each query is needed. This makes it necessary to providetfor each document i the factor ^ (TERMik)2. These factors can be computed
k=lin advance for each document and stored in a special “ document length” filewhich is accessed for all documents that have a nonzero similarity with thequery. The expanded inverted document reference lists together with the docu­
ment length file permit the computation of the full cosine similarity measure forall documents sharing one or more terms with the query, followed by the rank­
ing of documents in decreasing order of the query-document similarity.
The SIRE (Syracuse information retrieval experiment) system includes thenormal inverted file processing facilities used for the Boolean query operations,as well as the expanded term weighting operations that provide ranked docu­
ment output [26-28]. The SIRE file organization is shown in Fig. 4-15, and thecorresponding processing chain is presented in simplified form in Fig. 4-16. In
essence, the SIRE processing chain consists of two main sections. Initially, a
Boolean query formulation is processed in the conventional manner. This step
identifies all documents whose term assignment precisely matches the query
formulation. This subset of documents is then further processed by computing
a cosine similarity measure between each document and a “flattened” query
consisting of all the original query terms connected by Boolean OR operators.
Thus an original query formulated as (A AND B) OR (C AND D) becomes A
OR B OR C OR D, or simply the query vector (A,B,C,D).
In the SIRE system the users are not expected to assign weights to theterms. Instead the weight of term k in document i is defined as FREQik, that is,as the frequency of occurrence of the term in the document. Correspondingly,
the document length needed in the denominator of the cosine computation is
obtained as the sum of the squares of the individual term frequencies in the doc­
ument. It is easy to see how the file organization of Fig. 4-15 leads to the proper
computation of the cosine measure. A directory to the inverted lists is used togain access to the document reference numbers and the weights (term frequen­cies) for all query terms. This produces the numerator of the cosine for eachrelevant document (each document retrieved by the Boolean query) and thecorresponding query. The document length is next obtained for each documentfrom the document length list (Fig. 4-15c). Following the computation of theTHE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

149

DOCUMENT NUMBER*

FREQUENCY*,

DOCUMENT NUMBER,,FREQUENCY,,,DOCUMENT NUMBERm

FREQUENCYm,

TERM,

POSTINGS,POINTER,DOCUMENT NUMBERbf r e q u e n c y 02

TERM2

POSTINGSj

POINTER2 .. > L istj

DOCUMENT NUMBERC

f r e q u e n c y C2TERM,

POSTINGS,POINTER,DOCUMENT NUMBERp

f r e q u e n c y P2

DOCUMENTNUMBER dFREQUENCY,,,DOCUMENT NUMBERm

FREQUENCYm,

DOCUMENTNUMBER r

FREQUENCYr,

(a)

L St,

(b)

DOCLENGTH,

POINTER,DOCUMENT,

INFORMATION

do c len g th 2

POINTERj

docum ent2

INFORMATION

DOCLENGTHn

POINTER,,DOCUMENT,,

INFORMATION

(c)

<d>

Figure 4-15 SIRE file organization, (a) Directory to inverted lists, (b) Inverted document ref­erence lists, (c) Document length list, (d) Main document file.

query-document similarities, the output information may be extracted from themain document file in decreasing order of the cosine measure by using the file
pointers provided for that purpose.
In the SIRE system, the cosine computations and the ranking algorithms
are completely divorced from the Boolean retrieval operations. Alternatively,
it is possible to give up the Boolean operations completely and process query
formulations expressed simply as sets of weighted query terms. In the
BROWSER system, a file organization substantially equivalent to that shownin Fig. 4-15 is used together with term weights based on an inverse document

150

CHAPTER 4

Figure 4-16

SIRE processing chain.

frequency factor [29]. CITE is another system that uses the conventional in­verted file technology with term weights, document ranking, and relevance
feedback based on the methods described earlier [30].
Another possibility for combining Boolean query processing with term
weighting systems is to allow weighted terms directly as part of the normal
Boolean formulations. Unfortunately, this approach raises a number of difficult
problems, because the normal two-valued logic used to process Boolean
queries assumes that a term is either present in or absent from a document orquery identification. When the Boolean system is extended to include term
weight or importance factors, it becomes necessary to interpret the meaning ofcompound expressions consisting of weighted terms and Boolean operatorssuch as Aa AND Bb, where a,b represent the weights for terms A and B, re­spectively. In so doing one would like to define matching functions that resem­
ble the normal Boolean operations and produce equal output for distinct query
formulations that are logically equivalent [31,32].
It is possible to design retrieval models that furnish unambiguous retrieval
output for weighted Boolean queries. The theory of fuzzy sets provides a modelin which the weight of term k in document i represents the degree to which the
document is a member of the set of documents indexed by the term k [33]. A
weight of 1 then indicates that DOQ is a full member of the document set in-THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

151

dexed by TERMk, a weight of 0 says that the document does not belong to theset, and an intermediate weight designates a partial degree of membership. The
effect of compound Boolean expressions can also be defined in the fuzzy set
model. Whether weighted Boolean queries will ever become popular in re­trieval remains to be seen.
*B Retrieval through Man-Machine Dialogue and Local
Clustering

The previously described relevance feedback process is based on a somewhat
rudimentary type of user-system interaction, because the system generates
query formulations based on relevance assessments returned by the user forpreviously retrieved documents. There exist interactive systems where theuser is expected to take a much more active role in the retrieval operations.
Thus users may be asked to carry out the query reformulations by individuallychoosing good terms for incorporation into the queries; the corresponding
terms may then be chosen from among a set of potentially useful terms dis­played by the system. Users may also be asked to assign positive and/or nega­tive weights to the terms considered for incorporation into the query. Finallythe users may be asked to assign weights (positive or negative) to displayed
documents that may or may not have been retrieved in earlier searches [34].
Relevance judgments can be used as a basis for query reformulation also inconventional retrieval environments where Boolean query statements are used
to retrieve documents manually indexed by keywords. The user feedback pro­
cess devised for the European Community retrieval service consists of the fol­lowing main steps [35]:
1 Relevance assessments are obtained for some of the documents re­trieved in response to an initial search request.
2 The set of terms used to index some of the items known as relevant is
examined [for example, (A AND B AND C AND D) and also (E AND F AND
G)].
3 Some terms from the query statements chosen under step 2 are re­moved so as to broaden the resulting search statements [for example, state­ments (A AND B AND D) and also (E AND F) are constructed].
4 These shortened queries are used as new search statements to retrieve
additional documents; the relevance of some of these newly retrieved docu­
ments is then assessed.
5 For each of the new query statements a “ query quality factor” is com­puted as the ratio between the new relevant items retrieved divided by the newnonrelevant items retrieved.
6 Those partial ^queries with sufficiently high query quality factors arechosen and a final feedback query is constructed by inserting OR connectives
between the corresponding partial query formulations [for example, the newstatement used could be (A AND B AND D) OR (E AND F)].
7 The newly constructed query is used for search purposes, and the pro­
cess is repeated if desired.

152

CHAPTER 4

Additional feedback techniques incorporating slight variations of such a
process can easily be devised.
One of the virtues of the relevance feedback and related query reformula­tion methods is the local nature of the operations involved; normally only thepreviously retrieved documents are used, rather than, the whole document set.
Such considerations lie at the root of a number of local clustering systems de­signed to improve the final search output. A standard inverted file search isused as a fast preliminary step, and the automatic classification procedures pre­viously described then serve to cluster the (local) set of documents retrieved in
response to particular search efforts in the hope of improving the final search
output. The corresponding document classes can be used to determine a spe­cific ranking order in which the output items can be brought to the user’s atten­
tion. By displaying together whole groups of related documents and bringing
them to the user’s attention simultaneously, the choice of new terms to be incor­
porated into a feedback query may also be simplified [36].
Local clustering operations can be applied to terms as well as to docu­
ments. This produces a local thesaurus specifically applicable to each query
which is obtained by grouping terms extracted from previously retrieved docu­
ments. A typical query reformulation process based on local term clusteringmight be carried out as follows [37,38]:
1 Relevance assessments are obtained for certain documents retrieved inearlier search operations.
2 Terms from the documents identified as relevant are ranked in decreas­
ing order of relative frequency (frequency of occurrence in the relevant re­trieved documents divided by total frequency in the collection), and terms withlarge relative frequency are used for query reformulation purposes.
3 Alternatively, or in addition, term similarity coefficients may be ob­tained for pairs of terms occurring in the relevant documents, the size of thecoefficients being dependent on common occurrence patterns in the respective
documents or document sentences.
4 Terms with large enough similarity coefficients are then clustered, andeach original query term is considered as the kernel of a cluster of related terms
to be used for query reformulation purposes.
It is not hard to generate extensions and refinements of the local clustering
operations previously described. Thus local term association procedures can inprinciple also incorporate syntactic considerations where syntactic relation­
ships between terms lead to the generation of term groups [39,40]. Documentgrouping methods, on the other hand, might utilize the similarities not only be­
tween the assigned terms but also between bibliographic citations sharedjointly by a number of documents [41]. As the use of computers for document
processing becomes more widespread, one may expect that the query refine­ment procedures based on user-system cooperation and on local clustering op­
erations will also become more widespread.

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS153

REFERENCES[1] G. Salton, A utom atic Information Organization and R etrieval, M cGraw-Hill B ook
C om pany, N e w Y ork, 1968.
[2] G. Salton, editor, The SM A R T Retrieval S y ste m — Experim ents in A utom atic D o c ­um ent P rocessing, P rentice-H all, In c., E n glew ood C liffs, N e w Jersey, 1971.
[3] G. Salton and M .E . L esk , The SM ART Autom atic D ocum ent Retrieval S ystem — An
Illustration, C om m unications o f the A CM , V ol. 8, N o . 6, June 1965, pp. 39 1 -3 9 8 .
[4] G. Salton, A . W ong, and C .S . Y ang, A V ector Space M odel for A utom atic Index­
ing, C om m unications o f the A C M , V ol. 18, N o . 11, N ovem b er 1975, pp. 61 3 -6 2 0 .
[5] G. Salton and M .E . L esk , Computer E valuation o f Indexing and T ext P rocessing,
Journal o f the A CM , V o l. 15, N o . 1, January 1968, pp. 8 -3 6 .
[6] G. Salton, R ecent Studies in A utom atic T ext A nalysis and D ocu m en t R etrieval,
Journal o f the A C M , V ol. 20, N o . 2, April 1973, pp. 25 8 -2 7 8 .
[7] G. Salton, A N e w Com parison b etw een C onventional Indexing (M E D L A R S) andA utom atic T ext P rocessing (SM A RT), Journal o f the A S IS , V ol. 23, N o . 2, M a rch April 1972, pp. 7 5 -8 4 .
[8] J.B . L ovin s, D evelop m en t o f a Stem ming A lgorithm , M echanical Translation andC om putational L inguistics, V ol. 11, N o . 1 -2 , March and June 1968, pp. 1 1 -3 1 .
[9] A . Tars, Stem m ing as a S ystem D esign C onsideration, A C M SIGIR Forum , V ol.
11, N o . 1, Summer 1976, pp. 9 -1 6 .
[10] G. Salton, C .S . Y ang, and C .T . Y u , A T heory o f Term Im portance in A utom atic
T ext A n alysis, Journal o f the A S IS , V ol. 26, N o . 1, January-F ebruary 1975, pp.
3 3 -4 4 .
[11] K . Sparck Jones, A Statistical Interpretation o f Term Specificity and Its A pplica­tion in R etrieval, Journal o f D ocum entation, V o l. 28, N o . 1, 1972, pp. 1 1 -2 1 .
[12] G. Salton and C .S. Y ang, On the Specifications o f Term V alues in A utom atic In­
dexing, Journal o f D ocum entation, V ol. 29, N o . 4, D ecem ber 1973, pp. 35 1 -3 7 2 .
[13] G. Salton and A . W ong, On the R ole o f W ords and Phrases in A utom atic T ext A nal­
y sis, Com puters and the H um anities, V ol. 10, 1976, pp. 6 9 -8 7 .
[14] G. Salton, E xperim ents in A utom atic Thesaurus C onstruction for Inform ation R e­trieval, Information P rocessing 71, N orth H olland Publishing C om pany, A m ster­
dam , 1972, pp. 115-123.
[15] K . Sparck Jones, A utom atic K eyw ord C lassification for Information R etrieval,
B utterw orths, L ondon, 1971.
[16] G. Salton, D ynam ic Information and Library P rocessing, Prentice-H all In c., E n gle­
w ood C liffs, N e w Jersey, 1975.
[17] W .B . Croft, Clustering Large F iles o f D ocu m en ts U sin g the Single Link M ethod,
Journal o f the A S IS , V ol. 28, N o . 6, N ovem b er 1977, pp. 34 1 -3 4 4 .
[18] R .E . W illiam son, R eal Tim e D ocum ent R etrieval, D octoral T h esis, Cornell U niver­sity, Ithaca, N e w Y ork, June 1974.
[19] Gf, Salton and A . W ong, Generation and Search o f Clustered F iles, ACM Transac­
tions on D ata B ase S y stem s, V ol. 3, N o . 4, D ecem b er 1978, pp. 3 2 1 -3 4 6 .
[20] E. Ide and G. Salton, Interactive Search Strategies and D ynam ic File Organiza­
tion, in T he SM ART R etrieval S y stem — E xperim ents in A utom atic D ocum ent
P rocessing, G. Salton, editor, Prentice-H all, In c ., E n glew ood C liffs, N e w Jersey,
1971, Chapter 16.
[21] J.J. R occh io, Jr., R elevan ce F eedback in Inform ation R etrieval, in T he SM A RT Re-

154

CHAPTER 4

trieval S y stem — E xperim ents in A utom atic D ocu m en t P rocessing, G. Salton, ed i­tor, Prentice-H all, In c., E n glew ood Cliffs, N e w Jersey, 1971, Chapter 14.
[22] G . Salton, D ynam ic D ocu m en t P rocessing, C om m unications o f the A C M , V o l. 15,
N o . 7, July 1972, pp. 6 5 8 -6 6 8 .
[23] T. Brauen, D ocum ent V ector M odification, in The SM A RT Retrieval 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, 1975, Chapter 24.
[24] N .S . M althouse, In d exgen — Index Term Generation H eu ristics, Oak Ridge N a ­tional Laboratory, R eport O R N L-EIS-104, Oak R idge, T en n essee, June 1978.
[25] Inform atics In c ., R A D C A utom atic C lassification O n-Line (R A D C O L )— U se r ’s
M anual, Final T echnical R eport, R om e Air D evelop m en t C enter, R om e, N ew
Y ork, M ay 1975.
[26] T. N oreault, M. K oll, and M .J. M cGill, A utom atic Ranked Output from B oolean
Searches in SIR E , Journal o f the A S IS , V ol. 28, N o . 6, N ovem b er 1977, pp. 333—
339.
[27] M .J. M cGill, L. Sm ith, S. D avid son , and T. N oreault, Syracuse Information R e­trieval E xperim ent (SIRE): D esign o f an O n-Line Bibliographic R etrieval System ,SIGIR Forum , V ol. 10, N o . 4, Spring 1976, pp. 3 7 -4 4 .
[28] M .J. M cGill and T. N oreau lt, Syracuse Inform ation Retrieval Experim ent (SIRE):
R ationale and B asic S y stem D esign , R eport, S ch ool o f Information Stu d ies, Syra­cu se U n iversity, Syracu se, N e w Y ork, M ay 1977.
[29] J.H . W illiam s, B R O W SE R , A n A utom atic Indexing On-Line T ext R etrieval S y s­
tem , IBM Federal S y stem s D ivision Report, Gaithersburg, M aryland, 1969.
[30] T .E . D o szk o cs and B .A . Rapp, Searching M E D L IN E in English: A P rototype U ser
Interface with Natural L anguage Q uery, Ranked Output and R elevan ce F eedback,Proceedings o f the A SIS A nnual M eeting, M inneapolis, M innesota, O ctober 1979,
R .D . Tally, editor, K n ow led ge Industry P ublications, W hite Plains, N e w York,
1979, pp. 131-139.
[31] 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 ol. 29, N o . 3, M ay 1978, pp. 156-158.
[32] W .G . W aller and D .H . Kraft, A M athem atical M odel o f a W eighted B oolean R e­trieval S ystem , Inform ation P rocessing and M anagem ent, V ol. 15, N o . 5, 1979, pp.
2 3 5 -2 4 5 .
[33] A . B ook stein , F u zzy R equests: A n A pproach to W eighted B oolean Search es, Jour­nal o f the A m erican S o ciety for Information S cien ce, V ol. 31, N o! 4, July 1980, pp.
2 4 0 -2 4 7 .
[34] R .N . O ddy, Information 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] V . V ernim b, A utom atic Query Adjustm ent in D ocu m en t R etrieval, Inform ation
P rocessing and M anagem ent, V ol. 13, N o . 6, 1977, pp. 33 9 -3 5 3 .
[36] D .S . B ecker and S.R . P yrce, Enhancing the R etrieval E ffectiven ess o f Large Infor­
m ation System s, IIT R esearch Institute, Report PB 266 008, Chicago, Illin ois, 1977.
[37] R. Attar and A .S . Fraenkel, L ocal F eedback in F ull-T ext R etrieval S y stem s, Jour­nal o f the A CM , V ol. 24, N o . 3, July 1977, pp. 3 9 7 -4 1 7 .
[38] T .E . D o szk o c s, A ID — A n A sso cia tiv e Interactive D ictionary for O n-Line Search­ing, O n-Line R eview , V ol. 2, N o . 2, 1978, pp. 163-173.
[39] D .J. H illm an, C ustom ized U ser Services via Interactions with L E A D E R M A R T ,Inform ation Storage and R etrieval, V ol. 9, N o . 11, 1973, pp. 5 8 7 -5 9 6 .

THE SMART AND SIRE EXPERIMENTAL RETRIEVAL SYSTEMS

155[40] D. Taeuber, CONDOR—Ein Integriertes Datenbank und Informationssystem,
Nachrichten fiir Dokumentation, Vol. 29, No. 3, 1978, pp. 127-130.
[41] H. Small, Cocitation in the Scientific Literature: A New Measure of the Relation­
ship between Two Documents, Journal of the ASIS, Vol. 24, No. 4, July-August
1973, pp. 265-269.
BIBLIOGRAPHIC REMARKS

Many materials dealing with modern information retrieval appear as user man­uals and reports issued by the sponsoring organizations. A summary of many
existing, advanced systems is included in:F. W. Lancaster and E.G. Fayen, Information Retrieval On-Line, Melville Publishing
Company, Los Angeles, California, 1973.
Additional information about the SMART system can be obtained from:
G. Salton, editor, The SMART Retrieval System—Experiments in Automatic Document
Processing, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1971.
Advanced bibliographic retrieval services are also examined in various survey. papers. The following references may serve as a convenient introduction:
D.B. McCarn and J. Leiter, On Line Services in Medicine and Beyond, Science, Vol.
181, July 27, 1973, pp. 318-324.
T.E. Doszkocs, B.A. Rapp, and H.M. Schoolman, Automated Information Retrieval in
Science and Technology, Science, Vol. 208, April 4, 1980, pp. 25-30.
G. Salton, Progress in Automatic Information Retrieval, Computer, Vol. 13, No. 9, Sep­
tember 1980, pp. 41-57.
EXERCISES

4-1 It has been claimed that the generation of ranked retrieval output enhances re­trieval effectiveness and user satisfaction,a Justify the basic argument.
b Contrast the methods used to rank documents at the output in the SMART and
SIRE systems.
c Boolean query formulations and inverted file technologies do not ordinarily
produce ranked retrieval output; describe two methods that are usable to pro­
duce ranked output in a Boolean query environment.
-^•4-2 Relevance feedback and dynamic document space modification are dual opera­
tions: in the former the query formulations are enhanced by using terms from pre­viously retrieved documents, and in the latter the document vectors are altered byusing terms from queries submitted by the user population,a How could relevance feedback and dynamic document space modification be
implemented in a retrieval environment based on Boolean query formulations

156

4-3
4-4

Y-4-5

4-6

CHAPTER 4

and inverted file technologies; prepare a flowchart-like description for both pro­
cesses in the new environment.
b Do you feel that relevance feedback and dynamic document space modification
are well adapted to an inverted file organization? Carefully explain your rea­
sons.
Prepare a program to compute the cosine similarity between a given document andquery [expression (1)] given the file organization for the SIRE system shown in Fig.
4-15.
What is the purpose of cluster splitting during the generation of a clustered docu­
ment collection? In the cluster splitting system represented in Fig. 4-11 a new levelof centroids may be created, thereby causing an upward expansion of the cluster
tree. Can you think of a cluster splitting method in which the cluster hierarchy ex­pands in a downward direction instead of upward? What are the advantages of both
systems of cluster modification for cluster generation and search?
Consider a sample document collection consisting of six documents, each repre­
sented by six terms. Assume that three of the documents are relevant to a given
query and three are nonrelevant. Choose the term weights so as to model the situa­
tions shown in Fig. 4-14a, b, and c, respectively. Compute the centroid vector forthe relevant and the nonrelevant items in each case and show that the distance be­
tween the centroids is largest for the case of Fig. 4-14a and smallest for the situationof Fig. 4-14c. What are the consequences in a relevance feedback system?
What problems arise in implementing a relevance feedback system when a given
query does not succeed in retrieving any relevant items? How could one modify
feedback equation (7) to handle such a situation?