A u t o m a t i c P h r a s e I n d e x i n g for D o c u m e n t R e t r i e v a l :An Examination of Syntactic and Non-Syntactic Methods
Joel L. Fagan
Department of Modern Languages and Linguistics andDepartment of Computer Science
Cornell University
Ithaca, New York 14853

Abstract

This study has three objectives: (1) to further investigate thelevel of effectiveness that can be achieved by a simple, non-syntacticphrase indexing strategy based on the term discrimination model,(2) to discuss some problems faced by this non-syntactic phrase
indexing method, and {3) to suggest some solutions to these problems that make use of information about the syntactic structure of
document and query texts.

An automatic phrase indexing method based on the term
discrimination model is described, and the results of retrieval experiments on five document collections are presented. Problems related
to this non-syntactic phrase construction method are discussed, andsome possible solutions are proposed that make use of information
about the syntactic structure of document and query texts.

2. N o n - s y n t a c t i c P h r a s e I n d e x i n g

1. I n t r o d u c t i o n2.1. Phrase Construction Method

In most fully automatic document retrieval systems, where
both content analysis and retrieval are done without human intervention, documents and natural language queries are represented byan unstructured collection of simple descriptors (single words orword stems). Simple descriptors of this kind are not necessarily
ideal content indicators. This is due, at least in part, to the factthat words vary widely in specificity. Some words are highly
specific and therefore identify a narrow range of concepts, whereas
other words are very general and may be associated with a broad
range of concepts. For purposes of document retrieval, neither very
specific nor very general descriptors are ideal, because they retrieve
either too few or too many documents.

The phrase indexing procedure used in the current study isbased on the one proposed by Salton, Yang, and Yu (1975), but it
has been generalized to test certain extensions to their original
method. Because this method has been applied to five comparatively 2arge document collections, and a large number of variations
on the phrase construction process have been tested, the results provide an indication of the level of retrieval effectiveness attainablewith this method that is more realistic than the results reported by
Salton, Yang, and Yu (1975). The phrase construction processdepends on the values specified for five parameters defined as follows:s

In order to improve the quality of an indexing vocabulary, it isoften suggested that phrases be used as descriptors in place of (or in
addition to) excessively general terms (Salton, Yang, and Yu 1975,
Salton 1986, Dillon and Gray 1983). 1' 2 A number of methods havebeen proposed for automatically identifying phrases in the text of
queries and documents. These phrase identification strategies range
in complexity from simple procedures based on word frequencies andcooccurrence characteristics to rather sophisticated methods employing automatic syntactic analysis. Only a few of these methods,
however, have been examined experimentally to determine theirinfluence on retrieval effectiveness. Of those that have been tested
experimentally, the method based on the term discrimination model
has yielded increases in retrieval effectiveness that are among thebest reported to date (Salt, on, Yang, and Yu 1975).

(1) L e n g t h . The maximum number of elements in a phrase. In
these experiments, each phrase contains two elements.

(2) D o m a i n .

Elements of a phrase must occur together in a
specified domain of cooccurrenee. The domain may be a
document (or query) or a sentence.

(3) P r o x i m i t y .

Elements of a phrase must occur within a
specified proximity of one another within the specified domainof eooceurrenee.

(4) D F h . A document frequency threshold for phrase elements is
specified. The document frequency of term t, dft , is definedas the number of documents in which term t occurs at least
once. At least one element of each phrase must meet or
exceed this threshold. This high document frequency element
is called the phrase head.

1 The use of thesaurus classes is also advocated, but the current
discussion is restricted to phrases.

(5) D F p .

A document frequency threshold is specified. This
threshold specifies that the document frequency of the phrase(not its elements) must meet or exceed a specified minimum
value (DFPmin), or be less than a specified maximum value(DFPmax)-

2 Dillon and Gray (1983) discuss this as a problem of ambiguity, but the problems addressed are essentially the same.

s As currently implemented, the phrase indexing procedure allows for substantial flexibility in specifying how phrases are to beconstructed. Only those criteria for phrase construction that are
directly relevant to the current discussion are mentioned here, however. Further details regarding the phrase construction method andanalysis of retrieval results can be found in Fagan (to appear). The
phrase indexing programs are written in C, and have been designed
to interface easily with the SMART package (Buckley 1985).

Permission to copy without fee all or Part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the A C M copyright notice and the title of the publication and its
date appear, and notice is given that copying is by permission of the
Association for Computing Machinery. To copy otherwise, or to republish,
requires a fee a n d / o r specific permission.
© 1987 A C M 0 8 9 7 9 1 - 2 3 2 - 2 / 8 7 / 0 0 0 6 / 0 0 9 1 - - 7 5 ¢91

ACM SIGIR Forum

51

Vol. 51 No. 2, July 2017

The details of the phrase indexing procedure will be clarified
by describing its application to the title of a sample document fromthe CISI collection. Using sentence as the domain of cooceurrence,a proximity of 1, DFh -~ 55, and DFPmin = 1 requires that: (1) theelements of a phrase cooecur in the same sentence, (2) the elements
be adjacent in the document or query text after stopwords are
removed, (3)each phrase contain at least one element having a
document frequency of at least 55, and (4)the phrase occur in atleast one document.
The first step of the indexing procedure is to identify individual word tokens in the text (see Figure 1), remove stopwords, andperform a stemming operation. At the same time, paragraph andsentence boundaries are recognized. The result of this step is illustrated in Figure 2. This information is used as the input to thephrase construction procedure. The column labeled "Phrase Head"in Figure 2 indicates the status of each token with regard to its
acceptability as a phrase head, as determined by its document frequency. Phrase construction proceeds simply by combining phrase
heads with adjacent tokens. For example, in Figure 2, the token
doeu is acceptable as a phrase head, so it is combined with adjacenttokens aesoci and retrief to form phrases docu aseoci and docu
retrief. Similarly, the tokens retrief and system are both acceptable
as phrase heads, and therefore combine to form the phrase retrief
system. The order of phrase elements is regularized so that a pair ofphrases cannot differ by order alone. Also, a phrase descriptor may
not be constructed from two identical elements, so word word is not
assigned as a phrase descriptor, even though the document frequency and proximity requirements for these tokens are met.

2.2. Retrieval E x p e r i m e n t s
The objective of phrase indexing is to identify groups of words
that will enhance retrieval effectiveness when assigned as phrase
descriptors to representations of documents and queries. The nonsyntactic approach to phrase indexing described above attempts todo this by taking into consideration five simple characteristics ofwords in text: (1)phrase length (2)domain of cooccurrence ofphrase elements, (3) proximity of phrase elements, (4) document frequency of phrase elements, and (5) document frequency of phrases.
These characteristics are incorporated into the phrase indexing procedure by specifying values for the parameters defined above. At
the present time, there is no well-motivated basis for selecting
values that can be expected to yield good retrieval results for a particular document collection. Thus in order to establish the level of
retrieval effectiveness that can be attained with this method ofphrase indexing, optimal values must be' determined empirically foreach experimental document collection. A large number of experiments have been conducted in which the phrase indexing procedure
was applied repeatedly, while systematically varying parametervalues. This was done for live document collections: CACM,
INSPEC, CRAN, MED, and CISI. Basic characteristics of these collections appear in Table 1. For each set of values used, a retrieval
experiment was done to compare the effectiveness of simple single
term indexing to that of phrase indexing. In this way, a set ofparameter values was established for each collection that yields
optimal retrieval results for this phrase indexing method. 4
Optimal parameter values for each collection appear in Table
2, together with retrieval evaluation results expressed as percent
change in average precision in comparison to simple single term
indexing. Tables 3 and 4 contain complete recall-precision results.
These tables show that the responses of the test collections to thephrase indexing procedure were quite variable, both with respect tothe level of retrieval effectiveness achieved, and optimal parametervalues. Table 5 presents some additional average precision figures
to illustrate how the different collections behave when identicalparameter values are applied to all of them. These figures represent
the results of only a small sample of the complete series of retrieval
experiments. A variety of values for each phrase construction
parameter have been tested. Experiments were done using bothsentence and document as the domain of cooccurrence. Proximity
values of 1-30, plus unlimited proximity, were tested. A continuumof values for the document frequency of phrase heads and the document frequency of phrases was tested until a clear indication of theeffects that these parameters have on retrieval effectiveness could beperceived.

