OneINTRODUCTION

Information retrieval is a wide, often loosely-defined term but in thesepages I shall be concerned only with automatic information retrieval
systems. Automatic as opposed to manual and information as opposed
to data or fact. Unfortunately the word information can be very
misleading. In the context of information retrieval (IR), information, in
the technical meaning given in Shannon’s theory of communication, is
not readily measured (Shannon and Weaver1). In fact in many cases,
one can adequately describe the kind of retrieval by simply substituting‘document’ for ‘information’. Nevertheless, ‘information retrieval’ has
become accepted as a description of the kind of work published byCleverdon, Salton, Sparck Jones, Lancaster and others. A perfectly
straightforward definition along these lines is given by Lancaster2 :‘Information retrieval is the term conventionally, though somewhat
inaccurately, applied to the type of activity discussed in this volume.
An information retrieval system does not inform (i.e, change theknowledge of) the user on the subject of his inquiry. It merely informs
on the existence (or non-existence) and whereabouts of documents
relating to his request.’ This specifically excludes Question-Answeringsystems as typified by Winograd1 and those described by Minsky4 . It
also excludes data retrieval systems such as used by, say, the stock
exchange for on-line quotations.
Many automatic information retrieval systems are experimental. I
only make occasional reference to operational systems. Experimental
IR is mainly carried on in a ‘laboratory’ situation whereas operational
systems are commercial systems which charge for the service they
provide. Naturally the two systems are evaluated differently. The ‘realworld’ IR systems are evaluated in terms of ‘user satisfaction’ and theprice the user is willing to pay for its service. Experimental IR systems
are evaluated by comparing the retrieval experiments with standards
1

INTRODUCTION

specially constructed for the purpose. I believe that a book on
experimental information retrieval, covering the design and evaluationof retrieval systems from a point of view which is independent of any
particular system, will be a great help to other workers in the field andindeed is long overdue.
Many of the tecniques I shall discuss will not have proved themselves
incontrovertibly superior to all other techniques, but they have promiseand their promise will only be realised when they are understood.
Information about new techniques has been so scattered through theliterature that to find out about them you need to be an expert before
you begin to look. I hope that I will be able to take the reader to thepoint where he will have little trouble in implementing some of the newtechniques. Also, that some people will then go on to experiment withthem, and generate new, convincing evidence of their efficiency andeffectiveness.
My aim throughout has been to give a complete coverage of themore important ideas current in various special areas of information
retrieval. Inevitably some ideas have been elaborated at the expense ofothers. In particular, emphasis is placed on the use of automaticclassification techniques and rigorous methods of measurement ofeffectiveness. On the other hand, automatic content analysis is given
only a superficial coverage. The reasons are straightforward, firstly thematerial reflects my own bias, and secondly, no adequate coverage ofthe first two topics has been given before whereas automatic content
analysis has been documented very well elsewhere. A subsidiary reason
for emphasising automatic classification is that little appears to be
known or understood about it in the context of IR so that research
workers are loath to experiment with it.

The structure of the bookThe introduction presents some basic background material, demarcatesthe subject and discusses loosely some of the problems in IR. The
chapters that follow cover topics in the order in which I would think
about them were I about to design an experimental IR system. They
begin by describing the generation of machine representations for the
information, and then move on to an explanation of the logicalstructures that may be arrived at by clustering. There are numerous
methods for representing these structures in the computer, or in otherwords, there is a choice of file structures to represent the logicalstructure, so these are outlined next. Once the information has been
stored in this way we are able to search it, hence a discussion of searchstrategies follows. Lastly, in an experimental situation all of the above
2

INTRODUCTION

will have been futile unless the results of retrieval can be evaluated.
Therefore a large chapter is devoted to ways of measuring theeffectiveness of retrieval. In the final chapter I have indulged in a little
speculation about the possibilities for IR in the next decade.
The two major chapters are those dealing with automatic classifica­tion and evaluation. I have tried to write them in such a way that eachcan be read independently of the rest of the book (although I do notrecommend this for the non-specialist).

Outline
Chapter 2: Automatic Text Analysis—contains a straightforward
discussion of how the text of a document is represented inside acomputer. This is a superficial chapter but I think it is adequate in thecontext of this book.
Chapter 3: Automatic Classification—looks at automatic classification
methods in general and then takes a deeper look at the use of thesemethods in information retrieval.
Chapter 4: File Structures—here we try and discuss file structures fromthe point of view of someone primarily interested in information
retrieval.
Chapter 5: Search Strategies—gives an account of some search strategies
when applied to document collections structured in different ways. It
also discusses the use of feedback.
Chapter 6: Evaluation—here I give a traditional view of the measure­ment of effectiveness followed by an explanation of some of the more
promising attempts at improving the art. I also attempt to provide
foundations for a theory of evaluation.
Chapter 7: The Future—contains some speculation about the future of
IR and tries to pinpoint some areas of research where further work isdesperately needed.

