•'•'••:'./'•'" • : ' - ' ; ' ' : y / ' , 7 ':''•'•••.•;-•. '••••..•"::.;;W> :C;:;K.. ,'

••

--V.

'•

•••;

••

•.

• • ; • •.

.. •1-1r

CHAPTER 1v

•v

.

'.

'•

'-

1. The Document Retrieval Problem
The attention devoted to document retrieval systems in recent

years is based in some form or other on the assumption that such systems
can satisfy needs exhibited by a class of users or can satisfy needs
likely to be exhibited in the near future • Although there is generalagreement that situations requiring reference to some body of accumulated
knowledge do exist in modern society, there is no such consensus as tothe most effective means of satisfying such needs under-the varying setsof circumstances in which they arise* »',*,5V

One of the alternatives

under consideration is the application of automatic information
processing equipment'to the mechanization of reference providing
systems.'7 This report characterizes the basic functions required in such"'•

.

.

'•

•

systems, and develops optimization techniques, applicable to a certainclassof implementations of these functions. In addition the basis forthe evaluation of retrieval system performance is examined and some novel
evaluation criteria are introduced.
In general terms the document retrieval problem can be
introduced with the following assumptions: a body of recorded knowledge ;The references cited in theintroduction are only illustrative andare by no means «xhioMSlblV*#;:-''vJEhe Proceedings of the 195®
International Conference on Scientific Information contains a
number ofpapersdeeding with document retrieval and allied problems.

•'.

1-2

j

exists in the form of a collection of documents (where a document
connotates any segment of natural language text); a population of users
exists with reason to believe that the collection may contain information
pertinent to its needs. The problem, therefore, is in determining if
in fact there are relevant documents (i.e. documents with information
content useful to users) in the collection and in obtaining those which
may be found.

It will be assumed that the determination of theexistence of relevant documents implies their identification and thatsome unspecified means is available for obtaining tokens of such
documents once identified.

In this context it should be'noted that thedocument retrieval problem is considered distinct from the dataproviding or fact retrieval problem.

The information content of adocument in the former is considered an atomic element of the system;
and as such, a document or a set of documents (or unique referents
there to) is provided in response to user demands. But in the dataproviding or fact retrieval problem', specific items of information,e.g. facts, messages, statements, answers to questions, etc., areextracted from source material and provided in response to users1queries. Automatic da1»-pr6vi^ig systems raise a olasB of problems
such as the mechanization of d ^which

are not considered here*
•'•••

:.

-"v