Figure 3 illustrates the final vector form of document 71. This
vector consists of two subvectors: the single term subvector containing descriptors of type 0, and the phrase suhvector containing
descriptors of type 1. The weighting and similarity functions aredescribed in the appendix.

.I 71
.T
Word-Word Associations in Document Retrieval Systems
FIGURE 1.
Original title of CISI document 71 (Lesk 1969).
Token
word
word
associdocu
retrief_s~stem

Descr
T~'pe
0
0
0
0
0
0

Doc
Nbr
71
71
71
71
71
71

Para
Nbr
1
1
1
1
1
1

Sen
Nbr
1
1
1
1
1
1

Token
Nbr
1
2
3
5
6
7

Doc
Freq
99
99
23
247
296
535

Phrase
Head
YES
YES
no
YES
YES
YES

Characteristics

FIGURE 2.
Input to phrase construction procedure
for the title of CISI document 71.

Document
N__..umber
71
71
71
71
71
71
71
71
71

Descriptor
Number
26546
26850
34344
34406
39899
10365
17459
21114
24244

Weight0.5706
0.21940.73990.24430.13800.17870.23180.65530.4075

Descriptor
Type
0
0
0
0
0
1
1
1
1

Descriptor
associretriefword
docu
systemretrief systemdocu retrief
word associdocu asseciCollections
CACM

INSPEC

CRAN

MED

CIS1

Number ofDocuments

3204

12684

1398

1033

1460

Number ofStem Types

4522

1425.5

3763

6927

5019

Mean Stems
per Document

20.22

30.01

53.13

51.60

45.20

Number of
Queries

52

77

225

30

76

Number ofStem Types

324

576

585

241

657

Mean Stems
per Query

10.67

15.81

9.17

10.10

22.59

TABLE 1.
Statistics for document and query collections indexed withsingle terms, after stemming and stopword removal.
4 It should be emphasized that the results of these experiments
indicate an upper bound on retrieval performance for this indexing
method, since the parameter values were selected to yield optimal
results for these experimental document and query collections.

FIGURE 3.
Final form of vector for the title of CISI document 71.

92

ACM SIGIR Forum

52

Vol. 51 No. 2, July 2017

phrases. Low document frequency phrases ~re excluded by specifying a value for DFPmin, and then assigning phrase p as a descriptor
only if dfp > DFPmin. The largest increase in average precision
was obtained for the MED collection. With DFPmin---- 1 (otherparameter values: domain: sentence, proximity: unlimited,
DFh ~- 1), phrase indexing yielded a change in average precision of+ 3 . 3 % over single term indexing. With DFPmin = 3, thisincreased very slightly to + 4 . 0 ~ A substantial change in average
precision due to exclusion of low document frequency phrases was
obtained only for CACM. With DFPmin = 1 (other parametervalues: domain: document, proximity: unlimited, DFh = 1), phrase
indexing yielded a change in average precision of + 20.1/~o over single term indexing. With DFPmin = 2, this dropped to + 14.0~ fora decrease of 6.19~ In general, excluding phrases with document
frequencies of 3 or less has a very slight positive effect for some collections, and a negative effect for other collections. For all collections tested, as DFPmin is increased above 3, average precision
declines steadily.

The figures in Table 5 show that the domain of cooccurrence
has only a small influence on retrieval effectiveness. With unlimited
proximity, for example, CACIVI has a 20.1% increase in average precision with a domain of document, and a 16.2% increase with adomain of sentence. For CISI the difference is somewhat larger, but
still not great. With more restricted proximity values, varying thedomain of cooccurrence has even smaller effects, and this holds true
for all collections.
Proximity has a substantial influence on retrieval effectivenessfor some collections, and an insignificant influence for others. Using
document as the domain of cooccurrence, CACM shows an increasein average precision of 20.1% with unlimited proximity, and only a
7.GYMincrease with a proximity of 1. This is a difference of 12.5~
For MED, however, the same values yield a difference of only 1.4%
(2.3% vs. G.0%).
The general patterns revealed by testing various values fordomain of cooccurrence and proximity are as follows. Three collections, CACM, INSPEC, and CRAN perform better when the relative location of phrase elements is completely unrestricted (domain:
document, proximity: unlimited). CISI, however, performs best withmaximally restrictive requirements for the relative location of phrase
elements. The behavior of MED is perhaps most similar to that of
CACM, INSPEC, and CRAN, since unlimited proximity is preferred. MED differs from these collections, however, in that adomain of sentence is preferred. For all collections, as the proximity of phrase elements increases, for the most part, gradual changes
in average precision, result. In particular, from a proximity of 5
upward, changes in average precision tend to be small. Since anincrease in proximity causes more phrases to be assigned as descriptors, this suggests that a fairly balanced mix of good and badphrases are added.

The motivation for excluding high document frequency
phrases has to do with the fact that high document frequency
phrases tend to contain high document frequency single terms, andthat high document frequency single terms tend to have a negative
effect on precision. Matches on high document frequency phrases (inaddition to the corresponding single terms) thus tend to emphasize
the negative effect of the high document frequency single terms.
High document frequency phrases are excluded by specifying a value
for DFPmax and then assigning phrase p as a descriptor only if
dfp < DFPmax. A comparison of the best average precision values
for each collection in Table 5 with those in Table 2 reveals that by
excluding high document frequency phrases, small increases in average precision can be achieved. Using values for DFPmax of 90, 150,
90, and 30 for CACM, INSPEC, CRAN, and CISI (respectively},
results in increases in average precision of 0.7~0 to 4.0% over thebest average precision values in Table 5.

Experimentation with a wide range of values for the document
frequency threshold for phrase heads (DFh) has revealed that thisparameter has only a slight influence on retrieval effectiveness. The
largest change in average precision due to this parameter was
obtained for the CISI collection, with DFh = 50 (other values:
domain: document, proximity: 1, DFPmi n = 1). With DFh = 1,
phrase indexing yielded a change in average precision of -2.2% incomparison to single term indexing (see Table 5), whereas with
DFh = 50, the change increased very slightly to - 1 . 5 ~ Other collections showed either decreases in average precision, or evensmaller positive changes with values of DFh greater than one.

