Information Technology: Research and Development (1982), 1 (189-196)© 1982 Butterworths

A PROCEDURE FOR THE ESTIMATION OF TERMSIMILARITY COEFFICIENTS
T. NOREAULT
University o f Pittsburgh, Pittsburgh, Pennsylvania, USAAND

R. CHATHAM
Bolt, Beranek and Newman, Cambridge, Massachusetts, USA(Received 22 December 1981, revised 9 March 1982)

ABSTRACTTerm or document clustering has been shown effective in enhancing theperformance o f information retrieval systems. One barrier to the incor­
poration o f these clustering techniques into operational systems has been
the high cost o f calculating the matrix o f similarity measures. This paper
suggests an approximation procedure which greatly reduces the effort
expended in such calculation. The reduction is accomplished by estimationo f the similarity measures. The procedure results in a substantial reduction
in computational effort and a low error in the estimated similarity
measures.

1. INTRODUCTION
Willett (1981) has demonstrated an efficient technique for the calculation of either
document-document or term-term similarity measures. His algorithm provides
substantial savings over either the brute force approach or a technique suggested by
Croft (1977). The brute force approach requires the calculation of N ( N —l)/2similarity coefficients and is obviously not satisfactory when the N is very large.
Croft pointed out that the vast majority of the coefficients were zero, and suggested
an approach which avoids calculating the zero elements. Utilizing an inverted file
Croft’s algorithm only calculates the similarity coefficients which will be non-zero.
The weakness with Croft’s approach is that some, possibly many (Harding andWillett, 1980), of the coefficients will be calculated more than once. Croft’s
algorithm calculates the similarity measure every time the terms co-occur in aT. Noreault and R. Chatham

J93

If the simplistic scheme described above proved to be unsatisfactory, then one
could use the sampling estimation procedure described earlier. Results given here
will describe the effectiveness of the estimation using samples of size 30 and 60.
These sample sizes were chosen with two considerations in mind:
1. That the sample be large enough that it is likely to be representative.
2. That the number of vectors sampled be small enough that a real reduction ineffort would result from the sampling.
Table 3. Number o f coefficients calculatedin sample
Posting

Sample 30

Sample 60

30-44
45-59
60-199>200

138466(11%)
92887(16%)
263164(54%)
158670 (74%)__—

422962(26%)
248076 (59%)

The first number in each sample pair in Table 3 is the number of coefficients
calculated in the sample. The second is the percentage reduction in the number ofcoefficients this represents from the number which would have been calculated using
Willett’s algorithm. Very substantial savings result from using the estimation
procedure on highly posted terms.
Three consequences can result from the sampling estimation procedure. Coef­
ficients can be assumed to be:
1.
2.
3.
4.

Insignificant when they are actually significant (lost).
Significant when they are actually insignificant (added).
Significant when they are significant (retained).
Insignificant when they are insignificant.

The last of these categories, those coefficients correctly assumed to be insignifi­
cant, accounts for the vast majority of the terms and will not be reported in thetables as it is more meaningful to examine what is happening to the significant
category. The only insignificant terms which are of interest are those which areincorrectly estimated to be significant.
Table 4. Sampling size 30 with 0.1 cutoff
Postings

N o. lost

No. added

N o. retained

30-44
45-59
60-199
>200
Total

128
70
203
719
1120

416
462
4191
9593
14662

625
213
568
1314
2720

The performance of the sampling size of thirty with a cutoff point of 0.1,