2-1;

CHAPTER 2

THE IMDiEJXING FUNCTION

1.

Introduction
*

•

. .

The nature of indexing is examined in this chapter withemphasis on its relation to the document retrieval process. In thiscontext, document indexing may be viewed as a nonreversible (information
lossy) transformation from the natural language to an artificial
language (the index language), suitable for retrieval purposes. The
index transformation is designed in general to accomplish two
objectives: it serves on the one hand to trade amount or quantity of
information for search speed (indexing produces an information
compression), and.on the other hand the index transformation serves alanguage normalization function.

Since indexing produces-information

compression, the index representation of a document can be stored andmanipulated with greater facility than a representation of theoriginal text. The indefx transfdtmation also serves as a language
normalization function in the sense that both vocabulary and stanicturein the index language caxx be controlled, whereas in the natural
language they cannot. The general goal of the indexing function in
the context of document retrieval, then, is.to provide a compact \representation of the information content of source documents (or. arbitrary segments of, natua^

in a controlled format.

2-2

2. Manual Indexing

The increasing emphasis which has been placed in recent years
on coping with the rising flow of technological literature has stimulated
study of the traditional goals and procedures of the various activities
1of documentation and library facilities. The range of services offeredby such facilities is too broad to be considered here.

Since subject

classification and document indexing play a primary role infacilitating the accessibility of recorded knowledge, these faoets of
documentation have been examined with particular care. '?9^f:?

Suchactivities are directly conoemed with the document retrieval problem,
and thus are germane to this discussion; on the other hand, the present
objective is to consider mechanized systems for literature searching..
The theory and methodology of manual indexing must, therefore, largely
be ignored.

In so far as manual indexing is considered as an input

process for mechanized search and retrieval systems, its goals are .
similar to those of automatic indexing.

In this sense, the limitationsof current techniques for linguistic data processing normally dictate •the form and structure of the index language. • Thus the scope of bothmanual and automatic index transfbzmations for mechanized retrieval arelargely the' same and the distinction between' the two is not critical foran examination of the structure of index representations of information
content suitable for mechanized 'processing.

5V Automatic Indexing
The goal of automatic indexing is to develop a set of computer-*2r
based linguistic analysis procedures which provide an effective
representation of the information content of source documents withoutmanual intervention at any stage of the process. Information isconveyed in the natural language by the variety of semantic andstructural constraints implicit in the language. Machine indexing
techniques all depend, in effect, on the automatic recognition ofsome set of the information carrying elements of the natural language,
and on the representation of these elements in a formal structure. In
general, the processes of automatic content analysis can be classified
according to whether they are statistically, semantically, or
syntactically based. A discussion of each classification follows.

A.

The Statistical Approach*

A natural starting point for statistical content analysis
consists in assuming that meaning is principally carried-by the words
used in a document.

Under this assumption a suitable index

transformation consists in mapping a document into an unordered set ofsignificant content bearing words extracted from it. A variety ofstatistical techniques have been proposed and investigated for
determining the most suitable set of content words (keywords) to be
7 8*
used for the encoding.'' typically, such techniques generate afrequency count of word types (ignoring most function words) and theninvoke some frequency sensitive selection process to produce the'document index image. Such procedures can, of course, be extended in
•'•"•

. 9

theory to the detection and counting of word pairs, triples, etc.

2-4There exist obvious problems to such extensions on the practiced level.
An important defect in such an index transformation lies in thefact that the structure of the index image provides no facility for
representing the semantic associations which exist between distinct
word types in the natural language. One proposed for deeding with such
associations on a statistical basis consists in assuming that they can •be derived a posteriori from a set of index images characterizing a
document collection in some given subject area. Thus one can assume,for example, that terms which co-occur in the sentences of a given
document, or in the documents of a given collection, more frequently.
than the average are, in fact, semanticedly as well as statistically
10 11 12
related. ' 9
In the formal associative model, it is possible t&
account for key word associations of higher order than the first andin addition to use these associations to influence query-document
matching procedures. In such a system, a document is represented byits keyword set and additionally by-'.the statisticed properties of therepresentations of all other documents in the collection.
B.

Semantic Techniques
An important edtemative to the statisticed associative

process consists in providing a specific semantic model in the index
transformation directly.

The indexing function may then be implemented"

by a thesaurus mapping containing a pre-defined set of semantice^sociations. A thesaurus transformation may be defined as a many tomany mapping from recognizable word types or phrases to thesaurus

2-5categories or concept codes. Thus a set of semantically associated•natural language terms comprised of synonyms, for example, can hemapped into a single element in the index language; or a single
natural language term which has several connotations can he identified
with a set of elements in the index language (homonyms might betreated in this manner). Figure 2.1 provides an illustration by meansof an excerpt from the'SMART system thesaurus.
The notion of a semantically baaed transformation on a set ofrecognizable (by machine) linguistic features (word or stem types,
phrases, etc.) can be generalized to include a variety of .the13
associations which such elements possess.
The index transformation
may be described in this case by considering a multi-stage mapping. 'The first step consists in mapping the document into the set of basic
elements which describe it, e.g. into the set of word types it contains.
The second step is a transformation from these elements into a spaceof synonymous term groups i.e. into thesaurus categories. (Thethesaurus mapping described above consists in applying these two basic
transformations.) Additional transformation stages may also be defined.
Thus generic (inclusion) relations exist among semantic elements and,these may be used to define a set of hierarchies. A number oftransformation can be defined based on a set of such relations; thus
a term which includes or. which is included by a given term may be
added to or may replace the related term in the document image. The
index image of a document, therefore, can be modified to contain terms
which are generically related to those detected, but not explicitly
present in the input text. Relations among index terms other than

2-6
inclusion relations are also of interest, e.g. cause-effect, processproducts, etc. and these can be used to define additional transformations*
For example, the clause of elements denoting processes can be identified
and the. corresponding products listed. A document image containing aprocess term may then be modified to include the associated product term
' and vice versa.
In summary it is possible, then, to consider semantic index
transformations which include a variety of term associations such that /.
in principle a multiplicity of index representations can be produced
based on the same set of machine recognizable linguistic features. The
problem with such transformations, in general, is that a large numberof a priori semantic associations are possible among the index terms
describing a given document.

The correct associations are dependent on

the context in which the terms are used so that a context free encoding
such as is generally prddubed by machine processing does not necessarily
improve the accuracy of the index representation of information content.

C... iSyntaciiol Techniques
In general both the statistical and semantic procedures
discussed above ignore the information carried by the structural ••constraints of the natural language • It is possible, however, toincorporate a number of syntactic recognition features -into automatic
indexing algorithms*

One obvious use of this kind of information is . .

stem detection, i.e. recognition of the intrinsic association of thevarious' morphological forms of a given word.

Stem detection is readily

*

2-7

Input

Thesaurus

Word

Category

band

$5

50

39
carrier61
channel104

interconnection

516

341

351

"N
Excerpt Prom the SH&RT Thesaurus
Hgure 2.1•V$

2-8
applicable to both statistical and semantic processing since the meaningof a word is generally invariant over its morphological variants. Much:
more ambitious syntactic processing procedures are also under .
investigation, including the use of fully automatic syntactic? analysis.
A full sentence by sentence syntactic analysis could, for example,
provide explicit dependency relations among the various semantic
elements of a sentence, and could be used for phrase recognition or forthe recognition of structurally constrained associations among semantic
terms. At the.present time it* is not clear whether the complexity ..-•••
required for the recognition of complex structural constraints isjustified in terms of the additional information extracted thereby.

4.

The Structure of Index Representations

The index transformation represents a mapping from the natural
language of the source text to the target or index language. The index •image of a source document is thus a representation of the content of
the document in this target language.' The most commonly used index• language structure is the description list, or property vector, inwhich the index: image; consists Of a list of those properties of a finite
set which characterize the document. Index images of this type areused, for example, in Uniterm systems where the document representation
is an unordered set of keywords (descriptors,.uniterms, etc.).

If theproperty set is ordered, for example, by a 1 to 1 mapping' to the set ofIntegers,' the index image may be encoded as a binary vector. A moregeneral/representation of the same type allows for a quantization of the2-9value, or degree, to which each attribute pertains to the document by
associating a scalar with each attribute.

In this case the index

images can be encoded as numeric rather than binary description
vectors.in the attribute space. Table 2.1 illustrates a typical'•; keyword description derived by statistical analysis (from Booth) inwhich the relative frequency of the 15 most frequent non-common word
stem types from a sample document are shown. This analysis can beused to establish a property set index image (by employing a frequency
sensitive selection procedure), a binary description vector, or anumeric description vector incorporating relative frequency information.
Symbolic examples of each of these are illustrated in Figure 2.2.
A property list description does not allow for a direct
representation of any relations among the various attributes, unlessthese are specifically identified in the attribute space. Since
information in the natural language is conveyed by semantic referents(words, phrases)'and by the relations indicated among the referents(syntax and context), index languages capable of explicitly ... V.

representing relations among attributes have been investigated.

A

17
variety of such structures have been studied*. • including.: trpe.and .
graph representations. ' A syntactic dependency tree, for example, canrepresent a natural language sentence by associating its nodes with
'

•

.'

V

the semantic values of the words they represent, and its brancheswith direct syntactic dependency. An example (from Sussenguth) isillustrated in Figure 2. J. While such index structures are capableof more precise modeling of the ixiforraation carrying elements of the.

%

2-10

Word Stem

Relative

Qtype

Frequency

term

• 53

document.28

request

.20

index

.11

profile.11

association.098

generation.086

number.069

related.045

information•045

collection.045

system \m.041 5•

relevance•057

expanded

•037

thin

•033

Word Stem Frequency List of a Sample Documents
Table 2.1*.

The document' characterized is ireferenoe 12.

Keyword Set: £A,B,C 9 D 9 E 9 F 9 G 9 H}a) The Property Space