Some conclusions can be drawn regarding the general applicability of this phrase indexing method:(1) Though this approach to phrase indexing can have a substantial positive effect on retrieval effectiveness, the method does
not consistently result in substantial improvements ineffectiveness for all collections. This is indicated clearly by
the range of increases in average precision for the five collections: 2 . 2 ~ to 22.79~ According to the criteria suggested by
Sparck Jones (1974: 397), a material improvement is achieved
only by CACM and INSPEC. CRAN and MED show lower
levels of statistically significant improvement, and CISI shows
only a slight, statistically insignificant increase in average

The document frequency threshold for phrases was used to test
the effect of excluding both low and high document frequency

phrases from use as phrase descriptors. The motivation for excluding low document frequency phrases is that phrases that occur in avery small number of documents stand a good chance of simply
being fortuitous cooccurrences of terms rather than meaningful

precision, s

Non-syntactic Phrase Indexing Parameters

Average

Statistically

Precision

Significant

ChangeChange?

Change?

yes

DomainProximity

Phrase Head
Document
Frequency
(DFh}

CACM

document

unlimited1

PhraseDocument
Frequency
(DFp)
< 90

(o.o3.)+ 22.7%yes
P < 0.01

INSPEC

document

unlimited

1

< 150

(o.ol.)+ 11.9%yes

CRAN

document

unlimited1< 90(0.06n)+ 8.9%

iVIED

sentence

unlimited

3*

> 3

CISI

sentence

1

1

< 30

Collection+ 4.0%

P < 0.01
yes
P < 0.01

Material

yes
no

yes

P < 0.01
noP > 0.05

no4- 2.2%
no(0.02.)TABLE 2.
Best parameter values and summary of retrieval results. Average precision change is withrespect to single term indexing; see Tables 3 and 4. The value u is collection size; see Table I.
* This value is a by-product of the threshold for the document frequency of phrases, rather
than an independently specified requirement.

93

ACM SIGIR Forum

53

Vol. 51 No. 2, July 2017

Recall
Level
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.55
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Avg Pree% ChangeI
CACM
Single Term
PhraseIndexing
Indexing
0.57090.76130.55450.73150.50860.64890.48220.59880.43430.53350.50600.40730.36720.45420.3184
0.39110.29720.35690.25730.31990.23980.29710.20640.25720.19120.24160.17260.20890.14620.17190.13230.15410.10860.12610.08600.09090.07110.0742
0.0619O.06240.06100.08150.26040.3195
22.7

Precision
INSPEC
Single Term
PhraseIndexing
Indexing
0.66340.75050.58520.68850.52610.6084
0.5386
0.46280.4181
0.49230.38100.44000.34120.38930.30080.33990.27810.24620.22830.20450.17770.15810.13600.11500.0936
0.06430.04840.02930.01790.24590.30900.27820.24880.21180.19000.16060.13800.11500.09420.06900.05270.03150.01990.275011.9

CRAN
Single Term
PhraseIndexing
Indexin~
0.77580.82060.77580.82060.75260.80010.69000.7362
0.61870.67040.55210.60050.51840.56590.44480.48790.42820.47320.38220.42350.37140.41100.30940.34310.29520.32400.27340.29530.23010.24520.21070.22830.18390.20010.15530.17130.13130.14740.11790.13110.11750.13070.38520.4194
8.9

TABLE 3.
Comparison of single term (stem) indexing and phrase indexing. Phrase indexing parameters
as given in Table 2.

RecallPrecision
MED

Level
0.00
0.05
0.I0
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.55

CISI

Single Term
Indexing
0.92540.88530.8036
0.76200.72580.69640.6742PhraseIndexing
0.95350.90820.85120.80610.78430.7676
O.72220.65630.63170.5956

0.67260.64300.6052PhraseIndexing
0.68380.57690.49470.43850.4026
0.37200.32850.2947
0.27120.25280.23300.2080O.19820.18580.15560.13330.11310.55700.51970.60
0.48180.63
0.44440.70
0.41750.75
0.38710.80
0.35360.85
0.2947
0.09190.90
0.21270.08110.95
0.1286
0.06611.00
0.09700.0582
Avg Prec0.55950.2503~Change
4.0
2.2
TABLE 4.
Comparison of single term (stem) indexing and phrase indexing. Phrase indexing parameters as given in Table 2.

(2)

0.54470.49850.47280.4441"0.40820.38250.35010.29000.20570.12340.08880.5378Single Term
Indexing
0.66560.56230.49190.4366
0.40320.36680.31180.28720.26240.24630.23200.20570.19010.17870.15040.13120.11190.08430.0739 .
0.0801
0.05210.2450A single phrase selection strategy is not effective for all collections. CACM, INSPEC, and CRAN perform beet when very
nnrestrictive phrase selection criteria are employed, that is,with the broadest domain of cooccurrenee, and unlimited dis.-

tance between phrase elements. MED can be grouped with
CACM, INSPEC, and CRAN, since it performs best with theleast restrictive proximity requirement. In contrast, CISI performs best with maximally restrictive phrase selection criteria,
where phrase elements must cooceur adjacently in the samesentence. For all collections, further restrictions on the document frequency of phrases and phrase elements (heads andcomponents) have only a slight effect on retrieval performance.

s The Wilcoxon signed rank test for paired observations wasused to test the significance of the differences between average precision values.

9~

ACM SIGIR Forum

54

Vol. 51 No. 2, July 2017

Proximity OAOM I INSPEC I CRAN
unlimited

0.3128+20.1~

Domain: Document
0.26520.4160•4-7.0°~i +8.2~phrase indexing results to results of single term indexing withweights calculated as a product of term frequency and inverse document frequency (tf×idf). These figures are based on results
reported by Salton and Yang (1973). In comparing phrase indexing
with single term indexing and this better weighting method, theirphrase indexing still shows an increase in average precision, but themagnitude of the increase is much less, ranging between fi% and
20% rather than 17% and 3 9 ~ The tfXidf figures provide a better
point of comparison with the current study, since single term indexing with tfXidf weights is used as the basic point of reference for
evaluating retrieval results.