Information retrieval

Since the 1940s the problem of information storage and retrieval has
attracted increasing attention. It is simply stated: we have vast amounts
of information to which accurate and speedy access is becoming evermore difficult. One effect of this is that relevant information gets
ignored since it is never uncovered, which in turn leads to muchduplication of work and effort. With the advent of computers, a great
deal of thought has been given to using them to provide rapid andintelligent retrieval systems. In libraries, many of which certainly have3

INTRODUCTION

an information storage and retrieval problem, some of the moremundane tasks, such as cataloguing and general administration, havesuccessfully been taken over by computers. However, the problem ofeffective retrieval remains largely unsolved.
In principle, information storage and retrieval is simple. Suppose
there is a store of documents and a person (user of the store)
formulates a question (request or query) to which the answer is a set of
documents satisfying the information need expressed by his question.
He can obtain the set by reading all the documents in the store,retaining the relevant documents and discarding all the others. In asense, this constitutes ‘perfect’ retrieval. This solution is obviously
impracticable. A user either does not have the time or does not wish tospend the time reading the entire document collection, apart from thefact that it may be physically impossible for him to do so.
When high speed computers became available for non-numericalwork, many thought that a computer would be able to ‘read’ an entire
document collection to extract the relevant documents. It soon became
apparent that using the natural language text of a document not only
caused input and storage problems (it still does) but also left unsolved
the intellectual problem of characterising the document content. It isconceivable that future hardware developments may make natural
language input and storage more feasible. But automatic characterisa­
tion in which the software attempts to duplicate the human process of‘reading’ is a very sticky problem indeed. More specifically ‘reading’involves attempting to extract information, both syntactic andsemantic, from the text and using it to decide whether each document
is relevant or not to a particular request. The difficulty is not only
knowing how to extract the information but also how to use it todecide relevance. The comparatively slow progress of modern linguistics
on the semantic front and the conspicuous failure of machinetranslation (Bar-HiUel5) show that these problems are largely unsolved.
The reader will have noticed that already, the idea of ‘relevance’ hasslipped into the discussion. It is this notion which is at the centre of
information retrieval. The purpose of an automatic retrieval strategy is
to retrieve all the relevant documents at the same time retrieving as few
of the non-relevant as possible. When the characterisation of adocument is worked out, it should be such that when the document it
represents is relevant to a query, it will enable the document to be
retrieved in response to that query. Human indexers have traditionallycharacterised documents in this way when assigning index terms to
documents. The indexer attempts to anticipate the kind of index terms
a user would employ to retrieve each document whose content he isabout to describe. Implicity he is constructing queries for which the
document is relevant. When the indexing is done automatically it is4INTRODUCTION

assumed that by pushing the text of a document or query through thesame automatic analysis, the output will be a representation of thecontent, and if the document is relevant to the query, a computational
procedure will show this.
Intellectually it is possible for a human to establish the relevance ofa document to a query. For a computer to do this we need to constructa model within which relevance decisions can be quantified. It isinteresting to note that most research in information retrieval can beshown to have been concerned with different aspects of such a model.

An information retrieval system
Let me illustrate by means of a black box what a typical IR system
would look like. The diagram shows three components: input,
processor and output. Such a trichotomy may seem a little trite, but
the components constitute a convenient set of pegs upon which to hanga discussion.
Feedback

I'-------------1

Input

Figure 1.1. A typical IR system

Starting with the input side of things. The main problem here is toobtain a representation of each document and query suitable for acomputer to use. Let me emphasise that most computer-based retrieval
systems store only a representation of the document (or query) whichmeans that the text of a document is lost once it has been processed forthe purpose of generating its representation. A document representative5

INTRODUCTION