• / ' •.''''"••.'•.:•••• • ' • • '

•

' .

.'

N

•/:'••

2. A Functional Model
Any document retrieval system, automatic or manual, can befunctionally characterized by three basic elements:

••

- .

- V -

1-3s•••>;>•.'•a) the representation of the information content of source
documents, i • e. the indexing function; >b)

the representation of the information needs of the usersof the system, i.e. the search request formulation
function;c) the matching operation between search request
representations and source document representations, i.e. "...
the search or retrieval function.
In addition to this functional characterization, other elements ofdocument retrieval system organization are important in an: operationalframework. Such characteristics as storage organization, input-output
facilities, document acquisition policy, economic factors and others
may be critical in an operational sdnse, but for the purposes of thisreport these will be considered primarily as secondary factors. In
this sense, then, the main purpose here is to consider the logical andmethodological aspects of the mechanization of document retrieved
systems, and in so doing to ignore many of the operational factors
which may be important in other contexts.
The true information content of a document or segment of
natural language text might be defined as existing only in the mind of
its author. The representation of this content in recorded form via
the natural language can be considered aa an attempt at communication.
That in fact such communication is successful on the average might inpart be measured in terms of haaawui progress;1^

information content of a document is a theoretically tenuous concept.

•1-4
In document retrieval, one does not necessarily desire to extract and .
represent the "content11 of a document, hut rather to characterize that
content in a manner whiph can consistently lead to the recovery of its
primary representation, namely the document (the representation of thenatural language).
The first functional aspect of any document retrieval system, 'therefore, involves the means for representing or characterizing the .
information content of source documents. Traditionally, this is theprocess of subject indexing. Useful referents to documents in a
retrieval system may he indicative of attributes other than informationcontent.

In particular, referents such as the authorfs name,-publication date, journal' or publisher identification, cited *10references, etc., can be useful in several contexts.
For the current
purposes, however, those referents not directly indicative ofinformation content'will be ignored with the understanding that theirpractical usefulness to the retrieval process as a whole must be
considered in special circumstances.

Chapter 2 of this study considers

the role of indexing in document retrieval systems. The index function
is discussed in terms of its goals, as well as in terms of thelinguistic aspects of its mechanization, and of the possibilities ofoptimization -of automatic indexing techniques.
The second functional aspect of the retrieval system, "that is
the search request fomrulation, is primarily a user function. In thebroad sense it is also a s ^ t e m ftmction in that a retrieval system
includes the yxsex.

In a narrower sense, however, when the system is1-5
designed to react with the user so as to insure that a given searchrequest becomes an effective representation of the user's informationneeds in terms of the system's capabilities, the request formulation
process xpust be considered a critical system function.

11 12'Chapter

3 develops this premise and considers various means for optimizationof user search requests in terms of system parameters and theobjectives of the retrieval process as a whole.
The third functional aspect of document retrieval relates tothe nature of the matching criteria used to select source documents Ip.
response to a user's input query.

In Chapter 4 the influence ofthe structure of the information representations on the matching
criteria is developed. Major emphasis is placed in this ohapter on
the relation of the matching function to document classification andsearching;' and iti this context an automatic classification algorithm
is developed.

This algorithm is specifically designed to increase

search efficiency and is shown to be applicable to a certain class ofmatching functions.
Chapter 5 considers several aspects of the general problem of
the evaluation of document retrieval systems, particularly as they
relate to the functional model. In addition to examining thestatistical basis for evaluation parameters, some novel measures arederived which have several advantages over those in current use.
Some of the salient features of the SMART automatic document
retrieval system are presented in an appendix. The SN&BT system isused both as a concrete[iiiifoli':9&''-k*: a simulation device for the1-6experiments reported in this thesis.

3. A Specific Model -The SMART System

The experiments results to be presented here in connection
with the optimization and evaluation algorithms were obtained by• simulation, assuming a specific model for a mechanized document
retrieval system.

This model is based on the SMART retrieval systemdeveloped at Harvard University under the direction of Professor Gerard •15Salton. *' The primacy features of those elements of the SMART system ofinterest here are briefly outlined, so that it may become possible torefer to 1;hem in succeeding chapters. A more thorough outline of theSMART system is given in Appendix A.

A.

^.(Property Vector Indexing

Index images of source documents in the experimental system
are assumed to be property vector representations of document content.
For present purposes it is sufficient to assume that the index image ofa reference document is an n-dimensional vector in a property spaoe inwhich the weight or magnitude of a given component (or attribute)reflects the degree to which that attribute characterizes the contentof the source text.

Specifically, the index images experimentally used \were constructed by a thesaurus transformation of the input text. An
attribute of the resulting index space* corresponds to a thesaurus
category (group of semantioally elated natural language terms), andattribute weight is derived from the frequency of occurrence of the

1-7
category terms in the input text.

B. Request Processing

Search requests in the experimental system are introduced into
the computer in the natural language with no format restrictions. The
index language representations of the search requests are identical instructure with those of the reference documents and are derived byapplying thesame transformation rules to the* request text.. It will
be assumed, in general, that a search request is to be interpreted asa description of a single topic area, i.e. a request describing'topics"A" and "B" will be' assumed to be satisfied by documents-dealing withA and B, or with A in relation to B, etc. A user interested indocuments either about A or about B is, by assumption, required tosubmit two search requests. The implications of this assumption are
discussed in more# detail in Chapter 3.
C. Angular. Distance Matching

A retrieval operation in the model system is performed bymatching the index vector representation of the search request with
the index vector representations of all reference documents. The
range of the matching function i6 assumed to introduce at least a•/• • •- . .

• •.•.•••• ••partial order on the reference collection.

••

.

•v.

Since the length or

absolute magnitude of an index vector uttder the assumed index
transforinatioh is a first order function of the length (number ofwords) of the text: w

the contentr.

.

'••

1-8
thereoff a matching function is desired which is independent of thevector magnitudes involved. Under these circumstances it is natural toassume that the information carried by the index vector is contained in
its angular position (i.e. its orientation in the property space)*

The

matching function assumed, therefore, is the angular distance or amono tonic function of this distance between the search request vector
and the source document vector, wherein decreasing distance is assumed
to indicate increasing probability of relevance.

D.

Terminology

In dealing with the foregoing model, the following
definitions are required:
1) L e t & = {D 1 ,D2>...,D 3 represent the set of source
documents in the natural language comprising the referencecollection.
2) Let SI m £ Q . ,Q , •. • 9Q. ^ represent a set of sample searchrequests in the natural language comprising a test set ofretrieval queries.
3) Let T represent the index transformation from the natural' language to the index language. The index image of adocument D . € JS is d.-TC^), and the index image of asearch request Q.€^f is qi»T((4i). Further let ^ { & j t&2': Where alternative models are considered, eug. index images
represented by sets rather than vectors, the required notation
will be introduced following the framework defined here. .

1*9.. • ,d } he the set of source document images andOF f<Lj &of**m^hc\

be the set of query index images*

Let V represent the index language, an n-dimensional
vector space defined as the range of the transformation
T. An index image d may, therefore, he written:

where the d., i - 1 ,n are the scalar weights assigned
to the orthogonal unit vectors v., i - l,n whichconstitute the basis of the index language vector space.
Let M he the search request - source document matohing
function from which the retrieved ordering is derived;
M is then a function ffcom the couple (q,d) q € (%, d 6 D
to the real line.

AREFERENCES

Proceedings of the International Conference on ScientificInformation. 2 Vols., Washington, D.C., 1958.
de Grolier, E., "Problems in Scientific Communication",
IBM Journal of Research and Development. Vol. 2, No. 4, October 1958. ;Bar-Hillel, Y., "The Mechanization of Literature Searching",
Symposium on the Mechanization of Thought Processes. National
Physical Laboratories, Her Majesty's Stationary Office, 1959*Mooers, C.N., "The Next Twenty Years in Information Retrieval,
Proceedings of the Western Joint Computer Conference. March 1959
Kent, A. .Textbook on Mechanized Information Retrieval. .Interscience
Publishers, New York, I963
Oettinger, A.G., "A Bull1 s -eye View of Management Engineering
Information Systems", Proceedings of the ACM National Meeting. 1964
Salton, G., "Progress in Automatic! Information Retrieval", IEEESpectrum. Vol. 8, No. It Jan. 1965
Simmons, R.F., "Answering English Questions by Computer: A Survey",
Communications of the ACM. Vol. 8, No. 1, Jan. 1965
Becker, J.' and Hayes, R. M*, Information Storage and Retrieval:Tools. Elements, Theories. Wiley. New York, 1963
Garfield, E., "Citation'Indexes for Science - A New Dimension inVDocumentation Through Association of Ideas", Science. Vol* 122,No. 3159, JtOy 1955-::.

N1-1.1
11. Rocchio, J. J. and Sal ton, G;,""Information Search Optimizationand Iterative .Retrieval Techniques1.1, AFIPS Conference Proceedings.
Vol. 27, Part 1, Spartan Books, Washington, D.C. 1965
12.

Curtice, R. M. and Rosenberg, V., ftOptimizing Retrieval Resultswith Man - Machine Interaction", Center for the Information
Sciences, Lehigh University, Bethlehem, Pa. 1965

13*Stiles, H. £., "The Association Factor in Information Retrieval11,
Journal of the ACM. Vol. 8 No. 2/April 1961

14.

Le Schack, A. R., "A Note on Measures of Similarity11, Report ISR-7
National Science Foundation,' Harvard Computation Lab., Cambridge, ^Mass., June 1964

15.

Sal ton, G. and LeskV'M.'l!.^ "The SMART Automatic Document
Retrieval System - An Illustration". Comarcmications of the ACM.
Vol. 8, No. 6, June 1965 >•