[ CIS
0.55010.2167+2.3%-I 1.5%0.28030.2546
0.39890.54290.2396+3.5% i +3.6%
+0.9%
-2.2%
Domain: Sentence
0.25340.41050.55550.2320
unlimited
0.3025+ 16.2%+ 3.0%+ 6.6%+3.3~-5.0%
0.2545 i 0.3991
0.54350.240fl0.28081+ 3.5%+ 3.6%+ 1.1%-1.8%+ 7.9%TABLE 5.
Average precision change using identical phrase indexing
parameter values for all collections. Average change iswith respect to single term indexing, see Tables 3 and 4.
The best value for each collection in this table is given in
boldface. Other parameter values are: length 2, DFh: 1,
DFPmin: 1.

1

(3)

(4)

+ 7.6%

A comparison of these results with the figures in Table 2
reveals that Salton, Yang, and Yu's results are comparable to, or
better than, the results obtained in this study. In the present study,
the best average precision increase was 22.7% for CACM. This iscomparable to Salton, Yang, and Yu's result for the MEDLARS collection. The average precision increases obtained for INSPEC and
CRAN are close to the 11% increase obtained by Salton, Yang, andYu for the CRANFlELD collection and their fi% increase for the
TIME collection. The results obtained in this study for CISI and
MED, however, are lower than any of the results obtained by Salton, Yang, and Yu.

Because the domain of cooccurrence and the document frequency of phrases and phrase heads have such a small
influence on retrieval effectiveness, a level of performance thatapproximates the optimal level shown in Table 2 can beachieved by simply disregarding the document frequency anddomain parameters. Thus a very simple approach to phrase
indexing that makes use of only the length and proximity
parameters can be expected to perform reasonably for all collections. For practical purposes, this eliminates the need todetermine acceptable document frequency thresholds experimentally for each collection.

Dillon and Gray (1983) compared a single term indexing procedure using stemming and stopword removal to a syntactic phrase
indexing procedure based on matching sequences of syntactic
categories assigned to text words against a dictionary of patterns ofsyntactic categories. Inverse document frequency {idf) weights andthe cosine similarity function were used for retrieval with bothindexing methods. The two indexing procedures were applied to acollection of 250 library science master's papers and 22 natural
language queries. 7 The phrase indexing procedure proved to beslightly better than the single term procedure as indicated byincreases in precision at most recall levels below 8 0 ~ At 40-60%
recall, the increase in precision ranged between 3% and 7 ~The information about term specificity and relationships
among words in text that is provided by document frequency
and the relative location of words in text does not provide anadequate basis for a phrase indexing procedure that will consistently yield substantial, statistically significant improvements in retrieval effectiveness. This suggests that moredetailed information about text structure and relationships
among words is required. Sections 3 and 4 discuss this idea
further.

These results are not directly comparable to the non-syntacticphrase indexing procedure of the present study, since different collections were used. However, for CACM, INSPEC, and CRAN the
non-syntactic procedure appears to be as good as, or better than,
Dillon's syntax-based procedure. It may be that Dillon's procedure
would yield better results if used as a supplement to a simple single
term indexing procedure rather than as an alternative, since preliminary experiments with non-syntactic phrase indexing have shownthat excluding single term descriptors is detrimental to retrieval performance.

2,3. C o m p a r i s o n w i t h O t h e r P h r a s e I n d e x i n g E x p e r | m e n t sThis section compares the performance of the phrase indexing
procedure described above with four previous experiments in phrase
indexing: Salton, Yang, and Yu's (1975) work based on the discrimination value model, Dillon and Gray's (1983) procedure which isbased on dictionary look-up of syntactic patterns, and CroWs (1986)
and Smeaton's (1980) studies of term dependencies derived manuallyfrom syntactically correct natural language query phrases, s

Croft (1986) and Smeaton (1986) have experimented withmethods of incorporating information about natural language queryphrases into the retrieval process. In both cases, term dependencies
are derived manually from the natural language text of queries, sot h e dependencies correspond closely to syntactically correct natural
language phrases. Dependencies are then incorporated into theretrieval process by increasing the retrieval rank of a particular
document if that document contains the elements of a set of dependent query terms. For Croft, the dependent terms may occur anywhere in the document. Smeaton's cooccurrence requirements arestricter, in that dependent terms must cooccur within a sentence,clause, or phrase in the document text.

The results of Salton, Yang, and Yu's (1975) experiments arepresented in summary form in Table 6. This table contains two setsof comparisons for three small document collections. The row
labeled "tf" compares the average precision attained with simple
single term indexing with term frequency (tf) weights to the resultsof phrase indexing. This is the data provided by Salton, Yang, andYu (1975), and it shows that phrase indexing yields an increase inaverage precision of between 17% and 39% over single term indexing
with tf weights. The row labeled " t f × i d f " compares the same

Both Croft and Smeaton performed retrieval experiments on
the CACbt collection, comparing their term dependency methods tosingle term indexing with idf weights. CroWs single term retrieval
yielded an average precision of 0.2110. After taking into consideration dependent terms, the average precision rose to 0.2270, for an
increase of 7 . 6 ~ s Using a collection of 25 queries, Smeaton's single
term indexing resulted in an average precision of 0.2223. His bests In making comparisons of the kind presented here, it should
be remembered that in general it is difficult to draw firm conclusions
about the relative effectiveness of indexing and retrieval methods
that have been tested in different laboratories or at different times,
since experimental conditions may differ significantly. Document
and query collections differ, and the details of even widely acceptedindexing, retrieval, and evaluation procedures may differ. Nevertheless, it is still instructive to compare experimental results in order to
get a general idea of the relative effectiveness achieved by different
indexing and retrieval methods, provided that the limitations ofsuch comparisons are kept in mind.

7 A third, thesaurus-based procedure was also tested, but its
performance was much worse than the others.
s These figures are based on data in Croft (1980), Table 2, p.
75. Average precision was calculated at recall levels 0.10-0.90.

95

ACM SIGIR Forum

55

Vol. 51 No. 2, July 2017

Single Term
Weighting
Method!

Average Precision
CRANFIELD
424 documents
Single Term
PhraseIndexing
Indexing

MEDLARS450 documents
Single Term
PhraseIndexin$Indexing

TIME
425 documents
Single Term
PhraseIndexin~Indexing

0.54680.67830.4287tf

0.3207+ 32%

0.4158+ 39%

0.5794+ 17%

tfXidf0.3788+ 11%0.4722+ 20%

0.6440+ 6%

TABLE 6.
Comparison of average precision for single term {stem) indexing using two weighting
methods (tf and tf×idf} and Salton, Yang and Yu's phrase indexing method. Percentages
indicate changes in average precision attained by phrase indexing. Figures for the tf weights
are from Salton, Yang, and Yu (1975); those for the t f × i d f weights are based on Saiton andYang (1973).
term dependency method then increased this to 0.2754, for an
improvement of 2 3 . 9 ~ g
In comparing these results to the non-syntactic method of thepresent study, it is important to note that Smeaton and Croft eompared their term dependency results to single term indexing with idf
weights, rather than tfXidf weights. Table 7 compares retrieval
results for the CACM collection for single term indexing using two
different weighting methods, idf and tf×idf. Two different querycollections were tested: (1)the 25 queries used by Smeaton, 1° and(2) the complete collection of 52 queries. Smeaton's 25 queries are asubset of the larger collection. This table shows that single term
indexing with tfXidf weights performs better than single term
indexing with idf weights for both query collections. Using single
term indexing with t f × i d f weights as a point of comparison thus
provides a more demanding basis for evaluating the performance ofa phrase indexing method.

Query
Collection

Single Term Indexing
idf weights

Single Term Indexingt f × idf weights

Smeaton's

0.20790.2230+ 7.3960.21530.2604+ 21.0%25Standard
52

TABLE 7.
Comparison of average precision for the CACM
collection using single term indexing with twoweighting methods and two query collections.
(Precision averages calculated at recall levels 0.100.90.)

As can be seen from Table 8, the non-syntactic phrase indexing procedure yields an increase in average precision of 38.3% oversingle term indexing with t f × i d f weights when applied to Smeaton's
set of 25 queries. For the set of 52 queries, the non-syntactic procedure yields an increase of 22.7% over single term indexing witht f × i d f weights (see also Tables 2 and 3). A clearer indication of thepotential benefits of Croft's and Smeaton's approaches could beobtained by applying their methods to additional document andquery collections.
In summary, it can be concluded that: (1) when applied to the
CACM collection, the non-syntactic procedure yields an increase inaverage precision that is at least competitive with Smeaton's
syntax-based procedure, and better than Croft's method; (2)at its
best, the non-syntactic method exceeds the increases in precisionachieved by Dillon's syntax-based methgd, but on other collections,the performance may be approximately equal, or slightly inferior;and (3) the results obtained by Salton, Yang, and Yu are comparable to some of the results of the present study (CACM, INSPEC,CRANI, and better than others (MED, CISI). The results of thepresent study, however, provide a more realistic indication of thelevel of retrieval effectiveness that can be achieved using a nonsyntactic phrase indexing procedure, since the experiments were performed using more, and significantly larger, document and querycollections than were used by Salton, Yang, and Yu.

Query
Collection

Single Term Indexing
tfX idf weights

Non-syntactic
Phrase Indexing

Smeaton's
25

0.22300.3083+ 38.3%Standard
52

0.26040.3195+ 22.7%TABLE 8.
Comparison of average precision using single term
indexing and phrase indexing for the CACM document collection and two query collections. The
weighting method for phrase indexing is describedin the appendix. Phrase indexing parameter values
are those given in Table 2. (Precision averages calculated at recall levels 0.10-0.90.)
3. Problems with Non-syntactic Phrase I n d e x i n g
In examining large samples of phrases generated by the nonsyntactic procedure and the effect they have on retrieval performance, a number of problems with this procedure have become
apparent. This section discusses a few of these problems. It shouldbe emphasized that examples like the ones given below are not isolated occurrences. Similar cases occur abundantly in the document
and query collections, n Section 3.1 examines several examples ofphrases identified by the procedure that ideally should not be usedas phrase descriptors. Section 3.2 discusses cases in which natural
language phrases that are good indicators of document content can-0 This calculation is based on Smeaton's data for single term
indexing and his phrase indexing method that yields the best average precision figures. The data is given in Smeaton (1086), Table 8,
columns labeled "IDF lJncorrected" and "Corrected 5,10,5,10."
Averages were calculated at recall levels 0.10-0.90.

11 All examples are taken from experimental document andquery collections. The source is given in parentheses after each example. T h a t is, (CISI q12) and (CISI d1340) refer to query 12 anddocument 1340 in the CISI collection.

m I am grateful to Alan Smeaton for providing me with information about the query collection used for his experiments.

96

ACM SIGIR Forum

56

Vol. 51 No. 2, July 2017

not be identified as phrase descriptors due to limitations of the nonsyntactic phrase indexing procedure. For illustrative purposes, this
discussion assumes a relatively restrictive non-syntactic phrase construction strategy using parameter settings such as those given for
the CISI collection in Table 2.

descriptors. The net effect of this phrase descriptor on retrieval performance for CACM is a reduction in average precision.
3.2. F a i l u r e t o Identify Good P h r a s e D e s c r i p t o r sThis section illustrates a common situation in which the nonsyntactic phrase indexing process fails to identify phrase descriptors
that are good content indicators, and that should have a positive
influence on retrieval performance. Whereas simple frequency andproximity criteria often fail to identify useful phrase descriptors,
relatively simple syntactic criteria can be used to successfully recognize many appropriate phrases.

3.1. C o n s t r u c t i o n o f I n a p p r o p r i a t e P h r a s e Deacrlptors
A phrase descriptor may be thought of as inappropriate fortwo general reasons. First, the descriptor may simply not be an
accurate indicator of document or query .content. Second, themeaning of the source text of a phrase descriptor in a query may
differ significantly from the meaning of the source text of a phrase
descriptor in a document.
Phrase indexing consists of two processes: (1) identification ofphrases in text, and (2) normalizing the form of phrases that differ
in structure, but that may be related in meaning. Normalization isbeneficial, since it makes it possible to represent a pair of phrases
like information retrieval and retrieval of information by the single
phrase descriptor inform retrief. Similarly, the phrases book review
and reviews of books can both be represented by the phrase descriptor book review. In non-syntactic phrase indexing, normalization isaccomplished by three devices: (1)stemming, (2)regularizing theorder of phrase elements, and (3) ignoring stopwords that intervene
between content words. All of these devices must be used in orderto accomplish the normalization just illustrated. While normalization has significant benefits, many of the inappropriate phrase
descriptors generated by the non-syntactic phrase indexing process
are the result of excessive normalization.
Seven queries for the CACM collection contain the text phrase
operatin9 system, which yields the phrase descriptor oper system. In
all of these queries, the source of this descriptor is syntacticallycorrect, and the descriptor is a good indicator of document content.
A number of documents contain this descriptor, but many of them
are related only peripherally, if at all, to the topic of operating systems. The phrase descriptor oper system does not correspond to asingle phrase in document and query texts, or even to a set ofphrases closely related in meaning. For example:

Noun phrases involving conjunctions are an important sourceof good phrase descriptors that cannot adequately be identified on a
non-syntactic basis. Consider, for example, the text phrase
parallel and sequential algorithms (CACM q63).
Non-syntactic indexing yields from this the correct phrase sequential
aloorithm, and the meaningless parallel sequential. Syntactic
analysis provides the information that both parallel and sequential
can be understood as modifiers of alyorithrne, thus making it possible to generate two correct phrases, parallel algorithm and sequential
aloorithm, and to avoid the inappropriate phrase identified by thenon-syntactic procedure.
The same strategy can be applied to more complex constructions. For example, from the text phrase
the structure, analysis, organization, storage, searching,
and retrieval of information (CISI d175),the non-syntactic phrase construction process identifies the phrases*structure analysis*storage searching*analysis organization*searching retrieval*organization storage
information retrieval
Five of the six phrases generated are not good indicators of document content; these are indicated by asterisks. In contrast, simple
syntactic information makes it possible to generate
information structure
information storage
information analysis
information searching
information organization
information retrieval,and to avoid constructing all of the inappropriate phrases listed(1) a fully automatic document retrieval system operatino on the
IBM 7094 is described (CACM d1236)(2) to illustrate systems operations and evaluation procedures{CACM d1236)(3) extensive data on the system's operation (CACM d1533)(4) to achieve a system operational within six months(CACM d2380)(5) time between project inception and system operational date
(CACM d1034)(6) critical to the syetem's operating efficiency (CACM d1226)(7) examples of overall system operation (CACM d3087)(8) the system, operated entirely from a digital display unit,
interacts directly with the user (CACM d1695)(9) the system is operational and available on the arpa sdc timeshared computing system (CACM dl170)(10) the system has been in operation (CACM d1665)(11) the COBOL language was used specifically to enable the system to operate on three IBM computers (CACM d1168)(12) the logic required in procedures, operations, syetems, and circuits (CACM d320)(13) examples of the operation of system components(CACM d30871(14) an operational system utilizing this concept (CACM d2919)
115) the duplex operation gives the syetem greater reliability(CACM d252)

above.
The abundanceof constructions of this kind in titles andabstracts is a strong indication that a large number of good phrase
descriptors could be identified using syntactic criteria that could not
be identified on the basis of frequency and cooecurrence criteria
alone. The following section proposes a method for incorporating
information about syntactic relationships among words into thephrase construction process.
4. S y n t a e t l e P h r a s e I n d e x i n g
The objective of syntax-based phrase construction is to use
information about the syntactic structure of document and query
texts to identify relationships among words that will make it possible to construct useful phrases that could not be correctly identified
without syntactic information, and to avoid constructing inappropriate phrases that would be generated with a non-syntactic procedure.
A prototype phrase construction system has been implemented
using PLNLP, t= (Heidorn 1972, 1975) and a broad-coverage computational grammar of English which is also written in PLNLF (Jensen
1086). Based on the structural information produced by this syntactic analysis system, the phrase construction procedure decomposes
complex constructions into simpler forms, while preserving much of
the information about syntactic relationships among words. In
addition, the procedure normalizes the form of constructions thatdiffer syntactically, but that are closely related semantically. Thisis done in such a way that the resulting phrases can be incorporated
directly into the vector representation of documents and queries,
thus maintaining compatibility with the existing retrieval environment.

In all of these examples, the inappropriate document phrase
descriptors are the result of a pair of words that happen to occur inclose proximity in the text, but that nevertheless are not related
syntactically. That is, they do not enter into a relationship ofmodification with one another. The result is a phrase descriptor
that does not accurately reflect the content of the documents, andthat matches with a query descriptor whose source text differs
significantly in meaning from the sources of all of the document

Programming Language for Natural Language Processing.

97

ACM SIGIR Forum

57

Vol. 51 No. 2, July 2017

To illustrate the essential objectives and strategy of thisapproach, consider the following set of natural language phrases:
text analysis
analysis of text
analysis of scientific text
analysis of literary text

noun phrases. The second conjunct has a prepositional phrase
postmodifier that has a conjunction of noun phrases as object. With
noun phrases having this pattern of modification, a number of usefulphrases can be generated by applying the same basic decomposition
procedure. For purposes of phrase construction, the postmodifying
prepositional phrase is treated as a modifier of both elements of the
conjunction preparation and evaluation. Each of the conjuucts ofabstracts and extracts is therefore combined with each of the conjuncts of preparation and evaluation to produce four phrases:
abstracts preparation, extracts preparation, abstracts evaluation, andextracts evaluation.

automatic text analysis
automatic analysis of text
automatic analysis of scientific text
automatic analysis of literary text

All of these phrases are related semantically, having to do with text
analysis. They have several words in common, but differ in syntactic structure. If these phrases occurred in different documents in acollection, and a user submitted a general query containing a phrase
like automatic text analysis, the retrieval system should have thecapability of recognizing some similarity between the query and allof these phrases.

Proceeding into the lower levels of the parse tree, the adjectival premodifier computer-prepared is combined with both elementsof the conjunction abstracts and extracts to produce the phrases
computer-prepared abstracts, and computer-prepared extracts.
Before constructing the final vector representation of the document,each word is reduced to its base form, in order to normalize
inflectional and derivational variants.

Trees (T1) and (T2) are parse trees produced by the syntactic
analyzer. Given this syntactic information, phrases are constructedby simply combining the head of a constituent with the head ofeach constituent that modifies .it. In the parse trees, an asterisk
indicates the head of each constituent. In (T1), the noun analysis is
the head of the complete noun phrase, and it has two premodifiers,
an adjective phrase and a noun phrase. These modifying constructions have the adjective automatic and the noun text as heads. The
modifier automatic is combined with analysis to yield the phrase
automatic analysis. Similarly, text is combined with analysis toyield the phrase text analysis.

Again, by using syntactic information it is possible to avoid
constructing inappropriate phrases like *computer-prepared evaluation, *preparation evaluation, and *abstracts extracts, all of which
would be generated by the non-syntactic procedure.
So far, the phrase construction rules have been implemented
only for generating phrase descriptors from noun phrases. However,work is in progress that will extract phrases from verbal
constructions, and also normalize the form of certain nominal andverbal expressions. For example, in the sentence(T1) automatic text analysis
NP

AJP
NP
NOUN*

ADJ*
NOUN*
analysisautomatic
text

This is a system for a u t o m a t i c a n a l y s i s o f text.
the noun analysis has an adjectival premodifier automatic and a
prepositional phrase post-modifier of text. But in the sentence

Yields: automatic analysis, text analysis

This is a system that a n a l y z e s t e x t a u t o m a t i c a l l y .
the same idea is expressed in a relative clause with text as the objective of the verb analyze, which is modified by the adverb automati.
calln. Normalization of constructions of this kind will further
enhance the phrase indexing procedure.

In (T2), analysis is again the head of the complete nounphrase, and automatic is the head of the premodifying adjective
phrase. In this case, however, text is the head of a prepositional
phrase postmodifier, rather than a noun phrase premodifler.
Nevertheless, the same strategy illustrated for (TI) applies here toconstruct the same two phrases, automatic analysis and text
analysis. Within the prepositional phrase, scientific is the head ofan adjective phrase modifying text, so this head and modifier combine to form scientific text. Note also that the incorrect phrase*scientific analysis is not produced, since these words are not related
as head and modifier. This incorrect phrase would be generated by
the non-syntactic procedure.

The phrase construction procedure as outlined here is clearlyin need of refinements and extensions. One of the most obvious
problems that must be dealt with is the structural ambiguity ofcomplex noun phrases. Though it is not possible to resolve ambiguities of this kind given syntactic information alone, examination ofsample document and query texts indicates that it should be possible to develop rules for phrase construction that will deal adequately
with a large proportion of eases. After a more fully developed set ofphrase generation rules are in place, retrieval experiments will be
conducted to compare the level of effectiveness achieved by nonsyntactic phrase indexing with that of the approach to syntacticphrase indexing outlined here.

(T2) automatic analysis of scientific text
NP

AJP
NOUN*
PP

ADJ*
analysis
PREP
AJP
NOUN*

automatic
of
ADJ*
text

scientific

6. Summary and Conclusion
The automatic phrase construction procedure based on relative
location of phrase elements and on term specificity (as indicated by the document frequency of phrases and phrase elements) does not consistently yield substantial improvements inretrieval effectiveness when applied to five experimental document collections. Thus it is not likely that phrase indexing of
this kind will prove to be an important method of enhancing
the performance of automatic document indexing and retrieval
systems.
(2) Even though the non-syntactic method does not consistently
perform well, when applied to the CACM collection, it yields
improvements in retrieval effectiveness that are at least competitive with Croft's and Smeaton's methods that are based onsyntactically correct natural language phrases from queries.
This unexpected result may be due, at least in part, to thefact that those methods do not take into consideration syntactic relationships among words in documents. The examples
discussed in section 3.1 show clearly that simple cooccurrence
in a document of the elements of a syntactically correct queryphrase does not guarantee the presence of a document phrasethat is closely related in meaning to the query phrase. Manyof the inappropriate phrase matches that occur with the non(1)Yields: automatic analysis, text analysis, scientific text
Avoids: *scientific analysis
By applying this procedure of decomposition and normalization to the eight natural language phrases listed above, they can all
be represented by some combination of the following four simpler
phrases:
Modifier H e a dtextscientific
literary
automatic

analysis
text
text
analysis

After application of a stemming operation, these phrases would be
included as elements of the phrase subvector.
Tree (T3) is a more complex noun phrase that further illustrates the benefits of using syntactic information for phrase construction, is This is a noun phrase that consists of two conjoined
is Additional examples were presented in Fagan (1985).

98

ACM SIGIR Forum

58

Vol. 51 No. 2, July 2017

(T3) the preparation and evaluation of computer-prepared abstracts and extracts (CISI d6).
NP

DET
NP
CON J*
NP

ADJ*
NOUN*
and
NOUN*
PP

the
preparation
evaluation
PREP
of
NP
AJP
NOUN*
CON J*
and
NP
NOUN*

ADJ*
abstracts

computer-prepased

extracts

Yields: abstracts preparation, extracts preparation, abstracts evaluation, extracts evaluation
computer-prepared abstracts, computer-prepared extracts
AtJoid~: *computer-prepared evaluation, *preparation evaluation, *abstracts extracts

syntactic method are therefore likely to occur with Smeaton'sand Croft's methods as well. Thus in order to take full advantage of the possible enhancements that syntactic information
might provide, it appears that syntactic relationships amongwords in both queries and documents must be taken into consideration.

(3)

(4)

Acknowledgments
I am indebted to Gerard Salton for the advice he has provided
in planning and carrying out these experiments, and for his comments on a number of drafts of this paper. The help that Chris
Buckley and Ellen Voorhees provided in implementing the nonsyntactic phrase indexing software, and their advice on otheraspects of this work are greatly appreciated. I am also grateful to
George E. Heidorn and Karen Jenscn of IBM Thomas J. Watson
Research Center for providing the facilities and background required
to develop the syntax-based phrase indexing system.

The automatic syntactic phrase construction process outlined
in section 4 is capable of overcoming many of the difficulties
encountered in non-syntactic phrase construction, as describedin section 3. Since this approach is integrated into a broadcoverage automatic natural language analysis system, it can b eapplied to both documents and queries, and therefore should
provide for more reliable matches between query and document phrases.

This work was supported in part by OCLC, Inc. and the
National Science Foundation (grant IST 83-16166).
Appendix

It has long been acknowledged that information about relstionships among terms in text should be "exploited as a sourceof improvement in automatic document analysis and retrieval
systems. Research on this general topic began with the early
work on statistical term associations by Stiles (1961), Doyle(1961, 1962), Giuliano and Jones (1963), Salton (1968), andLesk (1969), as well as early work on syntax-based approaches(Baxendale 1958, 1961; Salton 1966; Earl 1970, 1972; Hillman
and Kasarda 1969; Hillman 1973; Klingbiei 1973a, b). Investigation has continued with more recent work on probabilistic
terms dependency models (van Rijsbergen 1977, Harper andvan Rijsbergen 1978, Yu et al. 1983, Salton, Buekley and Yu
1983), and syntactic methods (Dillon and Gray 1983,
Aladesulu 198.5, Metzler et al. 1984, Smeaton 1986).
Nevertheless, there is still no well-established consensus
regarding how information about term relationships should beobtained and incorporated into document retrieval systems, orthe extent to which this kind of information can be expected
to yield consistently positive results. The experimental resultsof the present study and the analysis of problems related tonon-syntactic phrase construction methods indicate clearly,
however, that if information about term relationships is to be
used in a way that will yield significant improvements, then it
will be necessary to go beyond simple measures of term frequencies, cooccurrenee characteristics, and proximity inanalyzing t e x t s t r u c t u r e and identifying relationships amongwords. Thus careful experimental evaluation of s syntacticphrase indexing strategy like the one outlined in section 4
should provide valuable insights regarding the potential
benefits of automatic phrase indexing for document retrieval.

Weighting and Similarity Functions
The weight assigned to a descriptor in a vector is indicative of
the importance of the descriptor as an indicator of document orquery content. In order to include information about the relative
importance of a term in an individual document or query, theweighting function used in these experiments incorporates the frequency of each term in a given document or query. As an indication of the quality of a descriptor with respect to the document collection as a whole, the inverse document frequency ratio is included.
A discussion of these two weighting factors can be found in Sparck
Jones (1972) and Salton and Yang (1973). Finally, the cosine normalization is used in order to normalize for vector length.
The following expressions define the weighting function. Initially, the weight of term t in vector v is the frequency of t in the
document or query represented by v. This is a simple term frequency weight, tf r y . The term frequency weights are normalized
by dividing by the maximum term frequency in the vector,
maz t f v :t f tvrant.try

norm_t f r y - ~(1)

The inverse document frequency ratio is incorporated with thedefinition given in (2),t f - i d f tv ~ n ° r m - t f tv " I n ' O r(2)

where n is the number of documents in the collection, and df l isthe document frequency of t, that is, the number of documents inwhich term ! occurs at least once.
The cosine normalization yields the final weight, Wry , of termt in vector v :t f _ i d f tv

(3)~'tv =

i~t f - i d f lv 2

where k is the length of vector v.

99

ACM SIGIR Forum

59

Vol. 51 No. 2, July 2017

The weights defined by expressions (1)-(3) are used for single
term descriptors in collections that are indexed with single terms
only, as well as for single term descriptors in collections indexedwith both single terms and phrases. In collections indexed withboth single terms and phrases, however, normalization is done overthe single term subvector only, rather than over the entire vector.
Thus the single term subvector for a document (or query) in a collection indexed with single terms and phrases is identical to the vector for the same document (or query) in a collection indexed withsingle terms only.

REFERENCES

Aladesulu, O. S. 1985. Improvement of Automatic Indexing
through Recognition of Semantically Equivalent SyntacticallyDifferent Phrases. Ph.D. Thesis, Ohio State University,
Department of Information and Computer Science, Columbus,
Ohio.
Baxendale, P. B. 1958. Machine-Made Index for Technical Literature - An Experiment. IBM Journal of Research and Development 2:354-361.

The weight of a phrase descriptor is a function of the weights
of its elements. T h a t is, if phrase p in vector v is composed of single terms a and b, also in vector v, then the weight, Wpv , of phrase

Baxendale, P. B. 1961. An Empirical Model for Machine Indexing.
In: Machine Indezin F Pro#ress and Problems. Third Institutefor Information Storage and Retrieval, February 13.-17, 1961.
Center for Technology and Administration, School of Government and Public Administration, The American University,
Washington, D.C.: 207-218.

p in vector v is:

pv=

way + Why
2

(4)This phrase weight has been chosen for two reasons. First,
since the phrase weight is a function of the weights of the phrase
elements, it incorporates information about the importance of theelements of the phrase into the phrase weight. Second, it assuresthat the magnitude of phrase weights does not differ greatly fromthe magnitude of single term weights.

Buckley, C. 1985. Implementation of the SMART Information Retrieval System. Technical Report TR85-686, Department ofComputer Science, Ithaca, New York.
Croft, B. W. 1986. Boolean Queries and Term Dependencies in
Probabilistie Retrieval Models. Journal of the American Society for Information Science 37(2):71-77.

A document or query indexed with both single terms andphrases consists of two subveetors, one containing single term
descriptors, and one containing phrase descriptorsJ 4 In order to calculate the similarity between a query vector and a document vector,
a partial similarity is calculated for each subvector, and the overallsimilarity is then calculated as a weighted sum of the two partial
similarities.
Let q represent a query vector consisting of a single term subvector qs and a phrase subvector qp; similarly, let d represent a
document vector with single term and phrase subvectors d and d .
sp
The simple innerproduct function (5) is used as the basic similarity
function for a pair of subvectors, for example, qs and ds:

Dillon, M. and A. S. Gray. 1983. FASIT: A Fully Automatic Syntactically Based Indexing System. Journal of the American
Society for Information Science 34(2):99-108.
Doyle, L. B. 1961. Semantic Road Maps for Literature Searchers.
Journal of the Association for Computing Machinery 8(4):553578.
Doyle, L. 13.

E qsi " dsi
i=l

(5)

Earl, L. L. 1972. The Resolution of Syntactic Ambiguity in Automatic Language Processing. Information Storage and Retrieval 8(6):277-308.

where k represents the length of subvector s, and qsi and dsi are
the weights of the i t h terms in the single term subveetors qs andFagan, J . L . 1985. Using PLNLP for Content Analysis in Information Retrieval. Paper presented at the Symposium on PLNLP:The Programming Language for Natural Language Processing
at the Annual Meeting of the Linguistic Society of America,
Seattle, Washington, December 27-30, 1985.

ds •For the single term subvectors to which the cosine normalization has been applied (see (3) above), the innerproduct function
yields a similarity value equivalent to the cosine similarity function(Salton and Leak 1971:163) applied to vectors to which the cosine
normalization has not been applied.
The overall similarity value for vectors q and d is calculated
as a weighted sum of the innerproduct similarity values calculated
for the single term and phrase subvectors:

aim{q, d) = (c a • ip(qs, ds) ) -I- {up • iplqp, dp))

