Searching

Distributed

With

Inference

Science

Department,

Amherst,{callan,

MA
zlu,

Lu

W. E!ruce Croft

University
01003-4610,

croft}@cs

of Massachusetts
USA.umass.eduronment,
therefore,a decisionmust be made about whichof them to search. A retrieval
system should provide
techniques that can make thk decision
automatically,
becauseusers may be unable or unwillingto make selections by exhaustively
examininglong lists of the available
collections.
Having selected the collections
to search, the retrieval
system must also provide techniques
for effectively
merging theindividual
ranked lists of documentsthat are produced.
Thk paper describes how these issues can be addressedin a retrieval
system based on the inference net, a probabilistic model of information
retrieval.
In the next section, we
describe related work on collection
selection and merging ofranked results.
In Section 3, we describe how the inference
network
can be used to rank collections
for relevance to aquery. Section 4 presents a method
for accurately
merging
the results frc)m different
collections
based on the collection
ranking.
The results in Section 5 show that it is possible
to select sub:sets of the available
collections
for searching
without
affectingretrievaleffectiveness.
Section 6 describes
several efficiency
optimizations
for distributed
searching.
Inthe final section, we summarize
the results and discuss someunsolved problems.

Abstract
The use of information
retrievalsystems in networked
environments
raises a new set of issues that have received little attention.
These issues include
ranking
document
collections
for relevanceto a query, selecting
the best set ofcollections
from a ranked list, and merging
the document
rankings
that are returned
from a set of collections.
This
paper describes methodsof addressing
each issue in the inference networkmodel,
dkcusses
their implementation
inthe INQUERY
system,and presents
experimental
results
demonstrating
their effectiveness.
1

Networks

ZhihongJames P. Callan
Computer

Collections

Introduction

Retrospective
document
retrievalis usually described as thetask of searchhg
a single collectionof documents
to produce
a list of documents
ranked in order of relevance to a particular query. The need to search multiple
collections
in distributed
environments
is becoming
increasingly
importantas the sizes of individualcollections
grow and network information
services proliferate.
Distributed
collections
can berelatively
homogeneous,as in the case where a large single
collection
is partitioned
and dktributed
over a local network
to improve search efficiency.
They can also be very heterogeneous in that wide-area network
services can make hundreds
or even thousandsof collections
available
for searching.
Searchinga dktributed
collection
presents a numberofunique problems.
One approach
would be to treat the distributed
collections
as a single, large, “virtual”
collection.
Every collection
would be searched individuallyand then
the results would be combinedor merged to produce a single ranked list.
One problem
with thk approachis how
to merge the individual
ranked lists.
The other problems
have to do with the economic
aspects of searching.
It will
generally
be too expensive
in terms of both computerandcommunication
resources and the user’s time to search every collection
in a distributed
environment.
Some systems
make this clear by making charges for searchingdependent
on the number of collections
searched.
When many collections
are available in dktributed
envi-

2

RelatedWork

Users of commercial
retrospective
information
retrievalsysselection problem.
Thetems have always faced the collectionuser must either search all collections
or choose the subset
to be searched.
Experienced
users, for example
librarians
acting as intsrmedlaries,
may draw upon their past experience or reference aids to help in deciding
which collections
to search. Many less experienced
choose to search all available collections
rather than take the time to select a subset
by trial-and-error,lSome service providers
manuallygroup their collections
into sets with common
themes, for example newspaper
collections
or appellate
court decisions.
Danzig,et al, showed
how to automaticallymaintainsimilargroupings
in distributed
environments[3]. They used broker agents thatmaintained
centralized
indices for particularsubjects by periodicallyquerying
remotecollections.
Both of these approaches simplify
collection
selection for users whose information needs can be anticipatedto some extent.
The EXPERTCONIT
retrievalsystem [7] is an early example of automatingcollection
selection.
EXPERT
decidedon a query-by-querybasis which collections
were most appropriate,
albeit for a relatively
static set of homogeneous

