4-1
CHAPTER 4
THE QIIBRY-DOCTMEaJT MATCHING FUNCTION

1. The Comparison of Structural Operands
In selecting references from a library collection, the user
matches his information needs against the disceraable information
content of source documents (or tokens representing them).

In amechanized document retrieval system an analagous process is .
implemented using the formal representations (index transforms) of
the user's information requirements and the content of reference
documents.

It is difficult to characterize precisely the nature of

the comparisons which the user has at his disposal because of therichness in information carrying elements present in the natural
language and because of the complexity of human decision making.

In'automatic systems, however, comparison operations are closely related
to the structure of the data-representations of the compared items.
In an automatic document retrieval system, then, the criteria for
selecting reference documents in response to user queries are directly
related to the data structures produced by the index transformation.
A variety of data structures has been considered for
information representations in document retrieval (see Chapter 2).
Perhaps the simplest of these is the unordered collection of elements
such as results with a keyword representation of document content.
When both the query and document representations are sets from a finite

4-2
collection of keywords, the comparison operation may take a variety offorms, as summarized in Table 4«1«

In general, selection of reference

documents based on an equality match between the query and document
set images is too restrictive for practical consideration.

Partitioninga reference collection into retrieved and rejected subsets by the ..
inclusion relation, however, has been used in many practical retrieval
systems.

In this case selected documents (members of the retrieved

subset R) are defined by:"• - {d^ 1 ^ 3 ,where d. and q are keyword sets, and R is a subset of the source
collection of document images D.

Figure 4*1(b) illustrates this process

for the collection and query of part (a).
In many instances it is desirable to have the response of theretrieval system be an assignment of values to all documents in thecollection, where the values reflect relevance'to the query.

Both theoverlap and metric distance functions are typical of the matching
operations of this type. The overlap coefficient merely measures thenumber of common elements in the two Object sets, whereas the distancefunction (developed by Rial, reference 1) induces a measure with themetric properties of ordinary distance. Figure 4*1,(•. (o.) and^ (d) )provides an illustration of values assigned by each of these comparison
operations.
An extension of the above matching operations on set-.,represented operands can be made by exploiting the isomorphism of a

4-5

•

'•

-

•

.

-

Definition

Comparison Operation

Equality

A - B

a 6 A£=£a 6 B

Inclusion

A C B

a € A^a c B

Overlap Correlation

J0(A,B) - n(A^B)

Metric Distancec£(A,B) - l-4(A.OB)/n(AUB)J\J

V*Comparison Operations on Set Represented Operands
Table 4.1 'Boolean algebra to the partially ordered system formed by the subsetsof the keyword set and the set inclusion relation.

This allows one

to structure the representation of a search request in the form of a
Boolean combination of keywords, i.e. q «w(k.) as opposed to using
an unordered keyword set representation.

Let column i of the keyword

document matrix (Figure 4.1(a)) represent the document subset of theith keyword.

The retrieval.operation, then, consists in generating

the retrieved subset R by replacing each keyword in the Boolean query
polynomial by its keyword set and substituting set intersection for
Boolean !!and" and set union for Boolean "or". With /this transformation
the subset R is specified by:

R -Wf"(K±)

4-4

Keywords.

documents

query

i

b

a
1

f4i
V

c

d

1

3
d
4

1

1

1

1

-—*

1 •

1
1

1

1

1-

1

• 1

<l

,f