could, for example, be a list of extracted words considered to besignificant. Rather than have the computer process the natural
language, an alternative approach is to have an artificial language within
which all queries and documents can be formulated. There is someevidence to show that this can be effective (Barber et al.6). Of course it
presupposes that a user is willing to be taught to express his
information need in the language.
When the retrieval system is on-line it is possible for the user tochange his request during one search session in the light of a sample
retrieval, thereby it is hoped improving the subsequent retrieval run.
Such a procedure is commonly referred to as feedback. An example ofa sophisticated on-line retrieval system is the MEDLINE system(McCarn and Leiter7). I think it is fair to say that it will be only a shorttime before all retrieval systems will be on-line.
Secondly, the processor, that part of the retrieval system concernedwith the retrieval process. The process may involve structuring theinformation in some appropriate way, such as classifying it. It will also
involve performing the actual retrieval function, that is, executing thesearch strategy in response to a query. In the diagram the documents
have been placed in a separate box to emphasise the fact that they are
not just input but can be used during the retrieval process in such a waythat their structure is more correctly seen as part of the retrieval
process.
Finally, we come to the output, which is usually a set of citations or
document numbers. In an operational system the story ends here.
However, in an experimental system it leaves the evaluation to be done.

IR in perspective
This section is not meant to constitute an attempt at an exhaustive andcomplete account of the historical development of IR. In any case it
would not be able to improve on the accounts given by Cleverdon8 andSalton9. Although information retrieval can be subdivided in many
ways, it seems that there are three main areas of research which
between them make up a considerable portion of the subject. They are:content analysis, information structures, and evaluation. Briefly the
first is concerned with describing the contents of documents in a form
suitable for computer processing; the second with exploiting relation­
ships between documents to improve the efficiency and effectiveness of
retrieval strategies; the third with the measurement of the effectivenessof retrieval.
Since the- emphasis^in this book is on a particular approacirto
document representation, I shall restrict myself here to a few remarks

6

INTRODUCTION

about its history. I am referring to the approach pioneered by Luhn1°.
He used frequency counts of words in the document text to determine
which words were sufficiently significant to represent or characterise
the document in the computer (more details about this in the next
chapter). Thus a list of what might be called ‘keywords’ was derived foreach document. In addition the frequency of occurrence of these words
in the body of the text could also be used to indicate a degree ofsignificance. This provided a simple weighting scheme for the ‘key­words’ in each list and made available a document representative in theform of a ‘weighted keyword description’.
At this point it may be convenient to elaborate on the use of‘keyword’. It has become common practice in the IR literature to referto descriptive items extracted from text as keywords or terms. Suchitems are often the outcome of some process such as, for example, thegathering together of different morphological variants of the sameword. In this book keyword and term will be used interchangeably.
The use of statistical information about distributions of words indocuments was further exploited by Maron and Kuhns11and Stiles12
who obtained statistical associations between keywords. These associa­
tions provided a basis for the construction of a thesaurus as an aid toretrieval. Much of this early research was brought together with the
publication of the 1964 Washington Symposium on Statistical Associa­
tion Methods for Mechanized Documentation (Stevens et al. 13).
Sparck Jones has carried on this work using measures of association
between keywords based on their frequency of co-occurrence (that is,
the frequency with which any two keywords occur together in the same
document). She has shown14 that such related words can be usedeffectively to improve recall, that is, to increase the proportion of therelevant documents which are retrieved. Interestingly, the early ideas ofLuhn are still being developed and many automatic methods ofcharacterisation are based on his early work.
The term information structure (for want of better words) covers
specifically a logical organisation of information, such as document
representatives, for the purpose of information retrieval. The develop­
ment in information structures has been fairly recent. The main reason
for the slowness of development in this area of information retrieval isthat for a long time no one realised that computers would not give an
acceptable retrieval time with a large document set unless some logicalstructure was imposed on it. In fact, owners of large data-bases are still
loath to try out new organisation techniques promising faster andbetter retrieval. The slowness to recognise and adopt new techniques ismainly due to the scantiness of the experimental evidence backing
them. The earlier experiments with document retrieval systems usuallyadopted a serial file organisation which, although it was efficient when7