Indexing and Abstracting by Association.

Earl, L . L . 1970. Experiments in Automatic Indexing and Extract..
ing. Information Storage and Retrieval6:313-334.

kip(qs, d e ) =1962.

American Documentation 13(4):378-390.

Fagan, J. L. to appear. The Effectiveness of a Non-syntactic Approach to Phrase Indexing for Document Retrieval. Journal of

the American Society for Information Science.
Fox, E. A. 1983a. Characterization of Two New Experimental Collections in Computer and Information Science Containing Textual and Bibliographic Concepts. Technical Report TR83-561,
Department of Computer Science, Cornell University, Ithaca,
New York.

(6)

where c8 and Cp are weights applying to the single term and phrase
snbvectors, respectively. For the experiments reported on here, thevalue 1.0 has been used for both ca and Cp.

Fox, E. A. 1983b. Extending the Boolean and Vector Space Models
of Information Retrieval with P-Norm Queries and Multiple
Concept Types. Ph.D. Thesis, Cornell University, Departmentof Computer Science, Ithaca, New York.

With these weighting and similarity functions, the addition ofphrase descriptors to document and query vectors has only a simple
additive effect on the overall similarity between a document andquery. T h a t is, the partial similarity due to the single term subvector is not altered by the addition of phrase descriptors. The net
effect of this strategy for weighting descriptors and calculating similarity values is that phrase descriptors can increase the similarity
between a pair of vectors, but cannot reduce the partial similarity
due to matches between descriptors in the single term subveetors of
the query and document.

