INTRODUCTION

This report contains a number of chapters, each of which can be readindependently. For a number of practical reasons we decided to present thereport in this form, rather than to impose an artificial continuity bysubstantial rewriting. Dr David Harper, formerly a research student of vanRijsbergen, was a co-author of Chapter 2, which is to be published inInformation Processing and Management. Chapter 6 will be published inProgram, and Chapter 3 in the Proceedings of the BCS-ACM Conference on
Research and Development in Information Retrieval held in Cambridge in June,
1980.
The aim of the project, broadly speaking, was to investigate methods ofpredicting which terms would be useful in searching and how useful theywould be. To some extent both van Rijsbergen and Robertson had been working
independently on this for several years now, developing and testing
probabilistic models, and using samples obtained by relevance feedback toestimate the usefulness of certain index terms. For some time it was thoughtthat1) the tests were made on inadequate data, and2) the relationship between the Rijsbergen/Robertson probabilistic approachand the Harter 2-Poisson model should be investigated.
The hope was that (2) might lead to a more general probabilistic model, one
which would encompass the 2-Poisson distribution model for the frequency ofoccurrence of terms within documents.
To meet (1), we established at Cambridge a test collection of appropriate
size. The original data for this came from the National Physical Laboratory
where, in the sixties, Vaswani and Cameron had created a machine readable
set of abstracts, queries and relevance assessments. The original data andsome of the problems it presented in processing are described in Chapter 1.
There was already a program suite at Cambridge for setting up testcollections, but it was decided to rewrite it, if only for the purpose ofcreating the new NPL test collection. A description of these programs,
together with their use in setting up the NPL test collection, is given in
Chapter 5. In particular, a new suffix stripping program was designed andimplemented as part of the package. This is fully described in Chapter 6.
The NPL test collection, derived from abstracts, was somewhat different fromprevious test collections in that each term had associated with it afrequency count representing the number of times that term occurred in theabstract. This frequency information was needed to investigate the Hartermodel and its relationship with our probabilistic work. Chapter 3 contains abrief description (and introduction) to Harter?s work. One should also look-1-

there for further references. Harter had proposed a 2-Poisson distribution
to model the statistical distribution of content bearing words. His
original aim was to use these for selecting index terms. Our aim was toinvestigate whether his approach could be incorporated into theRijsbergen/Robertson probabilistic approach and to test whether this would
lead to improvement in retrieval effectiveness. This work constituted ageneralisation of our previous work, since in the past we had been mainly
concerned with binary data, and we wanted to extend our work to frequency
data. The results of this 'marriage1 and its empirical testing can be foundin Chapter 3. Some further theoretical lines of work which, for various
reasons, did not reach any kind of conclusion are discussed in Chapter 4.
As a separate development, Rijsbergen pursued his original work on theusefulness of co-occurrence data. This work required the implementation ofan efficient spanning tree algorithm able to cope with the large data sets.
Porter redesigned an existing algorithm for this purpose and implemented it,
and a description can be found in the Appendix to Chapter 2. With the aid of
this fast spanning tree algorithm, a large number of experiments wereconducted to investigate the effectiveness of query expansion when the extra
search terms are derived from a spanning tree based on a number ofassociation measures. Most of the results of this work are reported inChapter 2. Some negative results are reported in Chapter 3. Some further
theoretical lines of work which, for various reasons, did not reach any kindof conclusion, are described in Chapter 4.
In the course of the project it soon became apparent that to conduct ourexperiments in an organised manner and on the scale required, some highlevel software would be needed. In other words we needed an experimental IR
system able to cope conveniently with the large number of experiments that
we needed to run. Chapter 7 gives a description of what is by now a subsetof the final system written by Porter for this purpose. The software
described in this report (with the possible exception of the spanning treealgorithm) is such that it would not be too difficult to implement it onsome other installation.

Acknowledgements
The work described in this report was carried out under a grant from British
Library Research and Development (grant no. SI/G/300) to Professor M.V.
Wilkes, Computer Laboratory, University of Cambridge. We must thank theUniversity Computing Service for the generous supply of computing resources
over the two year period 1979-1980. Van Rijsbergen was supported by a Royal
Society Research Fellowship throughout the project.
The main collection of data used in the experiments was supplied through Dr
Peter Vaswani of the National Physical Laboratory, Teddington, and we are
greatly obliged to him for making this material available.
We must also thank Dr David Harper and Dr Karen Sparck Jones for their many-2-

suggestions and criticisms throughout the course of this project.
Keith van Rijsbergen
Stephen Robertson
Martin Porter
September 1980-3-