KeywordRelative
Frequency (Significance)
1

A
B
•

•

:

•

&

3
" ' • .

10.

H .'.:'••:•

5b);. ^Pabular iJtocumJentrRepresentationd - [E9H9B9A]c) Document Image as a Set, d - (1,1,0,0,1,0,0,1)d) Document Image as a Binary Property Yectbr(Keywords in lexical order)d - (1,3,0,0,10,0,6,5)e) Document Image as a numeric Property Vector(Keywords in .lexical order)'V

Alternative Property Space Index Representations:

Pigure 2#2

2-12

i

I

I

i

!•"•

!

i

i

i

'i
i
!
!
j
I
i
i
. j
Eadiation of light waves occurs above the criticaltemperature.

Syntactic Dependency Tree
Figure 2.3

natural language, they necessarily involve text processing algorithms
more costly in terms of complexity and time, in addition to requiring
more storage. The degree to which such index languages justify theiradditional cost in terms of increased retrieval performance is at thepresent time an open question.

5#

Optimizing the Index Transformation

The two major aspects of automatic indexing algorithms are themechanical detection of information carrying elements of the natural :.
language and the representation of these elements in the index
language. To be useful, the recognition procedures must be applicable
to a sufficiently wide class of documents such as will be found in theliterature of some subject specialty. Due to the variations in usage
'