1 ''''"1de1a) Query and document keyword images represented by a binary
occurrence matrix.

d

1

d

2 Z>

d

4 4> 4-

.

-$> 1
4.

*

R-{d2, d5]•.

b) Hetrieval by set inclusion matching.

n(qHd)

d,
d

3

d'

n(q H d ) / n ( q O d)

2
3
3
1

d

1

d

?

d
5

d

c) Relevance, values assigned

4

2/5
3/4
5/5
1 /5

d) Relevance values
assigned by metricby overlap correlation.

corr. (1-metric dist.)
Set Image Matching Operations
Figure

4• 1

*

4-5
Figure 4.2 illustrates this process for two Boolean queries and thecollection described in Figure 4.1(a).
Another of the operand structures useful for document andquery representations is the N-dimensional cartesian vector.

Table ..

4.2 characterizes some of the vector comparison operations of interest.
Equality, as in the case of set represented operands, is too :restrictive a criterion for selecting source documents in responseto an input query.

The vector difference assigns a vector quantity .

to each query-document pair, but its magnitude could be a usefulmatching criterion.

In most cases, however, and particularly in thecase of the index images derived by a frequency counting technique(see Chapter 2), the information in the vector image of interest is
contained in the relative magnitude of its components rather than in
their absolute magnitudes. This results from the direct dependenceof the absolute magnitude on the number of words in the input text.
With this assumption, the angular distance function provides the mostsuitable matching operation for vector structured information
representations.
Data representations with structures considerably more
complex than set or vector operands have also been considered for2
automatic document retrieval systems. Hierarchical arrays, .tree
34

structures, and abstract graphs, are among these. With information
representations of these types, matching operations are considerably
more complex than those described above (see for example Sussenguth,reference 4, for a detailed account of graph matching procedures).
The price paid, then, for the additional information which can beq. m h Ac A e

R =
^

•s] n

n { d , ,42'Sl

R - [d2,d}]a)

R e t r i e v a l on the Boolean Polynomial q.-.. •42"

R - j d , ,d 2 d 5 ]
R -

HcAe

eACfVg)<v[KNh]lM/h) Retrieval on the Boolean Polynomial q.? -. eA('.fVg)

Retrieval Operations with Boolean Query Images
Figure 4*2

4-7Comparison Operation•

Definition

Equalitya • b

Vector Differenced - a - 15

Magnitude of the
Vector DifferencecT- 151 - [ X > i - V 2 "* '._Angular Distance

9a. - b. for i » 1fN

-1

-

cos

d. « a. - b. for i - 1,N
1

1

1

a.-b

TTTZT

WW

Comparison Operations on Vector Represented Operands
Table 4.2

carried by these more complex operand structures is the increased costin the required comparison operations necessary to specify a retrieved
subset or to assign a value indicative of document relevance. The
discussion here will be primarily concerned with vector operands;
however, certain of the results derived will be a function not of theoperand structures but of the matching function itself, and will,
therefore, be applicable to matching functions of the type consideredregardless of the operands to which they are applied.

2.

Storage Organization

In principle,* an automatic document retrieval system can be»characterized independently of any parameters of storage organization.
Given a description of the document' and query representations and of

4-8
the matching function used to implement selection or ranking, aretrieval operation is uniquely specified.

Each input query is matchedwith every reference document to specify the retrieved output. Matchinga user's search request against the full store of document index
images exploits, in effect, the maximum capabilities of the system.
Por any by.t limited collections, however, the complexity of effective
matching operations make a full search impractical. Useful retrieval
systems are then required to impose some organization to the document
store so as to limit the scope of the search to a document subset ofmanageable size.
The necessity for storage organisation in fact is likely to
become more stringent as research on automatic document retrieval
progresses. Advances in the techniques of automatic content analysis
are likely to lead to more complex index representations capable ofcarrying more information.

Such index .representations, while allowing

for finer retrieval distinctions necessarily require more time foreach basic comparison operation.

In- addition, the introduction ofoperationally effective time-shared computer systems is likely to
produce significant changes in the organization of document retrieval
systems.

In a real time environment the response time of the system tothe user's demand plays a critical role on overall system performance.
As the time per query-document comparison increases due to increased
information in the index representations, the number of comparisons.possible per unit time decreases. Thus, 'even with the increasing speedof information processing equipment, these factors suggest that some

4-9form of storage organization or document classification will benecessary to achieve economic retrieval from large collections withresponse times fast enough for a real time environment.
Classification may be regarded as a part of the general
problem of content analysis. When a document, is classified undersome given subject heading, its information content has been found to
be related to that area of discourse. A classification system,
however, is rarely used for retrieval in the sense that a user can besatisfied by all the references assigned to some given category.

The

classification schedule in general provides a means of storage
organization which allows a user to limit the scope of his search.

In'this sense the process of document classification is analagous to the
document indexing process. The index image of a document characterizes
the information content of that document while a classification
category normally characterizes the information content of some areaof discourse in the general field of knowledge.

The assignment ofsome set of documents to a category.then.,..in effect, creates an index
image for the information content of the entire set.

The usermatches his information needs against the categories of theclassification system to select subsets of documents in the same way.'in which his search request is matched with individual document
representations to select particular references. Thus in automatic
document retrieval systems, as in conventional library systems,
document classification provides the key for a storage organization
which can effectively limit the number of references which must be
examined in detail in a given retrieved operation.

4-1C

To formalize the effecx of storage organisation on the
document retrieval operation some definitions are required.

In the baseretrieval system (full query-document searching) a total of N
comparison operations are required for each input query, where N is
the number of documents in the reference collection. Let the numberof comparisons required per input query with a classification induced
storage organization be N . The relative search efficiency withcclassification may then be defined as the ratio N/N . Further, assumecthat the document set retrieved with a limited search R is a subset
cof the retrieved set R produced by a full search. This is a naturalconsequence of assuming that the retrieval criterion applied to thequery-document comparisons is the same for both systems. Thus somedocuments which would satisfy the retrieval criterion in a full search
may not be examined in the reduced search mode and therefore cannot bemembers of R • In general, then, there is a cost associated with aclimited search in terms of documents which would be retrieved by afull search but which are not retrieved by the reduced search (membersof the set R-R ).

More precisely, if E L is the document set relevantto the input query, the cost of an increase in search efficiency is afunction of the size of the set D R n(R-R c ), i.e. the number of
relevant documents lost.
Statistically, then, a retrieval system with a classificationinduced storage organization may be characterized by an expected*

R-Ro is defined as £d ± £ R : d ^ a l

4-11
increase in exarch efficiency of ll/Tl where 1! is the average numberccof comparisons required per input query. In addition, an expected
relative lo3s of relevant documents equal to the expectation ofn(B..O(R-E ))/n(2~)
*t

c

xi

will accompany the increase in search efficiency.

If the- relative cost of a query-document comparison is c*, and therelative value of retrieving a relevant document is c. the searchOw>si per input query of the base system may be expressed as:

C g » ^ N - c 2 n(D R OR) ;whereas with reduced searching, the search cost per query is:That system of storage organization which minimizes the expectation of
C f over the population of input queries may be defined as the optimals
reduced search strategy. Further, any reduced search strategy forwhich the expectation of C f is less than the expectation of C, , mayss
be used to provide a net gain to the retrieval system user.
. The above cost expressions are oversimplifications since therelative costs are subjectively variable from user to user and since
the total costs are probably not linear functions as assumed.

But

this formulation provides basic insight into the potential gain
which may be realized from a classification induced storing organization
in a document retrieval system. '4-12

3. Automatic Document Classification

Traditionally the creation of classification schedules aims at
producing a logically consistent, intelligible structuring of human,
knowledge, wherein the organization and structural relations among
subject categories reflect meaningful relations among the. fields of
discourse which they represent.

Research in automatic classification is

generally limited to a much narrower set of goals. In particular,
automatic classification techniques have, in general, been based on thestate or content of a given collection rather than on the state ofknowledge in a given field.

In this sense, then, the object ofautomatic classification has been to generate a set of categories which5
are in some sense optimal for the collection at hand.
The emphasis of this chapter is placed on the relation of
automatic classification to the problem of search optimization in an
automatic document retrieval system.

To this end, then, the basis forestablishing the set of# classification categories of a given collectionis specifically identified with increasing the search efficiency of
retrieval operations.
Previous investigations into the feasibility of automaticclassification have regarded the generation of a set of classification
categories, or the automatic assignment of documents into an existing
5 6classification schedule, or both, as primary goals. 'The interest ...

here, however, is not in the classification system as an end in itself,
7
but rather as an adjunct to an automatic retrieval system.
For -present .
purposes, then, there need be no a priori constraints on the nature of

4-13classification categories. Thus for example, there-may be norequirements for such categories to be intelligible to the users of
the system if, in effect, they are used for purely internal storage
organization.

The tailoring of the classification process to theinternal document searching operations of the retrieval system
offers, then, an increased degree of flexibility which can be
exploited to optimize the overall search strategy.
Tor present purposes, the following assumptions summarize therole of automatic document classification in a mechanized retrieval
system:1 • The discemable information content of source documents
which serve as the basis for classification is containedin the collection of index images to be used for
detailed query-document comparison.
2.

The objective of classification is to induce a storage
organization.which allows a.limited sfcafcch to retrieve. .....
the same documents as would be retrieved by a search of
the full source collection.

3. The characteristics, of the classification should be suchthat it jointly maximizes the search efficiency of thesystem and minimizes the associated loss of relevant J...
documents.
On the basis of these assumpticms it is clear that the natureof the query-document matching function is critical to the' automaticclassification process. In particular, to satisfy the objective

4-H

stated in assumption 2, a classification category should be an equivalence class with respect to the retrieval function.
Let F( be a relation on the set of document images such that4

i* d 3

if and only if every query which retrieves d. also retrieves d..
Assume then that the nature of the query-document matching function issuch that the relation $ defined above is an equivalence relation(reflexive, symmetric, and transitive). Further, let the equivalence .
classes it induces on the document set be identified as classification
categories. Under these circumstances it is necessary only to match«an input query against a single member of each equivalence class, andto retrieve all the members of those classes which satisfy the matching
function.

In this manner, a reduced search retrieves exactly the same

document subset as a full search.
The. only matching functions considered here, which result in
ft being an equivalence relation are set equality for set represented
index images and vector equality for vector index images. The equivalence classes for these comparison operations, however, rre suit \in atrival partition of the reference collection since each class is asingleton. Thus the search on equivalence classes in this case isidentical to a full search over all reference documents.
Consider, for example, the set inclusion matching function forwhich the retrieved set is defined by:

4-15

a - £d.^ : d. 2 i •Consider two document images such that:d^q.

for arbitrary q.

d

and

dg2q

Then ifMd.j.. jL d 2 either:

1 3 d2;ord'2 3 : d 1

;

or

d

1 ^ d 2 and d2^d1

The equality case has already been considered; ahyi;.«Qf t&efothefxLthree;possibilities lead to the existence of, some query which will retrieve .
one but not the other of the documents d1 and dp.

Thus in general,

the relation ^ induced by set .inclusion matching is not an equivalence
relation.
In the case of metric distknce matching (of set or vector
represented index .images), define the retrieved set a by the condition:

a.^d.] : J(q,di)<cT0

Now consider two documents, d,. and d-, such that:cT(a1fd2) - £where £ is the smallest distance possible in terms of the quantization

4-16

employed in the index space. Under these circumstances there always
exists some query q

such that

6 (vV -4
andcf(Vd2)=cf0+£
so that regardless of how close two document images are, they do notbelong to an equivalence class with respect to retrieval unless they are' in fact identical.
Under these circumstances it is clear that in order to reduce
the number of comparisons required in a retrieval operation, it will benecessary to introduce some finite probability of error. Thus, since \the classification categories cannot be identified with equivalenceclasses under matching functions of interest, a limited search strategy
may fail to retrieve some documents which would be retrieved by a fullsearch over the entire collection. The design of a classification
system, then, must involve a tradeoff between the total number ofcomparisons- (search efficiency) and the probability of loss of relevant
documents (versus retrieval by a full search).

4*

Classification and Metric Searching

The two previously considered metric query-document matching'functions did not lead to an equivalence class partition of the :.
reference collection. Metric comparison measures do, however, have a4-18index images as for query images, document-document distance is definedand possesses the same properties of query-document distance. Byvirtue of metric property (iii), the triangle inequality, a searchrequest which is close (related) to a given document d must necessarily
be close to all documents which are themselves close to d.
Let a set of documents D , grouped as a classificationccategory, be confined to a region of the index space such that:

6(d.,o) < X ,X

for all d, € 3>

C •

1

C,

.

where c is an arbitrary vector in this region. Let the distance from aquery q to the vector c be*.

The metric properties of the distance function allowfc the distance
between q and the members of D

to be bounded as follows:• c^(:o,(4-4)]<^(i,a i )<4+cf 0 »for all d.£D . Thus the single distance cKi^c) provides a bound on
1

C

the set of distances from q to the members of the document set D . Thecfollowing discussion is limited to the vector indexing model andangular distance matching with the understanding that it is generally
applicable to any system employing a metric similarity measure. 'In the vector model, docvunent or query index images are treated4-19
as N-dimensional Cartesian vectors. Using the angular distancesimilarity measure, it is clear that a classification category should
consist of a set of document images confined within a localized hypercone of the index space. Alternatively, if the index images are
pictured as unit vectors terminating on the unit N-sphere, aclassification category should consist of a set of documents representedi»g index vectors terminating within some local area on the surface of
the unit N-sphere. In these terms the problem of automatic documentclassification is' to define the characteristics of such areas and toestablish a procedure for identifying and representing them.

5. A Heuristic Classification Algorithm. A.

Basic Concepts
Associated with an' arbitrary set of document index vectors D,

a classification^vector c is defined by the equationn

1 V7 —i.

(4.2)

where D - id,., dp,... -d-r-. The vector c is the centroid or center ofgravity of the set of unit vectors d./|d.| derived from the elementsof D and represents, then, a vector with an orientation for which
n

£-1

4-20

where S is defined according to equation (4.1).

Hie classification .

vector c (or more precisely its orientation) is the best single
representation for all of the elements in the set D under the assumptionthat the information carried by an index vector is contained in its
angular position.
In the geometrical interpretation, the vector c/|c| terminates
at the centroid of the point distribution on the unit.N-sphere
representing the vectors d./|d.| • In particular, then, if the elements
in D are sufficiently close to one another, c must be close to all ofthem. With respect to the classification problem, if the members of D
are to. be grouped into a classification category, c can be considered tobe'the best classification "head" or representation for the category.
This property of the centroid vector together with the metric propertiesof angular query-document matching will be used as a basis for an
automatic classification algorithm suitable for storage organization in
the vector indexing model.

B.

Description of the Classification Algorithm
The objective of the classification process is to generate a

set of categories or document subsists, each represented by a classification vector (equation (4.2)) from the source! collection.

The propertiesof the classification' system should result in increased searchefficiency in a document retrieval system.

The storage organizationinduced by a classification of this type leads to a two-level searchalgorithm.

Consider an input item'which, is. to be compared with eachmember of a collection of N elements so .that those elements which ;4-21
satisfy some comparison criterion may he determined.- Assume further
that the elements can he grouped such that a comparison of the input
item with the representation of each group will determine whether anyof the group members can satisfy the comparison condition. Under thesecircumstances, assuming also that k groups are searched in detail, andthat the groups are of equal size, the^totfcl number of comparisons•frequired, N, may he written:

H t - x + k*|

;

(4.5)

where x is the number of categories and (N/x) is the population ofeach category. Assuming that all elements of the collection haveequal a priori probability of matching an input item, the total
number of comparisons N, is minimized for x - (kN) . Thus in anx
ideal two level storage organization scheme 2(kN)^ comparisons are
required versus N for single level searching.

The variation of N.

with the number of categories (for k-1) is shown in Figure 4*3 on asemi-log plot.

Note that the minimum of the total number ofcomparisons with number of categories in the classification isrelatively broad.
The'foregoing analysis is applicable to the document
retrieval case since all documents can be considered to have equal
likelihood * of being relevant to an arbitrary search request (at leastin the! absence of'any evidence to the contrary).

The classification'categories'should, therefore, contain approximately the same number of
document images. To this end the criteria for identifying a suitable4-23subset of index vectors for category formation are based on the numberof elements in the subset as well as the mutual distance among theelements. Under these conditions a region of the index space with ahigh density of document vectors will*yield categories in which all the
documents are closely related (via the distance function) whereas inregions of relatively*low density, categories covering a wider scope
will be formed.' Note that'as the mutual distance among the members ofa classification category increases, the classification vector becomesless representative of the group as a whole. There is therefore adefinite tradeoff in category formation between producing categories
of equal population on the one hand!, and maintaining control of the
distance relation among category members on the other.
Control of the classification categories is achieved by a setof input parameters to the algorithm which specify:
1•

The number of categories desired.

'2. A lower and upper bound on the number of elements to be
included in any classification subset •3«

An upper bound on the*'distance (lower bound on thecorrelation coefficient) between a document and aclassification'vector such that the document is still
considered to* be associated with that vector.

In the course of the classification process each document may
be associated with one'of'three possible states. Initially, all
documents 'are' coiisidered to be "unclustered", implying that they have
not T)een'assigned to any classification category, nor is anything

4-24

known about their relative position in the index space. As"the processdevelops, a document may become '•clustered11 i.e. associated with aparticular classification vector, or may be identified with the "loose"state indicating that it'has beien found to be oriented in a region of
low density 'in the index space. Unclustered documents are consideredin sequence and the first step "consists in generating a measure of the
distribution of" document'images around the document being considered.
This is accomplished by' correlating this document with all documents"except those which are in the clustered state. The resulting correlation distribution is sorted into descending order (note that thecorrelation is inverse to the angular distance metric), i.e. into orderof increasing distance and a density test is applied to determine if theregion being considered (defined by the object document plus those•unclustered documents in its-immediate vicinity) is dense enough for
category formation.

The density test employed ( a flowchart is given in

Figure 4-4)"requires that the correlation distribution exceed two test
points as illustrated by*Figure 4*5•

Thle test was* chosen heuristicallyafter experimenting with typical document-document correlation
distributions.
If the density test fails, jthe. .document under consideration ismarked "loose" and control returns to step 1 to consider the next
unclustered document.' If' the density test is satisfied, a cutoff
correlation is determined

as a function of the category size limits.and the distribution of' correlation values. The cutoff-determining
algorithm is illustrated in Figure 4*6. As the documents above the4-26

NumberofDocuments

nr
n

i 4-

-

-

—f
4-

0

i

-t-

Correlationa) Hypothetical Doc.-Doc. Correlation Distribution
Showing Density Test Points

N-umberofDocuments

Correlationb) Two Distributions which Pail the Density Test
Graphical Illustration of the Density Test
Figure

4*5

1.0

4-27

j ^—

n2

i j^r— n.. - 1
1^>i . .

i

LEGEM)•

i j-%-| i + 1

J * rank index of cutoff:•

correlation

/

i

i

:

n2

#1^

>'/
>

•

^ 1

:

^min

>f
A

<

<=—

n

i

:

lower bound on
category sizen

2 V

upper bound on
category sizeoPJ

vector of sorted
correlations

J?m±n :•

lowest correlation
always placed above
cutofff^/i -/i+1

A !

>J/

V

,

ist

j

^ i

Program for Specifying Cutoff Correlation
Figure4-6

4-29have been either clustered or marked loose*

Note that as the documents

are clustered,. they are removed from the process of identifying initialcategory subsets. This strategy prevents the generation of classification subsets with large overlap and materially reduces the number ofcorrelations required.

Since it is reasonable to expect that somedocuments shotUd be multiply classified, the classification vectors
are themselves correlated with the'entire collection.

In this manner,

previously clustered documents can appear above the cutoff for agiven classification vector and thus be associated with more than one
category. Figure' 4*7(a) "illustrates a .correlation distribution of
uncrtistered documents which leads to a classification vector (shown in
Figure 4»8(a)')'and part'(b) shows a< part of the correlation
distribution of "this classification vector with the entire collection.
Since there is no a pridri w&y to establish exactly how many categories will be formed by this initial pass through the collection,a second pass is used in case the number formed is less than specified.
(Note that "more than the speqified number of categories could beformed* during'pass'1, but'this would imply that the density test could
be made more restrictive "or that the category size limit could be
increased.) During pass 1, the initial part of the sorted correlation
list for all documents failing the density test is saved on tape. In
pass 2 this list is"scanned*and a meiasure of the unclustered document
density around such documents is computed.

The maximum values of thismeasure" (which is just the sum" of a fixed number of the sorted
correlations; are used "to setect additional classification regions
until the specified number of categories has been formed.

The algorithm

4-31

a)

11

(

1)

39
59

:

4)

: D

(2)

12 ( 1)46 I 3)53 • :

64

13

30

i:

1).

32

:

5)

1)

55

;
i:

1)

57

:

3)

1)

73

i:

1)

:

1)

68 I:

1)

71

80 (: 1.)110 (: 24)

90 I:

1)

91 I:

1)

92 <:

2)

107

i:

1)

119 I:

1)

122 (:

1)

137 <:

3)

142

i;

2)

145 (:

D

149 <:

3)

155 (:

4)

167 <:

1)

173 <:

1)

176 (:
240 (.

1)

196 (:

1)

198 (:

2)

202

(:

1)

209 <:

2)D

252 (:.

1)257 (:

290

(:

1.)

320 <:

1)

522 (

2)

324 (:

9)525 '(:

1)
2)

341

(:

5)

.342

(:

1)

346 (

3)

353

(:

4)

559

(.

2)

360

(.

1)

437

(:

2)

444 (

1)

448

(:

1)

496

(

4)

Classification vector (in condensed format) of the subset of
Figure 4.7 (a). The initial part of the correlation distribution

12 I:

1)

13 <:

2)

16

i:

1)

30

••(

1)

52 I

VJI

of this vector is shown in part (b) of Figure 4»7*

39 i:
59 <:

5)

,46 l:

2). 55 • :i

1)

57

(• 4)

58 <:

1)

1)

68 I:

. 72. i:

1)

90

(

1)

91

(;

1)

92 <:

5)

107 .<:

1)
2)

n o <: 24)

112

(

1)

121

(:

1)

122 I:

1)

137 I:

2)•142 <:

2)

145

(

1)

149 <:

3)

155 <:

5)

167 <:

1)

176 <:

1)

196

(

1)

198 (:

3)

202 (:

2)

209 <:

2)

214 <[

1

240

(

1)

250. (;

1)

252

(:

1)

290 (:

1)

320 <:

1)

321

c

1)

522 (:

3)

324

(:

6).

325

(:

1)

341

3)

342

(

1)

345

(:

2)

346 (
i:
444 (

2)

353 (:

4)

362

(

)

437

(:

5)

2)

487 (:

1)

35? <: 1)
496 (: . 5 )(:b) Classification viScthr of,..th6ipartition class shown in Figure 4*7(c).

The initial part of* the correlation distribution of thisvector is shown in part (d). of Figure 4*7*
Classification Vectors
Figure

4-8

v

4-32
proceeds exactly, as iji. pass 1 except for bypassing the density test. >At
the end of pas's* 2,'.therefore, at least.the required number' of initial.categories have been formed.
It should be clear that at the end of pass 2 not every document
has necessarily been used as an element of a classification subset.
However, those which have not can be assumed to be document images which
are relatively isolated in the index space.' In general there are several
alternatives for dealing with such documents.

In a dynamic environment,

i.e. one in which the collection is growing, there will be new documents
not yet classified.

Isolated documents, then, could be grouped withthese in a 'category which is always searched in detail for all input•queries. At periodic intervals all such documents would be enteredinto the 'classificatibii system with the possibility of generating new
categories as" the size of the collection increases. For .the current
study, however, the elimination of those documents which are in effecthard to classify would bias the evaluation of the overall effectivenessof the technique. The objective here then is to produce a set of
categories suitable for all documents in the test collection.

To thisend a'third pass was incorporated into the classification process.
At the'completion of'pass 2 each source document is assigned •'to'the classification vector with which it has the highest correlation.
• This 'assignment induces a "part it ion of the collection such thatpartition class i contains all documents* which are closer toclassification vector i'than'to any other classification vector.

Inpass 3 each partition class is used as the classification subset for a *new classification vector which will be similar to but not identical

4-33
with the one on which it is based. Each of these final classification
vectors is again correlated'with the "entire document collection todefine the resultant set of categories. At this point a document is, associated with a category if it is above the cutoff of the classification vector of that category, or if it is not above any cutoff but isclosest to said classification vector. Figure 4»7(c) illustrates thepartition class which results in the- classification vector of Figure
4.8(b); the correlation distribution of this vector, which specifies
the final category, is shown in Figure 4.7(d).
At the end of the classification process, then, eachclassification vector represents all the documents with index vectors
within the angular distance correspbnding to its cutoff correlation,
and additionally, a few documents outside this radius. Documents of
the latter jfcype' however, are closer to the vectors to which they are
assigned than to any others' of the set.. Note that the finalclassification vgctors are not necessarily the centroid vectors of thevector subset they represent since the final categories are not ingeneral identical to the partition class from which the centroid
vector was formed.

However, the final categories generally contain themembers of the partition class in addition to documents which are
multiply classified.

This strategy provides a convenient means forgenerating multiple classifications for some documents, while
maintaining a set of categories balanced over the entire collection.
Table 4.3 summarizes the main parts of the classification algorithm"and an overall flowchart is given in Figure 4»9*

1. Identify a dense set of unclustered document images.
2. Form the classification or centroid vector for thissubset.
3* Identify all documents in the vicinity of theclassification vector. Define a category by choosing acutoff, and cluster documents in the category.
Passes 1 and 2• 4.. Partition the source collection on the basis ofassociation with the set of .classification vectors formed
above.
5.

'Form the classification or bentroid vector for eachpartition class.

6. Define the final set of categories for these classification
vectors by correlation with the document collection andcutoff. Assign documents below all cutoffs on the basisof maximum association.
Pass 3

Summary of the Steps of the Classification Algorithm
Table 4*3

4-37
where ncis the number of categories. Assume for simplicity that each.category subset C. contains only documents for which:^Co3}±)<S
where'c. is the representation for C. • The distance from the query q
to any member of the set C. may be bounded by:maxo,tirS0)\<6(l\)<£i+60•

On a probabilistic basis, then, the category for which cT is minimum
is clearly most likely to contain documents close enough to the query
to satisfy the retrieval criterion. Thus the ordering of categories
by increasing query-classification vector distance dictates thesequence in which individual query-document comparisons should beijiadeTo test thfe* characteristics of this system of query-document
searching, the 'classification algorithm was programmed in Fortran andrun on the IBM 7094 to produce several classifications of the document
set of 405 IRE abstracts discussed earliey. Retrieval results based ,on a full "search of this collection for a set of 24 sample searchrequests were available from•previous experiments conducted with the
SMART system.

The objective, then, is to compare the retrieval

characteristics resulting from the classification induced searchsystem to those obtained in the full search mode. Equation (4.3)

4-38
indicates that 20 categories would be about optimal for a collection of
405 documents, (assuming only a single category is searched in detail),
however classifications of 20, 30, and 40 categories were experimentally
produced for comparison purposes. The algorithm required from about 6 J
to 8 minutes, respectively for" these classifications and could
undoubtedly be speeded up if it were repr'ogrammed for this purpose.
Descriptive paramieters of the classifications include the
distributions of the cutoff correlations and the average documentclassification vector correlations which toe shown in Figure 4.10. To
evaluate the effectiveness of the search optimization based on theclassification induced storafee organization, the parameters of interest
are:1.) the consistency of retrieval with respect to all documents,

i.e. does'the reduced search lead to retrieving the same documents as \the full sfearch, and 2.)the" consistency of retrieval with respect torelevant documents, i.e. is the* retrieval of relevant documents alteredby the reduce'd search?

To this end each of-the sample search requests

was correlated with'the set of Classification vectors for the threeclassifications. Figure'4^11'shows the correlation distributions, for *.
one'of the'test queries with the* vectors of each of the classifications.
for each of the classifications (20, 30, and 40 categories) thefiVe highest correlating categories for each query were recorded.

The

documents contained in "the union of the first' through fifth' of such
Categories Vete then compared wittT'the first 15 and first 30 documents .
retrieved by a full search. In addition the 'number of relevant
documents in each of these category*retrieved subsets wa.s computed.
Assuming then that from 1 through 5 categories would be searched in

4-39

40 -L
Average documentclassification vector
correlation

40
category

20 categories - .523
30 categories - .564
40 categories - .596

304

30 !
category

20 4

20category

0)

o

MS-

^5
Correlation

1

Cumulative Frequency Distribution of the Cutoff
Correlation for Three Classifications
Figure

4*10

40

10

T

20 C a t e g o r i e s

150)

n
.2

i n

.4

.8

-6

1.0

Correlation
10 T
30 Categories

I
!

5

4

+

i-

•4

.6

.8

1.0

Correlation
10-

I
I

-40- Categories..

0

in

n
.4

rr

.6

Correlation

Query-Classification Vector Correlation
Distributions for Request "Core Memory"
Figure 4.11

.8

110

4-41

detail'for each query the following parameters could be produced:
1.) The total number of documents in the union of theretrieved categories.
2.) The overlap correlation of the category retrieved subset
with the first 15 and first 30 documents retrieved by afull'search. ' (The*overlap correlation between sets A
and B i s defined by n(AnB)/minimum(n(A),n(B)).)
3«) The category recall or percentage of relevant documentsin the category retrieved subset to the total number of
relevant documents.
4'*) The normal recall or percentage of relevant documents
retrieved to thfe total number of relevant documents,
assuming the same total number of documents retrieved as
contained in the category retrieved subset.
It should be; noted that this method of evaluating theclassification based search is somewhat unfair on two counts. First,
it does not consider the correlation distribution of the searchrequests with the category vectors. Thus when a query has highcorrelation with'only' one or two category vectors, only these should
be searched.

Some queries, however, will not correlate very well withany of the category vectors;, and:.in this case, one should expect tohave to search a larger number of categories in detail to do as well
as a full search. 'Queries of this latter type in effect do not fit
the .classification "structure." Second, the degree of association
between each classificatibri vector and the documents it represents(as reflected by Figure 4*10 is sufficiently small such that a wide4-45
attractive as the collection size increases on-two
counts: first,, because a larger collection should lead
to.better defined categories, and second, because theratio of comparisons required with classification to
the number required with a full search (2Hr/]j) is adecreasing function of :N.

4-46
REFERENCES

1. Rial, J.F., "A Pseudo-Metric for Document Retrieval Systems," Report
W-4595* t^cie Mi-fcre Corporation, Bedford, Mass.
2. Mooers, C.N., "A Mathematical Theory of Language Symbols In Retrieval,"
Proceedings of the International Conference on Scientific
Information, Washington, D.C., 1958
3.

Salton, G., "Manipulation of Trees in Information Retrieval,11Communications of the ACM, Voi. 5t No'.. 2, February 1962

4«

Suss.enguth, E.H., "Structure Matching in Information Processing,",•• Ph.D. Thesis, Harvard University, April 1964
5-

Borko, H. and Bernick, M., "Automatic Document Classification,"
Journal of the ACM, Vol. 10, No. 2, April 1963

6. :.Baker, P., "Information Retrieval Based Upon Latent Class Analysis,"• Journal of the ACM, Vol. 9, No. 4,vOct. 1962
7.

Goffman, W., "A Searching Procedure for Information Retrieval,"
Information Storage and Retrieval, Vol. '2, No. 2, July T964 ,