Permission to nmke digital/h~rd
copies of all or port of [his nmterial
without fee is granted provided th:ll lhc copies :irc nol lnfi’ie or
distributed for profit or commerci:llwivantage, the ACM cnpyri@U
server notice, the tine 01’ the puhlic:ltiun:im{ ils d:i[e :Ippcur, ;md
notice is given (hat copyright is by pcrnlission ijf LI)CAssoci:tti{)n [i)rComputing Machinery,Inc, (A ChI). Tcj CUI,Y {]~hcrwisc. to repul,lish,
to pOst on servers or to reciistril)~]tc to 11s1s,requires spwificpcrnlissioll
andlor fee.
SIGIR’95 .%al[le WA USA([) 1995 ACM 0-39791-71 4-6/95/07 $3.50

1Personal communicationfrom a commercial retrieval service

21

ACM SIGIR Forum

160

Vol. 51 No. 2, July 2017

collections.
It used rule-based
inferencing
to match the informationneed to a knowledge-basedescribing
document
collections,producinga ranked list of collections.
Voorhees,
et al, exploredrankingcollections
using thesimilarityof a new query to training
queries [13]. Relevancejudgments
for the most similar
training
queries determine
whether,and how much, to retrieve
from each collection.
This technique
may be practical
for relatively
static collections, but obtaining
relevance judgments
could be problematic for widely distributedand dynamic
collections.
GLOSS [5] estimates
the number of potentiallyrelevant
documents
in collection
C for a Boolean
AND query Q as
ICI . ll~.~fi,

wheret is a terminQ, dftis thenumberof documents
in C containingt,and ICl is the number of
documents
in C. The GLOSS approachis easily applied tolarge numbers of dynamic collections,because GLOSS stores
only term frequency
information
about each collection.
It’seffectivenessis not known yet, due to limited
evaluation
andthe lack of support
for other forms of query.
Moffat,et al, used a centralizedindex on blocks of B
documents
in individualcollections[8]. For example,
eachblock might be 10 documents
concatenated
together.
A newquery first retrieves
block identifiers
from the centralizedindex,
then searches the Klghly
ranked blocks to retrieve
documents.
This approach
worked well for retrieving
small
numbers of documents,
but caused a significant
decrease inprecisionand recall when 1,000 documents
had to be retrieved.
Once a set of collections
is chosen, the retrieval
systemmust decide how to combine search results from each collection into a single ranking.
This task is simple if the results
are an unordered
set of documents,
but it is more d]fficult
if results are ranked lists of documents.
Some have successfully used documentscores from the different
collections
tocreate a merged ranking[6; 8], but others have had problems
with thk approach[4].
Voorhees,
et al, call this the collection
fusion problem,and describe two solutions[13]. One solution is to interleave
the rankings,
in a round-robinfashion.
A second solutionisuneven interleaving,biased by the expected relevance of thecollection
to the query.
The latterapproach
was substantially more effective in experimentswith the TREC
collection.
3

Ranking

Collections

With

Inference

Figure1: A simple

document

retrievalinference

network.

A CORI net has moderatestorage requirements
if only
document
frequency(d~) and inverse collection
frequency(zcf) are stored.z
The CORI net for one 1.2 gigabyte
collection (TREC
Volume 1) would be about 5 megabytes,
assuming simple compression
algorithms.
In thk case, the CORI
net is about about 0.4~o the size of the originalcollection.
One advantage
of using the inference
network
for ranking collections
is that one system is used for ranking
bothdocuments
and collections.
It is not necessary to design new
file organizations
or algorithms.
Instead, document
retrievalbecomes a four step process:1. Use the query
2. Select

to retrieve

the top group

3. Search the top
quentially,
and

list

of collections,of collections,group

4. Merge the results
single ranking.

a rankedfromof collections,thevariousin parallelor se-

collections

into

Steps 1 and 3 can be performed
by a single algorithm
operat ing on different
indices.
To the retrieval
algorithm,
a CORI network
looks likea document
retrievalinference
networkwith very big documents;
each ‘document’is a surrogate
for a complete
collection.
Search complexity
is comparable
to searching smallcollectionsof abstracts.
A CORI networkfor 3,OOO document collections
is comparable
to searching the well-known(df)and ‘id~’ (zcf)collectionof CACM
abstracts.
The ‘tf’values are higher, but that does not affect the computational
complexityof retrieval.
There are also many more inverted
lists, but only those that match terms in the query are accessed.
The effectivenessof thk approach
to ranking
collections
was evaluatedusing the INQUERY
retrievalsystem[11;
12; 2] and the 3 gigabyte
TREC
document
collection.
The
TREC
collectionis heterogeneous,containing
17 subcollections from different
sources and/or
periods
of time (Table1). The subcollections
vary widelyin size, in numberofdocuments,
and in average document
length.
Experiments
were conductedwith 100 queries developed
for TREC
topics 51-150 during previous TREC and TIPSTER
evaluations[1].

Networks

Inference networks
are a probabilistic
approach to information
retrieval[12: 11].
The traditionaluse of inference
networks
for document
retrieval
is a directed
acyclic graphin which documents
are represented
by leaves, and the root
node represents
an informationneed (Figure
1).
A major part of the collection
selection problem
is ranking collections
for a given informationneed. Rankhg
collections can be addressed by an inference networkin whichthe leaves (the d nodes in Figure1) represent
document
collections,and the representation(r) nodes represent
theterms that occur in the collection.
The probabilities
thatflow along the arcs can be based upon statistics
that areanalogous
to tf and idf in normal
document
retrieval;forexample, document
frequency
d~ (the number of documents
containing
the term)
and inverse collection
frequencyic~(the numberof collections
containing
the term).
We callthis type of inference
networka collection
retrievalinjerence network,or COR1 net for short, to distinguishit fromthe more common document
retrievalinference networks.

‘The inference network can incorporate proximity information
operators, but it is impractical to do so for collection ranking.

and

22

ACM SIGIR Foruma161

Vol. 51 No. 2, July 2017

term

rk is determinedby:Table 1: The TREC
document
collections
used for experiments. The TREC volume number is shown in parentheses.

2’
Name
AP ’88 (2)AP ’89 (1)AP ’90 (3)DOE (1)Fed. Reg. ’88 (2)Fed. Reg. ’89 (1)Patent(3)
SJM ’91 (3)WSJ ’87 (1)WSJ ’88 (1)WSJ ’89 (1)WSJ ’90 (2)WSJ ’91 (2)WSJ ’92 (2)Ziff 1 (1)Ziff 2 (2)Ziff 3 (3)Documents
79,91984,67878,321226,087
19,86025,9606,711
90,25746,44839,904
12,38021,70552,652
10,16375,18056,920161,021

Words
21,425,011
22,407,342
21,555,502
17,201,000
20,068,562
23,444,637
19,624,651
36,441,456
11,562,767
9,738,438
3,307,151
6,500,181
12,418,568
2,880,247
20,374,002
15,637,443
44,120,132

Table 2: The averasze o~timal
rank of the TREC
collections
for topic;
51:100 and 101-150.

51-100101-150

WSJ
’87
2.3
2.4

AP
’89
2.6
2.0

WSJ
’88
2.9
2.9

WSJ
’89
4.7
4.5

DOE
4.9
4.6

Meszab~t es
249
267
249
193
219
272
254
301
132
109
38
73
146
35
254
184
362

Volume

Ziff
5.3
4.9

d.t+ (1 – cLt)=

log

log(dflog(maz-dj+ 0.5)+ 1.0)( ICI+O.5

—)

(2)

1

=

log(lq:l.o)$)(TklC,)=

d-b+ (1– d-b) T.

I(3)

where:
df

is the numberof documents
in ci containing~k,is the numberof documents
containing
themost frequentterm in c,,
Icl
is the numberof collections,is the numberof collections
containing
term rk,Cfd,is the minimum
term frequency
component
when term rk occurs in Collectionc,,db
is the minimum
belief component
when termrk occurs in collectionC;.
Thk is a variationof the well-known
tf .idf approach to ranking documents,
with values normalized
to remain between O
and 1, and further
modifiedby default
term frequency(d~)
and default belief (db) values. d~ and db default
to 0.4.
The probabilistic
query operatorsthat combine the beliefs accruing
from the query terms remained
unchanged[11; 12]. The proximity
operators
were replaced
by strictBoolean AND operators,
due to the lack of proximity
information in CORI nets (discussed in Section 6.2).
This approach
was used to rank TREC
volume 1 collections for topic~s 51-100.
The mean-squared
error, averaged
over 50 queries, was 2.3471. The rankings
for about 7570 of
the queries were nearly perfect;
the rankingsfor the other25~o were more disorganized,
and accounted
for most of theerror. No pattern
was apparent
to explain why some queries
yielded such poor rankings.
One possible problem
in applying
the default
formulasfor ranking
documents
to ranking
collections
is the use of
the max-df
statistic
to scale df. Although
we have argued
that ranking
collections
is analogous
to ranking
documents,
there are differences.
The reason for ranking
collectionsis
not to find collections
about a particularsubject;
it is tofind collections
containing
as many documents
as possible
about the subject.
Scaling df by max~ftends to obscuresmall (and not-so-small)sets of interesting
documentsinlarge collections.
Recent experimentswith document
retrievalsuggest thatit may be better to scale tf by tf + K, for some small K [10].
The analogue for this task would be to scale d~ by d~ + K,
replacingEquation
1 above with Equation
4 below.
max-df

1

FR
’89
5.4
6.6

The mean-squared
error metric was used to compare theeffectivenessof variations
to the basic collection
rankingalgorithms.
The mean-squared
error of the collection
ranking
for a single query is calculatedas:& 2’ec(O’- “)’
where:
0,=

optimalrank for collectioni, based on thenumber of relevant
documents
it contained(the collection
with the largest number of
relevant
documents
is ranked 1, the collection
with second largest numberof relevant
documents
is ranked 2, and so on),Ri=
the rank for collection
z determinedby theretrievalalgorithm,
andc=the set of collections
being ranked.
The mean-squared
error metric has the advantagethat it iseasy to understand(an optimal
result is O), and it does not
require labelinga collection‘relevant’or ‘not relevant’
for

T

=

d-t+

(l–d-t).

~
df+K

(4)

When ranking documents,
it makes sense to make K a function of document
length.
However, when ranking collections,
it may make more sense to let K be more sensitive
to thenumber,and not the percentage,of documents
about thesubject.
It may also make sense to let K be large, because
the df values will generally
be large.
We defined K = k . ((1 – b) +b.
cw/@,
where k and b
are constants,
cw is the numberof words in the collection,and ~ is the mean cw of the collections
being ranked.
The
constant k controls the magnitudeof K. Varyingb from O to
1 increases the sensitivityof K to the size of the collection.
Thk approach
was used to rank TREC
volume 1 collections for ~~pics 51-100.
Experiments
were conductedwitha particularquery.
The average optimal
rank 0. for eachcollection
in TREC Volume
1 is shown in Table 2.
INQUERY’s
algorithms
for ranking
documents
havebeen documented
extensively[11; 12; 2; 1], so thk discussion
is confined to the changes necessary to rank collections.
Thechanges were confined
initially
to replacing
t.f with d~ andidf with icf, as discussed above, and with replacing
the maximum term frequency
in a document
statistic(maz.tf)withthe maximum
document
frequency
in” a collection(raaz.df).
Hence, the belief p(~k It, ) in collection
ci due to observing

23

ACM SIGIR Forum

(1)

162

Vol. 51 No. 2, July 2017

4.0
3.5
3.0

0
m

2.5

L

2.5

i:L
(-6
0)

0

50

2.0

1.5
1.0 E
0.0

100150200250300

0.2

0.4

0.6

0.8

1.0
b

k

Figureva~led.

2: The effect on mean-squaredIn b) k = 200 as b is varied.

error

of varying

K

(TREC

VolumeMerging

topics51-1 OO)).