•

.

.

•

•

•

•

'

.

.

•

•

•

-

"

•

.

.

.

•

•

.

-

•

•

•

.

»

'

.

'

.

.

'

'

'

•

•

•

•

•

•

'

'

i

2-13
and linguistic style, and due to the difficulties of extracting
contextual information, any set of properties ohosen to encode theinformation content of documents or search requests in a given fieldmust reflect statistical approximations over the usage of thedetected features. Such a statistical basis is clearly evident
in the statistical association indexing model discussed earlier, where
it forms an explicit part of the index representation.

In various

other indexing-schemes such as manual descriptor indexing, or inmechanized thesaurus indexing, the statistical approximations are, in
effect, hidden in the decision rules incorporated in the index
transformation.

This necessary statistical basis for document

content encoding is emphasized because of its significance in terms of
the problems of generating, maintaining, and evaluating indexing
schemes.
Consider as a concrete example the indexing model
specifically assumed in this report*

The semantic associations

incorporated in the thesaurus mapping from word stems into thesaurus
or concept categories can be established on an ad hoc basis, reflecting
individual or collective value judgments. It is possible, however,to subject these value judgments to experimental verification.
Assume, for example, that a given set of natural language terms
• •..

.

N,

. • _. •(words, phrases, etc.) is mapped into a single attribute of the index
space, i.e. all the elements of the set have been judged to be
sufficiently associated so as to be treated as a unit in the index
language. It is possible, then, to'Examine the occurrence of this