Giuliano, V. E. and P. E. Jones. 1963. Linear Associative Information Retrieval. In: Paul W. Howerton and David C. Weeks,

Vistas in Information Handling, Volume 1: The Augmentationof Man's Intellect by Machine. Spartan Books, Washington,
D.C.: 30.-54.
Harper, D. J. and C. J. van Rijsbergen. 1978. An Evaluation ofFeedback in Document Retrieval Using Cooecurrence Data.
Journal of Documentation 34(3):189-206.

14 For" further discussion of composite vectors, see Fox (1983a,

b).

100

ACM SIGIR Forum60

Vol. 51 No. 2, July 2017

Salton, G., C. Buckley, and C. T. Yu. 1983. An Evaluation ofTerm Dependence Models in Information Retrieval. In:
Gerard Salton and Hans-Jochen Schneider, Research andDevelopment in Information Retrieval, Proceedings of the
SIGIR/ACM Conference, Berlin, May 18-e0, 1#8e. Lecture
Notes in Computer Science, 146. Springer-Verlag, Berlin:
151-173.

Heidorn, G. E. 1972. Natural Language Inputs to a Simulation
Programming System. Technical Report NPS-55HD72101A,
Naval Postgraduate School, Monterey, California.
Heidorn, G. E. 1975. Augmented Phrase Structure Grammars. In:
R. Schank and B. L. Nash-Webber, Theoretical Issues in Natural Language Processing: An Interdisciplinary Workshop in
Computational Linguistics, Psychology, Linguistics, andArtificial Intelligence, 10-18 June 1975. : 1-5.