In a) b = O as k isdesirable,
because the idf represents
the term’s importance in a particularcollection.
It can also be viewed as
undesirable,
because an importantquery term can behave
erratically,
rewarding
the random
mentionof a term in one
collection
and penalizing
its common use in another[4].
The problem
of incomparable
scores can be overcome insome cases by normalizing
statistics
such as id~ for the setof collections
being searched [6]. The intent is to normalize
document
scores to obtain
precisely
the same results thatwould be obtained
if the individual
document
collections
were merged into a single unified
collection.
The dMicultYof normalizing
document
scores for a set of collections
depends upon the retrieval
algorithms
employed.
For the inference networkarchitecture,normalizing
scores requires a
preprocessing
step prior to query evaluation.
In the preprocessing
step, the system obtains from each collection
thestatistics
about how many documents
each query term orvalues of k ranging
from 1 to 300 (Figure2a), and withvalues of b ranging from O to 1 (Figure2b). The best combinationof values for thk set of queries and collectionsisk = 200, b = 0.75.
The mean-squared
error, averaged
over 50 queries, for
thk combination
was 1.4586, which is 38y0 better than themean-squared
error obtained
when scaling df by max.df.
The collection
rankings
improved
for 30 queries,
some
quite dramatically.
The rankingsfor 8 queries deteriorated
slightly.
The rankingsfor 12 queries dld not change.
A mean-squared
error of 1.4586 is not perfect,
but it isgood.
Analysisof the results reveals few serious mistakes.
Most of the mistakes
were due to mixing
up the rankingsof collections
containing
nearly equal numbersof relevant
documents.
These cases were counted
as errors, but theywould not be noticeable
to a user. Indeed, althoughfurther
improvement
is possible, it is likely to yield diminishingreturns.
4