2-14
property in some sample set of document index representations, and to
manually determine from the context of each occurrence in the source
text whether the semantic value assumed in the index transformation, :.
in fact, agrees with that found in the document*

The degree to which

actual usage conforms to the associations assumed in the model can
provide confirmation or suggest changes.
One possibility is to incorporate such statistical evidence
directly into the thesaurus transformation by use of a weighting
scheme. * Consider the mapping shown in figure 2.1. The term ffchannel1'
maps into two categories, one of which, category 30, is associatedwith magnetic disk storage, while the other, category 61, is associatedwith information transmission. On the basis of the statistics of acollection of documents' the a priori probabilities of each of theseusages- can be estimated. Assume that« thejcajegory 30 context occurs
with relative frequency oc and that the category 61 usage occurs withrelative frequency 1-4. The contribution of n occurrences of "channel11
in a document will then contribute an amount k?n*oc to the resultant
weight of category 30 and k*n#(*-l) to category 61 (where k is anarbitrary scaling constant).

In any event, assuming that such a• procedure or its equivalent is carried over a sufficiently large
sample of source text to produce statistically significant correlationof the various associations incorporated into the index transformation, •the index image of a particular document is still at best a good
approximation of what could be produced manually by applying a similar
set of context dependent rules. In other words the noise introduced by

2-15

the statistical approximations necessary in a context independent
framework must necessarily distort the characterization of the
document's content.
This suggests that there aire essentially two alternatives toimproving an already statistioally optimized index transformation.
One method clearly involves the incorporation of context dependent
recognition procedures into the content detection process. In somesense, this is approximated by encoding larger segments of thenatural language text, e.g. phrases instead of words, or sentences
instead of* phrases; Alternatively, context dependence can be
introduced by multi-level recognition procedures in which thedecision rules are altered by global' interpretation of a context
free encoding, thereby producing a second context dependent index
representation.
Consider again a thesaurus transformation of the- typeillustrated in Figure*2.1. Assuming*that all ambiguous input terms(terms which map into more than one thesaurus category) are mapped.,with statistically derived weights as.described above, one can expctot .
" that the correct context will be reinforced over all the term
encodings characterizing the document; whereas the incorrect ones
will not.

The term trchannelV.mapped .as shown in Figure 2.1, isinitially associated with two alternative contexts. After theentire initial encoding is completed, it should be possible to derive
A total score for context "magnetic disk" versus the context
11

information transmission11 by comparing the total weights of all

2-16

categories associated with each of these concepts. . If such an?....• '*>evaluation indicates that one of these alternatives is much more
likely than the other, the individual term mappings can be reweighted
conditioned on this finding. Thus the weight of category 30 due tooccurrences of "channel" might be increased from k*n*o< to k-n if thetotal document encoding indicated that "magnetic storage" was* moreprobable than "information transmission."•

This second encoding iscontext dependent in the sense that a global interpretation of theoverall original index image has been used to modify the termtransformation rules.
The second method of possible optimization which avoids thenecessity of adding context dependent, complexity to the index,
transformation, focuses on'the index images of individual documents.
Consider a document retrieval system in which it is possible to record
effectively the reactions of the users to the responses of the system.
In the course of a retrieval operation the indexing rules of thesystem are evaluated by users in the sense that some retrieved <.
documents * are accepted and others are rejected.' To the extent thatthese* user value judgments reflect the indexing accuracy of the system,
the information they represent can be used to modify the index imagesof the documents in question.
One possible means of implementing such a scheme is by^anindex term weight adjustment algorithm.

Consider a document d^retrieved in response, to a search request with index image q..
>'••••'J

Define.

the set of terms common to d. and i. to be T • If the user judges d.
i

w

^

•*

•

2-17
to be relevant, the weights of all terms contained in T

are promotedin the index image d.; while if ^negative relevance judgment occurs,
the corresponding term weights are decreased.

Over a number of such •.