INTRODUCTIONa sufficiently large number of queries was processed simultaneously in abatch mode, proved inadequate if each query required a short real time
response. The popular organisation to be adopted instead was theinverted file. By some this has been found to be restrictive (Saltonls).
More recently experiments have attempted to demonstrate thesuperiority of clustered files for on-line retrieval.
The organisation of these files is produced by an automaticclassification method. Good16 and Fairthorne17 were among the first to
suggest that automatic classification might prove useful in document
retrieval. Not until several years later were serious experiments carriedout in document clustering (Doyle18; Rocchio19). All experiments so
far have been on a small scale. Since clustering only comes into its own
when the scale is increased it is hoped that this book may encouragesome large scale experiments by bringing together many of thenecessary tools.
Evaluation of retrieval systems has proved extremely difficult.
Senko20 in an excellent survey paper states: ‘Without a doubt systemevaluation is the most troublesome area in ISR . . and I am inclined
to agree. Despite excellent pioneering work done by Cleverdon eta l.21
in this area, and despite numerous measures of effectiveness that havebeen proposed (see Robertson22,23 for a substantial list), a general
theory of evaluation had not emerged. I attempt to provide foundations
for such a theory in Chapter 6 (page 117).
In the past there has been much debate about the validity ofevaluations based on relevance judgments provided by erring humanbeings. Cuadra and Katter24 supposed that relevance was measurable on
an ordinal scale (one which arises from the operation of rank-ordering)but showed that the position of a document on such a scale wasaffected by external variables not usually controlled in the laboratory.
Lesk and Salton25 subsequently showed that a dichotomous scale onwhich a document is either relevant or non-relevant, when subjected toa certain probability of error, did not invalidate the results obtained forevaluation in terms of precision (the proportion of retrieved documents
which are relevant) and recall (the proportion of relevant documents
retrieved). Today effectiveness of retrieval is still mostly measured interms of precision and recall or by measures based thereon. There is still
no adequate statistical treatment showing how appropriate significancetests may be used (I shall return to this point in the Chapter on
Evaluation, page 127). So, after a few decades of research in this area
we basically have only precision and recall, and a working hypothesis
which states, quoting Cleverdon26: ‘Within a single system, assumingthat a sequence of sub-searches for a particular question is made in the
logical order of expected decreasing precision, and the requirements arethose stated in the question, there is an inverse relationship between
8

INTRODUCTION

recall and precision, if the results of a number of different searches areaveraged.’

Effectiveness and efficiency
Much of the research and development in information retrieval is aimed
at improving the effectiveness and efficiency of retrieval. Efficiency isusually measured in terms of the computer resources used such as core,backing store, and C.P.U. time. It is difficult to measure efficiency in amachine independent way. In any case it should be measured inconjunction with effectiveness to obtain some idea of the benefit interms of unit cost. In the previous section I mentioned that
effectiveness is commonly measured in terms of precision and recall. I
repeat here that precision is the ratio of the number of relevant
documents retrieved to the total number of documents retrieved, andrecall is the ratio of the number of relevant documents retrieved to thetotal number of relevant documents (both retrieved and not retrieved).
The reason for emphasising these two measures is that frequent
reference is made to retrieval effectiveness but its detailed discussion isdelayed until Chapter 6. It will suffice until we reach that chapter tothink of retrieval effectiveness in terms of precision and recall. It would
have been possible to give the chapter on evaluation before any of theother material but this, in my view, would have been like putting thecart before the horse. Before we can appreciate the evaluation ofobservations we need to understand what gave rise to the observations.
Hence I have delayed discussing evaluation until some understanding ofwhat makes an information retrieval system tick has been gained.
Readers not satisfied with this order can start by first reading Chapter 6
which in any case can be read independently.

Bibliographic remarks
The best introduction to information retrieval is probably got byreading some of the early papers in the field. Luckily many of thesehave now been collected in book form. I recommend for browsing thebooks edited by Garvin27, Kochen28, Borko29, Schecter30 andSaracevic31. It is also worth noting that some of the papers cited in thisbook may be found in one of these collections and be therefore readily
accessible. A book which is well written and can be read without any
mathematical background is one by Lancaster2. A critical view of
information storage and retrieval is presented in the paper by Senko20.
This paper is more suitable for people with a computer science9
IR -2

INTRODUCTION

background, and is particularly worth reading because of its healthy
scepticism of the whole subject. Readers more interested in information
retrieval in a library context should read Vickery32.
One early publication worth reading which is rather hard to come byis the report on the Cranfield II project by Cleverdon et al.21 This
report is not really introductory material but constitutes in my view
one of , the milestones in information retrieval. It is an excellent
example of the experimental approach to IR and contains many goodideas which have subsequently been elaborated in the open literature.
Time spent on this report is well spent.
Papers on information retrieval have a tendency to get published injournals on computer science and library science. There are, however, a
few major journals which are largely devoted to information retrieval.
These are, Journal o f Documentation, Information Storage andRetrieval, and Journal o f the American Society for Information
Science.
Finally, every year a volume in the series Annual Review o f
Information Science and Technology is edited by C. A. Cuadra. Eachvolume attempts to cover the new work published in information
storage and retrieval for that year. As a source of references to thecurrent literature it is unsurpassed. But they are mainly aimed at thepractitioner and as such are a little difficult to read for the uninitiated.