1 collections,asproximity
operator
matches.
The statistics
are merged toobtain a normalized
idf. The query and the normalizedidfi
are sufficientto then retrieve
documents
with comparable
scores from dkparate
collections.
Normalizing
document
scores can entail significant
communicationand computationalcosts when collections
are
distributed
across a wide-area
network.
An alternative
toboth simple interleaving
and normalized
scores is merging

Results

Rankingcollections
is only part of the problem.
After aset of collections
is searched, the ranked results from eachcollection
must be merged into a single ranking.
If only the document
rankings
are available,
the resultsfrom each collection
can be interleaved[13]. This solution
is not satisfying,for it is unlikelythat all of the collections
have equal numbers
or proportionsof relevant
documents.
However,
it is difficult
to do anything
more sophkticatedwithout
more information
than just the document
rankings.
Many IR systems return
not only a ranking
of documents, but a numericscore that indicates
how well eachdocument
matchesthe query.
If the scores from different
collections
are comparable,
one can merge the set of rankings based upon the documentscores (~aw score merge).
Withsome techniques,
the scores from different
collections may not be dkectlycomparable.
For example,
although the zdj weights for many words are relatively
consistent across different
collections,the idfweights
of words suchas computer,tort and cholesterol
will vary widely
amongtechnical,
legal and medicalcollections.
This can viewed

based on weighted
scores.
Weights
can be based upon adocument’s
score and/or
the collection
ranking information.
Thk approach
offers the computational
simplicity
of simple
interleaving
while overcomingsome of its disadvantages.
The weight w, below, is an exampleof how one might
weight results from d~fferent collections.
We have used thecollection’sscore, instead of its rank, because we believe thatsimilarcollections
should have similar
weights.

where:IcI=
the number of collections
searched,s=
the collection’sscore, and3=
the mean of the collection
scores.
Each document
is ranked based upon the productof its score

24

ACM SIGIR Forum

163

Vol. 51 No. 2, July 2017

Table3: Different

techniques

for merging

resultsfromdifferent

collecticms