Salton, G. and M. E. Lesk. 1971. Computer Evaluation of Indexing
and Text Processing. In: Gerard Salton, The SMART Retrieval System -- Experiments in Automatic Document Processing. Prentice-Hall, Inc., Englewood Cliffs, New Jersey: 143180.

Hillman, D. J. 1973. Customized User Services via Interactions
with LEADERMART. Information Storage and Retrieval
9:587-596.
Hillman, D. J. and A. J. Kasarda. 1969. The LEADER Retrieval
System. AFlPSProceedings 34:44%455.

Salton, G. and C. S. Yang. 1973. On the Specification of Term
Values in Automatic Indexing. Journal of Documentation
29(4):351-372.

Jensen, K. 1986. PEG 1986: A Broad-Coverage Computational
Syntax of English. Research Report, IBM Thomas J. Watson
Research Center, Yorktown Heights, New York.

Salton, G., C. S. Yang, and C. T. Yu. 1975. A Theory of Term Importance in Automatic Text Analysis. Journal of the American Society for Information Science 26(1}:33-44.

Klingbiel, P. H. 1973a. Machine-Aided Indexing of Technical
Literature. Information Storage and Retrieval9(2):79-84.

Smeaton, A. F. 1986. Incorporating Synthetic Information into aDocument Retrieval Strategy: an Investigation. In: Fausto
Rabitti, Proceedings of the 198# ACM Conference on Researchand Development in Information Retrieval, Piss, Italy, September 8-10, 1986. Association for Computing Machinery,
Baltimore, Maryland: 103-113.