operations those terms most useful in characterizing the content of
document d. will receive increased significance while terms
representing out of context encodings should receive no net significance 'gain.
The efficiency of such a scheme is open*to question. Clearly,oiiekiw6\ild/wa2itLtha changes^in the index image of a given document toreflect some significant sample of user value judgments, since eachuser brings his own individual biases and viewpoints into the picture.
The rate of adjustment to the index images of documents for a given
topic will then be influenced by the density of search requests for ulthat topic. This implies that'the documents of most interest have thehighest probability of obtaining an improved index representation, afeature which could be desirable. On the other hand, however, aserious drawback of this process lies in the difficulty of improving apoorly indexed document.

Such a document will hardly ever be detected

as being relevant to any user.ls search request so that any evaluations
obtained will be negative ones; While special techniques (such as
calling for manual intervention) anight be employed in this case, it
seems clear that the value of such an optimization process will depend
critically on hbw good the initial index transformation is to begin
w i t h . •:',% • '•• • ::.'.y' '••'•;The question of whether effective operational procedures can

2-18

be devised to implement the optimization of the index images ofparticular documents, in accordance with information obtained bysubjective evaluation of a user population

will require a large

sample of experimental evidence such as can only be obtained in an
operational system environment. The following chapter, however,offers experimental evidence ;that similar techniques are useful forsearch request optimization.

2-19
REFERENCES

1. Proceedings of the International Conference on Scientific
Information, 2 Vols.. Washington, D.C., 1958
2. Perry* &.V*.+ vW&Xwvt'$

A., Tools for Maohine Literature Searching.

Inter science Publishers, New York, 1958
' 5• American University, "Machine Indexing: Progress and Problems,"
Center for Technology and Administration, American University*
February 1961
' 4.

Cleverdon, C , "Interim Report on the Test Programme on an
Investigation into the Comparitive Efficiency of Indexing Systems,1!
College of Aeronautics, Cranfield

5*

Cleverdon, C. and Mills, J., "The Testing of Index Language.Devices," Aslib Proceedings, Vol. 15* No. 4, 1965

' 6. 'Luhn, H.P.y"A Statistical Approach to Mechanized Encoding and
Searching' of Library Information," IBM Journal of Research andDevelopment. Vol* 1, January, and Vol. 4> October 1957
7. Maron,' M.E.,. and Kuhns* J.L;, "On Relevance, Probalistio Indexing
and Information Retrieval,1] Journal of the ACM, Vol. 7, No. 5? *'*- "•July .I960.
8. Maron, M.E., "Automatic Indexing; An Experimental Inquiry/1.
Journal of the'ACM. Vol. 8. No. 5; July 1961•• ;-9#- - Doyle, L.B.,'"The Micro^tatistics ofText," Information Storageand Retrieval. Vol. 1, No. 4, Hov. 1965

2-20

10.

Giuliano, V.E., and Jones, P.E., "Linear Associative Information
Retrieval," Repts. CACL- 1,2,3, Arthur 3). Little, Inc. 1962-1963* 11. Giuliano, V.E., and Jones, P.E., "Linear Associative Information
Retrieval," in Vistas in Information Handling. P. Howerton ed.,* Washington, D.C.; Spartan Books, 1965
12.

Stiles, H.E., "The Association Factor in Information Retrieval,
Journal of the ACM, Vol. 8, No. 2; January 1961

1'3• Salton, G.', "The Identification of Document Content- A Problem in
Automatic Information Retrieval," Harvard Symposium on Digital
Computers and Their Applications, April 1961
'14*

Kuno, S. and Oettinger, A.G., "Multiple-path Syntactic Analyzerj"
Proceedings of the D T P Congress 62. Munich. 1962

15*

Salton, G., and Sussenguth, E.H.Jr.', "Some Flexible Information
Retrieval Systems Using Structure- Matching Procedures,"
Proceedings' of the AFIPS Spring Joint Computer Conference. April.
1964*•16. Booth, A.D. /"Characterizing Documents- A Trial of an Automatic
Method," Computers and Automation. Vol. 14, No. 11, Nov. 1965 •17.' Salton, G. and Sussenguth, E.H., "Some Flexible Informationw

Retrieval Systems Using Structure-Matching Procedures,11 Proceedingsof the AFIPS Spring Joint Computer Conference. April 1964

18.

Sussenguth, E.E., "The Senitenoe Matching Program-Graph," Report ISR-7,
National Science Ffcundation, Harvard Computation Lab, Camb., Mass.,
June 1964; •