References
1. SHANNON, C. E. and WEAVER, W., The Mathematical Theory o fCommunication, University of Illinois Press, Urbana (1964)
2. LANCASTER, F. Vi .inform ation Retrieval Systems: Characteristics, Testingand Evaluation, Wiley, New York (1968)
3. WINOGRAD, T., Understanding Natural Language, Edinburgh University
Press, Edinburgh (1972)
4. MINSKY, M., Semantic Information Processing, MIT Press, Cambridge,
Massachusetts (1968)
5. BAR-HILLEL, Y., Language and Information. Selected Essays on their
Theory and Application, Addison-Wesley, Reading, Massachusetts (1964)
6. BARBER, A. S., BARRACLOUGH, E. D. and GRAY, W. A. ‘On-line
information retrieval as a scientist’s tool’, Information Storage and Retrieval,
9,429-440 (1973)
7. McCARN, D. B. and LEITER, J., ‘On-line services in medicine and beyond’,
Science, 181, 318-324 (1973)
8. CLEVERDON, C. Vi., ‘Progress in documentation. Evaluation o f information
retrieval systems’, Journal o f Documentation, 2 6 ,5 5 -6 7 (1970)
9. SALTON, G., ‘Automatic text analysis’, Science, 168, 335-343 (1970)
10. LUHN, H. P., ‘A statistical approach to mechanised encoding and searchingof library information’, IBM Journal o f Research and Development, 1,
309-317(1957)

10

INTRODUCTION
11. MARON, M. E. and KUHNS, J. L., 'On relevance, probabilistic indexing andinformation retrieval’, Journal o f the A CM, 7, 216-244 (1960)
12. STILES, H. F., ‘The association factor in information retrieval’, Journal o f
the ACM, 8, 271-279 (1961)
13. STEVENS, M. E., GIULIANO, V. E. and HEILPRIN, L. B., Statistical
Association Methods for Mechanised Documentation, National Bureau ofStandards, Washington (1964)
14. SPARCK JONES, K., Automatic Keyword Classification for Information
Retrieval, Butterworths, London (1971)
15. SALTON, G., Paper given at the 1972 NATO Advanced Study Institute foron-line mechanised information retrieval systems (1972)
16. GOOD, I. J., ‘Speculations concerning information retrieval’, Research
Report PC-78, IBM Research Centre, Yorktown Heights, New York (1958)
17. FAIRTHORNE, R. A., ‘The mathematics of classification’, Towards
Information Retrieval, Butterworths, London, 1-10 (1961)
18. DOYLE, L. B., ‘Is automatic classification a reasonable application of
statistical analysis of text V, Journal o f the ACM, 12, 473-489 (1965)
19. ROCCHIO, J. J., ‘Document retrieval systems-optimization and evaluation’.
Ph.D. Thesis. Harvard University. Report ISR-10 to National Science
Foundation, Harvard Computation Laboratory (1966)
20. SENKO, M. E., ‘Information storage and retrieval systems’. In Advances inInformation Systems Science, (Edited by J. Tou) Plenum Press, New York
(1969)
21. CLEVERDON, C. W., MILLS, J. and KEEN, M., Factors Determining the
Performance o f Indexing Systems, Vol. I, Design, Vol. II, Test Results,
ASLIB Cranfield Project, Cranfield (1966)
22. ROBERTSON, S. E., ‘The parameter description of retrieval tests’, Part 1;
The basic parameters, Journal o f Documentation, 25, 1-27 (1969)
23. ROBERTSON, S. E., ‘The parametric description o f retrieval tests’, Part 2;
Overall measures, Journal o f Documentation, 25, 93-107 (1969)
24. CUADRA, A. C. and KATTER, R. V., ‘Opening the black box of“relevance” ’, Journal o f Documentation, 23, 291-303 (1967)
25. LESK, M. E. and SALTON, G., ‘Relevance assessments and retrieval systemevaluation’, Information Storage and Retrieval, 4, 343-359 (1969)
26. CLEVERDON, C. W., ‘On the inverse relationship of recall and precision’,
Journal o f Documentation, 28, 195-201 (1972)
27. GARVIN, P. L., Natural Language and the Computer, McGraw-Hill, NewYork (1963)
28. KOCHEN, M., The Growth o f Knowledge-Readings on Organisation and
Retrieval o f Information, Wiley, New York (1967)
29. BORKO, H., Automated Language Processing, Wiley, New York (1967)
30. SCHECTER, G., Information Retrieval: A Critical View, Academic Press,
London (1967)
31. SARACEVIC, T., Introduction to Information Science, P.R. Bowker, NewYork and London (1970)
32. VICKERY, B. C., Techniques o f Information Retrieval, Butterworths,
London (1970)11.