Klingbiel, P. H. 1973b. A Technique for Machine-Aided Indexing.
Information Storage and Retrieval 9(9):477-494.
Leak, M. 13. 1969. Word-Word Associations in Document Retrieval
Systems. American Documentation 200):27-38.
Metzlcr, D. P., T. Noreault, L. Richcy, and B. Heidorn. 1984.
Dependency Parsing for Inrormation Retrieval. In: C. J.
van Rijsbergen, Research and Development in Information Retrieval: Proceedings of the Third Joint BCS and ACM Symposium, Kings College, Cambridge, £-6 July 1984. Cambridge
University Press, Cambridge: 313-324.

Sparck Jones, K. 1972. A Statistical Interpretation of Term
Specificity and Its Application to Retrieval. Journal of Documentation 28:11-20.

Salton, G. 1966. Automatic Phrase Matching. In: D. G. Hays,
Readings in Automatic Language Processing. American Elsevier Publishing Co., Inc., New York: 169-188.

Stiles, H. E. 1961. The Association Factor in Information Red
trieval. Journal of the Association for Computing Machinery
8(2):271-279.

Salton, G. 1968. Automatic information storage and retrieval.
McGraw-Hill, New York.

van Rijsbergen, C. J. 1977. A Theoretical Basis for the Use of
Cooccurrence Data in Retrieval. Journal of Documentation
33:106-119.

Sparck Jones, K. 1974. Automatic Indexing. Journal of Documentation 30(4):393-432.

Salton, G. 1986. Another Look at Automatic Text-Retrieval Systems. Communications of the Association for Computing
Machinery 29(7):648-656.

Yu, C. T., C. Buckley, K. Lain, and G. Salton. 1983. A Generalized Term Dependence Model in Information Retrieval.
Technical Report TR83-543, Department of Computer Science,
Cornell University, Ithaca, New York.

101

ACM SIGIR Forum

61

Vol. 51 No. 2, July 2017