Recall - Precision Averages (5o queries):
Normalized
Interleaved
Raw Score
Merge
Merge
Merge
0%
88.37
78,95
(-10.7)83.14(-5 9)
1070
65.99
38.67
(-41.4)60.08(-9.0)
57.49
2070
2942
(-48.8)52.49(-8.7)
30%
51.23
24,76
(–51,7)45.88(-10.4)45.63
20.13(-55.9)40.53{-11.2)40’?7,
5070
38.65
14,64
(-62.1)
34.23(-11,4)10.74(-67.4)27.57(-16,3)
60%
32.95
7070
26,25
6,81
(-74.1)
21.83(-16.8)
80%
17,31
4.29
(-75.2)
15.24(-12.0)1.43(-82.9)
90?’o
8.36
6.71
(r~~.;~
100%
1,22
0.33
(-73.0)
1.18
Average precision (non-interpolated)over all rel dots
37.76
17.54
(-53.5)
33.67(-10.8)(TREC

Volume1,,. to~ics

51-100).

Interpolated

Precision:
5 dots:
10 dots:
15 dots:
20 dots.
30 dots.
100 dots:
R-Precision
Exact:

69,60
52.80(-24.1)
63.60
65,00
43.20
(-33.5)
59.20
62.93
38.00
(-39.6)
59.47
62.10
37.30
(-39.9)
56.20
59.00
35.40
(-40.0)
53.67
46.76
29.82
(-36.2)
43.66(precision after R (= numxel for a query)
41.96
25.42
(-39.4)
38.67

38,18

(+1,1)(-8.6)
67.60(-8 9)
6420(-5.5)
62.00(-9 5)
6160(-9.0)
5933(-6 6)
47.76
dots retrieved):(-7 8)
42.46(-2,9)(-1 2)(-1.5)(-0,8)(+0.6)(+2.1)(+1.2)

specific weights was about as effective as ranking
based onnormalized
scores. It produced
small improvements
in mostlevels of recall for queries 51-100 on the TREC
1 collections;
small losses in most levels of recall for queries 101-150 on
the TREC
1 collections;and small changes in precisionatmost levels of recall for queries 51-100 on the TREC
1+2+3
collections.
In general, our experience
with weighted
rankings was small changes at low recall, and occasionallyerratic
behavior
at high recall.
We view these results as extremely
encouraging.
Theysuggest that it is possible
to get the accuracyof rankings
based on normalized
scores without
the computational
effort.

and the weight w for its collection.
Thk algorithm
favorsdocuments~om collections
with high score;, but also enables a good documentfrom a poor collection
to be ranked
highly.
These four approaches
to merging
results,
interleaving,Taw sco7e9, nor’mahzed acorea and weighted
Scores, were compared in a series of experiments
using the collections
andqueries described in Section 3. Experiments
were conductedwith two query sets (51-100 and 101-150) on TREC
Volume 1 (7 collections),
Volume2 (6 collections),
Volume3(4 collections),
Volumes
1+2 (I3 collections),
and Volumes
Results are shown for Volume
1,
1+2+3(17 collections).
and Volumes
1+2+3.
The normalized
scores approach
wastreated as the baseline, because it is equivalent
to the “single
database”
paradigm
that has been the norm in information
retrieval.
The experimental
results are containedin Tables
3-5.
Both 11 point recall/precision
and absolute precisionatvarious cutoffs are included,
to give a clear picture of behavior at both low and high recall.
Recall and precisionwere
calculatedby the TREC
trec2.eval
programusing just the
top 1000 documentsfrom the merged ranking.
Thkapproach treats all documents
above rank 1000 as ranked last,giving a very pessimistic
view of high recall behavior.
In each experiment,
simpleinterleavingof document
rankings
was extremely
ineffective,
producing
dramatic
losses in average precision.
This result is not surprising,
because interleaving
has the effect of boosting
the rankkgs
of random documentsfrom collections
with few relevant documents.
Merging
based on raw documentscores from each collection was simificantlv
worse than ranklmz based on normalized documentscores. causirw losses from 1o-2o% in average precision.
The only difference
betweenthe normalized

5

Collection

Selection

In the experiments
described
above, all collections
weresearched, and their results used to create the final document
rankkm.
However, in distributed
environments,
one rarelv
has th~ resources to search every collection.
It is’more likel~
that one searches an index of collections,obtainsa ranking, and then searches the top few collections
for interesting
documents.
There are any numberof ways to decide how far down
the collection
rankings
to go. One could choose the top n,
any collection
with a score greater than some threshold,or
the top group as defined by some clustering
method.
We
investigatedthe latter approach.
A single-passalgorithm[9] was used to cluster
the collection rankingsfor each query.
Collections
were clusteredon the basis (of their scores, as determinedby the collection ranking
algorithm(Section3). The cluster difference
threshold
was low (0.0012),
creating
clusters
that tended
to be smaller than necessary.
The seven TREC
Volume1collections
moducedan averat?e of 4.04 clusters for toDics
51-100 and 4.06 clusters for to~lcs 101-150. It was rare for acollection
with a significant
numberof relevant
documents
to be excluded from the top 2 clusters.

“

and unnormalized
scores was the L-if component.
thatsult confirms
previous
research suggestingized idfs can give misleadhg
results [4].
Ranking
based on documentscores andWeighted
Merge
85.92
(-2.8)
65.15(-1,3)
58,21(+1.3)
51.84(+1.2)(+0.6)
45.92
39,50(+2.2)
32,83(-0,4)
26.28(+0.1)
18.22(+5.3)
10,64(+27.3)1.25(+2.5)

Thk reunnormalcollection-

25

ACM SIGIR Forum164

Vol. 51 No. 2, July 2017

Table4: Different

technirmes

for merging. . resultsfrom

different

collections

Recall - Precision Averages (5o queries):
Raw Score
Interleaved
Normalized
Merge
Merge
Merge
80.36
(-4.4)
82.91(-1.4)
84.05
07’0
42.65
(-30.8)5’7.25(-7.1)
61.62
10%
54.66
33.35
(-39.0)49.94(-8.6)
20%
49.54
27.72
(-44.0)45.16(-8.8)
30?70
44.76
22.75
(–49.2)
38.72(–13.5)40~o
18.26(-52.2)
32.71(-14.3)
38.18
50~o
32,68
14.57
(–55.4)27.82(–14.9)60%
8.54(-67.3)22.05(-15.6)
26.13
70%
4.62
(-75.7)
16.46(-13.4)
19.01
80~0
9.40
(i::::]
1.66(-84.4)
90%
10.66
0.35
(-76.2)
1.39
1.47
10070
Average precision (non-interpolated)over all rel dots
36.98
20.48
(–44.6)
33.22(–10.2)(TREC

Volume1, topics

101-150).

Interpolated

Precision:
5 dots:
10 dots:
15 dots:
20 dots:
30 dots:
100 dots:
R-Precision
Exact :

63.20
54.40
(–13.9)
60.80
58.80
50.00
(–15.0)
55.80
59.13
43.73
(-26.0)
54.00
57.30
41.00
(-28.4)
52.30
55.60
38.47
(–30.8)50.27
29.06(-33.8)40.04
43.92(precision after R (= numxel for a query)
26.50(-33.5)
36.96
39.85

6.2

6.3

a CollectionWitha Subsetof Terms

One could create a smaller collection
retrievalinference net
by keeping only a subset of the terms that appear in thecollection.
An example
would be to keep only the mostfrequent.
An experimentwith TREC
Volume1 and topics
51-100 investigatedthe effect of building
inference nets withdifferent
percentagesof the most frequentterms in the collection.
Figure 3a shows the mean-squared
error, averaged
over 50 queries.
Figure 3b shows the effect on average 11

ACM SIGIR Forum(–3.8)
62.00(–5.1)
58.20(-8.7)
56.00(-8.7)
55.50(-9.6)
53.80(-8.8)
43.34
dots retrieved):(-7.3)
38.47(-1,9)(-1.0)(-5.3)(-3.1)(-3.2)(-1.3)(-3.5)

Proximitysuggest that it is necessary tofrequent
terms, and that there
all of the terms.

Information

Retrieving

Fewer

Documents

If a user wants to retrieven documentsfrom a set of C
collections,
one could retrieven documentsfrom each collection,
merge the rankings,
and then dkcard
everything
below rank n. However, this approach is costly if collections
are distributed
widely across networks,
because (C – 1) - n
documents
are retrieved,
sent across the network,and thendkcarded
without
a user seeing them [13]. Thk cost raises
the question of whether it is possible to safely retrieve fewer
than n documentsfrom collections
with low ranks or scores.
We have experimented
with a heuristicthat uses the collection ranking
information
to decide how much to retrieve
from each collection.
The number of documents
R retrieved
from the i’th ranked collectionis:Optimization

Represent(-3.7)The INQUERY
system [2], which is based on the inference
networkmodel, extends the inference network
formalism
toinclude proximity
operators.
One could also use term proximity information
for collection
ranking,but it would requirethat the locationof each term in each document
in each collection be stored in the CORI index. Although
it is possible
to do so, the CORI net for one collection
would become
about 30% the size of the originalcollection.

In this section we discuss several decisions that can affectthe efficiency
of collection
ranking
and merging rankings.
6.1

35.60

point precision.
The results..
store at least the 20’70 mostis some advantage
to storing

The effect on recall and precision
was noticeable,
but not
significant
at low recall.
We summarize
the results, rather
than providing
complete recall/precisiontables} due to space
limitations.
With topics 5I-1oo, the difference
between using the two best clusters of collections(an average of 4.04
collections)and using all i’ collections
was less than —5~oat all document
cutoffs from 5 to 1,000. The differenceinexact R-precision
was —O.9~o. The differencein average 11
point precision was –2.2’70.
The effect on topics 101-150 was
more noticeable,with differences> 5.()~o at and above the
200 document
cutoff.
The difference
in exact R-precision
was – 5. 6~0, and the difference in average 11 point precision
was –9. l%, both reflecting
significant
deteriorationin highrecall results.
It is not surprisingthat eliminatingcollections
reducesrecall.
There will occasionallybe errors in the collection
rankings,
or a few relevant
documents
in marginalcollections. In our opinion it is more significant,and encouraging,that precision
at low recall is relatively
unaffected
when thenumber of collections
searched is reduced by 4370. Few interactive
users will care about a drop in recall at rank 200.
Those that do can choose to search more collections.
6

Weighted
Merge
79.64
(-5.2)
60.76(-1.4)
53.35(-2.4)
48.19(-2.7)(-6.5)
41.86
37.03(-3.0)(-5.4)
30.92
25.30(-3.2)
18.47(-2.8)
9.70(-9.0)
1.15(-21.8)

R(i)=

M.n.

I+

C–i=M
Z:=,’j~“2.(l+c–i)“C.(c+l)where &fc[l.0,~],and M . n is the number of documents
to be retrieved
from all collections.
Thk heuristic
is a linear functionthat allocatesa predetermined
number of document
retrievals(M . n) across Ccollections.
If C = 5 and M = 2, the first collection
retrieves

165

Vol. 51 No. 2, July 2017

Table5: Different

techniquesL

far merczin~ results
.“

from

different

collections(TREC

Recall - Precision Averages (50 queries):
Raw Score
Normalized
Interleaved
Merge
Merge
Merge
(-2.4)
86.50
77.15(-10.8)8441
07’0(-9.8)
59.90
33.81(-43,6)5404
10’?702451(-51 9)45.88(-10.0)
20%
50.96
1628
(-62.4)3891(-102)
4332
30~o
10.06
(-70.2)
29.35(-13 1)
40%
3378
7.01
(-71.6)19.71(-20 1)24.67
50~o(–72.5)
12.95(-19,7)
6090
16.12
4.44
2.04
(-83.3)
10.86(-10,9)
707’0
12.19
744
0.41
(-94,5)555(-25.4)8070
033(-89 7)
2.53(-20.9)
90%
3,20
000
(Inf)
0.00
(Inf)
100’7’0
0.00
Average precision (non-interpolated)over all rel dots
12,34(-564)
2511(-11.2)
28,28

Volumes

1.2

and 3. toDics,.

51- 100).

Interpolated

Precision:
5 dots:
10 dots:
15 dots:
20 dots:
30 dots:
100 dots:
R-Precision
Exact :

68,80
60.00
(-12.8)
64.40
6700
53.40
(-20.3)
61,60
6467
42.00
(-35.1)
59.47
63,40
40.90
(–35.5)
57.60
61 27
39.80
(-35.0)
57.93
53.80
32.76
(-39.1)49.80(precision after R (= numi-el for a query)
3699
22,86
(-38.2)
34.54

27.91

(-1.3)(-6.4)
68.00(-8.1)
66.20(-8.0)
64,53(-9.1)
62.80(-5.5)
61.33(-7.4)
54.40
do.. retrieved):(-6.6)
36,66(-1.2)(-1.2)(-0.2)(-0.9)(+0.1)(+1.1)(-0.9)

results
Thk
paper describes
efficientalgorithms
for providing
these capabilities
in systems based on the inference networkmodel of information
retrieval.
They enable a system toautomaticallyand efficiently
rank collections
for relevance toa query, select a subset of them, search the subset efficiently,
and then accurately
merge the results.
The effectivenessof the algorithms
is demonstrated
in experimentswith theINQUERY
information
retrievalsystem and the TREC
setof document
collections.
The experimental
results are encouraging
because simple methods were quite effective with collections
that varied
widely in size and content.
However,they must be viewed
as preliminary,because only 17 collections
were involved.
These methods
will be equally
efficientwith hundredsorthousandsof collections,but it is not known whether
theywill be equally effective.
Distributed
collections
present
several other problems
that we have not addressed.
In our work, all of the collections
used the same stemmingalgorithm,
stopwordlist,
and query processing
techniques.
When these differ, as they
will in collections
an wide-area
netwarks,
several problems

0.67. n documents,
the second retrieves
0.53. n documents,
the third retrieves 0.40. n, the fourth retrieves 0.27. n, andthe fifth retrieves 0.13. n. More documents
are retrieved
as
M is increased, allowing
the user or system to trade cost forsafety.
In experimentswith TREC volume 1 and topics 51-150,
the total numberof documents
retrieved
to produce a final
list of 1000 was reduced from 4,050 to 2000 (a 51% savings),
Therewith only minimal
impacton recall and precision.
was almost no change in which documents
were ranked 1 to
500 for each query. The average 1I point precisionchanged–0.1% for topics 51-100, and +1.OVO for topics 101-150.
We also exploredthe effect of retrieving
different
numbers of documents
by varying
M from 1 to 3 by 0.5. For
the TREC
volume 1 collections,
all values produced
nearlyidentical
results for ranks 1 to 200. At Al = 2, they wereidentical
down to rank 500. M = 3 produced
slightly
betterresults between ranks 500 and 1.000,
on both auerv.“. sets,,.
than smaller
values of M.
Similarresults were obtained,with slightly
highervalues of M (e.g.
M = 3 insteadof
M = 2), for the full set of 17 TREC
collections.
These results are encouraging,but they are based on relatively accurate methods of ranking and selecting collections
for a query, When accurate
methods
are available,
computationand communication
costs can be minimized
by retrievimz fewer documentsfrom each collection.
When there
is dou~t about the collection
ranking,
it may be worth theadded cost to retrieve more documentsfrom each collection.
7

Weighted
Merge
8654(+0.0)
60.09(+0.3)(-1 3)
50.30
42.04(-3 o)
35.04(+3.7)
23.47(-4.9)
16.61(+3 o)
11.53(-5.4)
6.45(-13.3)
2.76(-13.8)0.00(Inf)become more difficult.
It is less obvious how to represent
each collectionin the collection
retrievalinference network.
It is not clear how to provide information
to the user about
how the informationneed was transformed
into a structured query, because the transformation
may be collectionspecific. Finally,
it is unclear how to perform
relevance feedback when the set of relevant documents
is scatteredacrossa set of collections
with different
representations.
The work described in this paper, although
positiveandencouraging,is merely the first step.

Conclusion

As information
retrievalsystems are appliedin networked
environments
to widely
dktributed
document
collections,the systems will need to provide
collection
ranking,collection selectzon
and ~esults nzerging capabilities.
It is desirable
to provide these capabilities
efficiently
and transparently,
sothat users can, if they choose, maintainthe illusionof asingle ‘virtual’collection
returninga single, coherent set of

Acknowledgements

This research was partiallv
suDDorted bv the NSF Cent.. forIntelligent
Information
R“etri~~al at th~ Universityof Massachusetts,
Amherst.

27

ACM SIGIR Forum

166

Vol. 51 No. 2, July 2017

8.0

—

7.0

%—

F

log (df+O.5) / log (max_df+l
df / (df+K)

x

k

5.0
4.0
3.0

~ 30.0.—“~ 27.5

“,

2.0
1,0}
00

L$ 25.0oa: Accuracy of collection
3: Theeffect—log (df+O.5) / log (max_df+lof buildingOanets fromonly

the most

frequentterms

B. Croft,

and J. Broglio.

TREC

TIPSTER

experiments

with

INQUERY.

Processingand Management,(in press).

[2] J. P. Callan,

W. B. Croft,and S. M. Harding.

andaries.

Information

retrievalInternational

system.

In Proceedings

Conferencetemg Application,

on Database

pages 78–83,

Theof theIN-

Spain,

B.

Y.

J.

Ahn,

J.

indexing:
information

Chiaramella,
Proceedings

tionalA CM/SIGIR

Chicago,

Nell,

in

of

K.

The

1992.

of Standards

retrieval.

In

and

A.

V. V.

Fourteenth

Text

In

Raghavan,

ed-

and

pages

1991. Association

Rasmussen.

Prentice

Latentsemantic

indexing

Harman,editor,K.

220–229,

National

Specialof GLOSSandfor the text

In Proceedings

137. ACM,

September(in~nformation

retrievalsYs-

In D. K. Harman,
Confe~ence(TREC-

National

Institutepress).
SpecialPublication

Hall,

500-

databaseof SIGMOD

dkcovery94, pages

Harman,editor,routing

retrieval

REtrieval

Conference
National

Specialand

D. D. Lewis.

and thresholding

In D. K. Harman,(in press).

The

Data

16, pages 419-442.

S. Jones,
Okapi

Third

MD,

and

M. M. Hancock-at TREC-3.

Text

Gaithersburg,of Standards

In D. K.
Conference

REtrieval(in press).

Technology,

National

SpecialIn-

Publica-

500-225.
and W. B. Croft.
retrievalsystems,

Evaluation

model.

R. Turtleand W. Bruce

abilistic

inference

for

April

Proceedings,

of an infer-

A CM

9(3):187–222,[12] Howard
ference

126-

FrakesTrarsgactions

1991.

Croft.

Efficient

prob-

text

retrieval.

In RZA O 3 Con-

pages

644-661,

Barcelona,

Spain,

1991.

1994.

L. Grunfeld,

using PIRCS.

S. Walker,

on Information

The

chapter

In

Retrieval:

1992.

ence network-basedof Stan-algorithms.

Information

and Algorithm,[11] H. R. Turtle

500-215.

A. Tomasic.

Clusteringand M. Gatford.

[13] E. M.
[6] K. L. Kwok,

nology,REtrievalMD,

Beaulieu,

tion

and

Second105-115,

InstitutePublication

H. Garc~a-Molina,

problem.

(LSI)
The

pages

(TREC-2),

1994.

and Technology,

ad-hoc,Text

editors,[10] S. E. Robertson,

De-for Computing

D.
MD,

Gaithersburg,

effectivenessforInformationcollections.

and Technology,.$’t?’uctwes

lnter’na-

AnnualRetrieval,

Conference

REtrieval[5] L. Gravano,of the effec-

as search intermedl-

Society

Zobel.

Third(TREC-3),

Dumais.

dards

J.

documentand Baeza-Yates,

stituteTREC-2.

51-100).

1983.

Gaithersburg,[9] Edle

dk-Bookstein,

on Research

Conference

InformationforMachinery.
[4] S. T.

topicscomparisonof the American

and

3),

1 collections,and humans

34:381-404,

Moffateditor,

Obraczka.

mechanism

theIL, OctoberandA scalable

G, Salton,itors,

velopment

Volumerankings.

225.

Danzig,tributed~ourna~Sys--

Springer-Verlag.

Distributed

100

An experimental

tems for large

Thirdand Expert

Valencia,

80of computers

Science,[8] A.

QUERY

60

(TREC

tiveness[3] P.

40[7] R. S. Marcus.
W.

)of Terms In Cori Net

b: Accuracy of merged document

rankings.

CORI

20

Percentage

References[1] J. P. Callan,

df / (df+K)x

g 20.0 L‘

40
60
80
100
of Terms in Coti Net20~$ 22.5~Percentage

Figure)editor,(TREC-3),
InstitutePublication

TREC-3The

experiments
The

Third

Gaithersburg,of Standards

and

itor,

Tewt

3),

MD,

Voorhees,collection
The

Third

Gaithersburg,of Standards

Tech-

N.

K.

fusionGupta,

andproblem.

In

Text

MD,

B.
D.

Johnson-Laird.

K. Harm an, ed-

REtrieval

Conference(TREC-(inNational

Instituteand Technology,press).
SpecialPublication

500-

225.

500-225.

28

ACM SIGIR Forum

167

Vol. 51 No. 2, July 2017