Query-based sampling of text databases.
The proliferation of searchable text databases on corporate networks and the Internet causes a database selection problem for many people. Algorithms such as gGLOSS and CORI can automatically select which text databases to search for a given information need, but only if given a set of resource descriptions that accurately represent the contents of each database. The existing techniques for a acquiring resource descriptions have significant limitations when used in wide-area networks controlled by many parties. This paper presents query-based sampling, a new technicque for acquiring accurate resource descriptions. Query-based sampling does not require the cooperation of resource providers, nor does it require that resource providers use a particular search engine or  representation technique. An extensive set of experimental results demonstrates that accurate resource descriptions are crated, that computation and communication costs are reasonable, and that the resource descriptions do in fact enable accurate automatic dtabase selection.
Table

1.
Size, Size,
Name in bytes in documents
CACM 2MB 3,204
Test corpora.
Size, Size,
in unique in total
terms terms Variety
6,468 117,473 homogeneous
122,807 9,723,528 heterogeneous
very heterogenenous
of these choices is deferred to later sections of the paper.
How best to represent a large document database is an open problem. However,
much of the prior research is based on simple resource descriptions consisting of
term lists, term frequency or term weight information, and information about the
number of documents 15; 14; 36 or number of words 7; 39; 40 contained in the
resource. Zipf's Law and Heap's Law suggest that relatively accurate estimates of
the rst two pieces of information, term lists and the relative frequency of each
term, can be acquired by sampling 20; 43 .
It is not clear whether the size of a resource can be estimated with query-based
sampling, but it is also not clear that this information is actually required for
accurate database selection. We return to this point later in the paper.
The hypothesis motivating our work is that su ciently accurate resource descriptions
can be learned by sampling a text database with simple free-text' queries.
This hypothesis can be tested in twoways:
1 by comparing resource descriptions learned by sampling known databases
learnedresource descriptions' with the actual resource descriptions for those
databases, and
2 by comparing resource selection accuracy using learned resource descriptions
with resource selection using actual resource descriptions.
Both types of experiments were conducted and are discussed below.
4. EXPERIMENTAL RESULTS: DESCRIPTION ACCURACY
The rst set of experiments investigated the accuracy of learned resource descriptions
as a function of the number of documents examined. The experimental
method was based on comparing learned resource descriptions for known databases
with the actual resource descriptions for those databases.
The goals of the experiments were to determine whether query-based sampling
learns accurate resource descriptions, and if so, what combination of parameters
produce the fastest or most accurate learning. A secondary goal was to study the
sensitivity of query-based sampling to parameter settings.
The following sections describe the data, the type of resource description used,
the metrics, parameter settings, and nally, experimental results.
4.1 Data
Three full-text databases were used:
CACM: a small, homogeneous set of titles and abstracts of scienti c articles from
the Communications of the ACM;
Query-Based Sampling of Text Databases 7
WSJ88: the 1988 Wall Street Journal, a medium-sized corpus of American newspaper
articles;1 and
TREC-123: a large, heterogeneous database consisting of TREC CDs 1, 2, and 3,
which contains newspaper articles, magazine articles, scienti c abstracts, and
governmentdocuments
These are standard test corpora used bymany researchers. Their characteristics
are summarized in Table 1.
4.2 Resource Descriptions
Experiments were conducted on resource descriptions consisting of index terms
usually words and their document frequencies, df the number of documents containing
each term .
Stopwords were not discarded when learned resource descriptions were con-
structed. However, during testing, learned and actual resource descriptions were
compared only on words that appeared in the actual resource descriptions, which
e ectively discarded from the learned resource description anyword that was considered
a stopword by the database. The databases each used the default stopword
list of the INQUERY IR system 34; 33; 6 , whichcontained 418 very frequent
and or closed-class words.
xes were not removed from words stemming' when resource descriptions
were constructed. However, during controlled testing, su xes were removed prior
to comparison to the actual resource description, because the actual resource descriptions
the database indexes were stemmed.
4.3 Metrics
Resource descriptions consisted of twotypes of information: a vocabulary, and frequency
information for eachvocabulary term. The correspondence between the
learned and actual vocabularies was measured with a metric called ctf ratio.The
correspondence between the learned and actual frequency information was measured
with the Spearman Rank Correlation Coe cient.Each metric is described
below.
4.3.1 Measuring Vocabulary Correspondence: Ctf Ratio. The terms in a learned
resource description are necessarily a subset of the terms in the actual description.
One could measure howmany of the database terms are found during learning,
but such a metric is skewed by the many terms occurring just once or twice in a
collection 43; 20 . We desired a metric that gave more emphasis to the frequentand
moderately-frequent terms, whichwe believeconvey the most information about
the contents of a database.
Ctf ratio is the proportion of term occurrences in the database that are covered
by terms in the learned resource description. For a learned vocabulary V 0 and an
actual vocabulary V , ctf ratio is:
1The 1988 Wall Street Journal data WSJ88 is included on TREC CD 1. WSJ88 is about 10
of the text on TREC CD 1.
8 J. Callan and M. Connell

Table

2. ctf ratio example.
Actual Resource Description
Learned Resource Descriptions
Vocabulary ctf
Vocabulary ctf ratio
apple 4
bear 1
cat 3
dog 2
where ctfi is the number of times term i occurs in the database collection term
frequency,orctf . A ctf ratio of 80 means that the learned resource description
contains the terms that account for 80 of the term occurrences in the database.
For example, suppose a database consists of 4 occurrences of apple", 1 occurrence
of bear", 3 occurrence of   cat", and 2 occurrences of dog" Table 2 . If
the learned resource description contains only the word apple" 25 of the actual
vocabulary terms , the ctf accounts
for 40 of the word occurrences in the database. If the learned resource description
contains both apple" and   cat", the ctf ratio is 70 . ctf ratio measures the degree
to which the learned resource description contains the words that are frequentin
the actual resource description.
Note that the ctf ratios reported in this paper are not arti cially in ated by
nding stopwords, because ctf ratio was always computed after stopwords were
removed.
4.3.2 Spearman Rank Correlation Coe cient. The second component of a resource
description is document frequency information df , which indicates the relative
importance of each term in describing the database. The accuracy of frequency
information can be determined either by comparison of learned and actual
df values after appropriate scaling, or by comparison of the frequency-based term
rankings produced by learned and actual df values. The two measurementmethods
emphasize di erentcharacteristics of the frequency information.
Direct comparison of df values has the undesirable characteristic that the comparison
is biased in favor of estimates based on larger amounts of information, because
estimates based on 10n documents enable only n digits of accuracy in scaled values.
This characteristic was a concern because even relatively noisy df estimates based
on small numbers of documents might be su cient to enable accurate resource
selection.
rankings produced by learned and actual df values can be compared by
the Spearman Rank Correlation Coe cient, an accepted metric for comparing two
orderings. The Spearman Rank Correlation Coe cient is de ned as:
where di is the rank di erence of common term i, n is the number of terms, fk is
the number of ties in the kth group of ties in the learned resource description, and
gm is the number of ties in the mth group of ties in the actual resource description.
Two orderings are identical when the rank correlation coe cient is 1. They are
Query-Based Sampling of Text Databases 9
uncorrelated when the coe cient is 0, and they are in reverse order when the
coe cientis,1.
The complexity of this variant of the Spearman Rank Correlation Coe cientmay
some readers. Simpler versions are more common e.g., 28 . However,
simpler versions assume a total ordering of ranked elements; two elements cannot
share the same ranking. Term rankings have many terms with identical frequencies,
and hence identical rankings. Variants of the Spearman Rank Correlation Coe -
cient that ignore the e ects of tied rankings can give misleading results, as was the
case in our initial research on query-based sampling 5 .
The Spearman Rank Correlation Coe cientwas computed using just the terms
in the intersection of V and V 0. Use of the intersection is appropriate because the
Spearman Rank Correlation Coe cient is used to discover whether the terms in V 0
are ordered appropriately by the learned frequency information.
Database selection does not require a rank correlation coe cient of 1.0. It is
su cient for the learned resource description to represent the relative importance
of index terms in each database to some degree of accuracy.For example, it might
be su cienttoknow the ranking of a term 5 . Although most database selection
algorithms are likely to be insensitive to small ranking errors, it is an open
question howmuch error a given algorithm can tolerate before selection accuracy
deteriorates.
4.4 Parameters
Experiments with query-based sampling require making choices about howquery
terms are selected and howmany documents are examined per query.
In our experiments, the rst query run on a database was determined by selecting
a term randomly from the TREC-123 vocabulary. The initial query could be
selected using other criteria, for example selecting a very frequent term, or it could
be selected from another resource. Several informal experiments found that the
choice of the initial query term had minimal e ect on the quality of the resource
description learned and the speed of learning, as long as it retrieved at least one
document.
Subsequent query terms were chosen byavariety of methods, as described in
the following sections. However, in all cases the terms chosen were subject to
requirements similar to those placed on index terms in many text retrieval systems:
A term selected as a query term could not be a number, and was required to be 3
or more characters long.
We had no hypotheses to guide the decision about howmany documents to
sample per database query. Instead, a series of experiments was conducted to
determine the e ect of varying this parameter.
The experiments presented belowwere ended after examining 500 documents.
This stopping criteria was chosen empirically after running several initial experi-
ments, and were biased by our interest in learning resource descriptions from small
ideally, constant sized samples. Several experiments with each database were
continued until several thousand documents were sampled, to ensure that nothing
unusual happened.
J. Callan and M. Connell
ctf ratio
| | | | | | 0.0 | | | | | |
|
|
|
|
|
|
|
|
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(a) (b)
Fig. 1. Measures of howwell a learned resource description matches the actual resource description
of a full-text database. a Percentage of database word occurrences covered by terms in the
learned resource description. b Spearman rank correlation coe cientbetween the term rankings
in the learned resource description and the database. Four documents examined per query. Each
point is the average of 10 trials.
4.5 Results
Four sets of experiments were conducted to study the accuracy of resource descriptions
learned under a variety of conditions. The rst set of experiments was an
initial investigation of query-based sampling with the parameter settings discussed
above. We call these the baseline experiments. A second set of experiments studied
the e ect of varying the number of documents examined per query. A third set
of experiments studied the e ect of varying the way query terms were selected. A
fourth set of experiments studied the e ect of varying the choice of the collection
from which documents were picked. Each set of experiments is discussed separately
below.
4.5.1 Results of Baseline Experiments. The baseline experiments were an initial
investigation of query-based sampling. The goal of the baseline experiments was to
determine whether query-based sampling produced accurate resource descriptions,
and if so, how accuracy varied as a function of the total number of documents
examined.
The initial query term was selected randomly from the TREC-123 resource de-
scription, as described above. Subsequent query terms were selected randomly from
the resource description being learned.
The top four documents retrieved byeach query were examined to update the
resource description. Duplicate documents, that is, documents that had been retrieved
previously by another query,were discarded, hence some queries produced
fewer than four documents.
Ten trials were conducted, each starting from a di erent randomly selected query
term, to compensate for the e ects of random query term selection. The experimental
results reported here are averages of results returned by the ten trials.
Query-Based Sampling of Text Databases 11

Table

3. E ect of varying the number of documents examined per query on howlongittakes a
sampling method to reachactf ratio of 80 .
Documents CACM WSJ88 TREC-123
Per Total Total Total
Query Docs Spearman Docs Spearman Docs Spearman
The variation in the measurements obtained from each trial on a particular
database was large 10 , 15 at 50 documents, but decreased rapidly.At150
documents it was 4 , 5 , and at 250 documents it was 2 , 4 . The consistency
among the trials suggests that the choice of the initial query term is not particularly
important, as long as it returns at least one document. The e ects of di erent
strategies for selecting subsequent query terms are addressed in Section 4.5.3.
Figure 1a shows that query-based sampling quickly nds the terms that account
for 80 of the non-stopword term occurrences in each collection.2 After about
250 documents, the new vocabulary being discovered consists of terms that are
relatively rare in the corpus, which is consistent with Zipf's law 43 .
Figure 1b shows the degree of agreementbetween the term orderings in the
learned and actual resource descriptions, as measured by the Spearman Rank Correlation
Coe cient. A high degree of correlation between learned and actual orderings
is observed for all collections after seeing about 250 documents. The correlation
observed for the largest collection TREC-123 is less than the correlations observed
for the smaller collections CACM and WSJ88 . Extending the number of documents
sampled beyond 500 does not substantially improve the correlation measure
on this large collection.
Results from both metrics support the hypothesis that accurate resource descriptions
can be learned by examining only a small fraction of the collection. This result
is encouraging, because it suggests that query-based sampling is a viable method
of learning accurate resource descriptions.
4.5.2 Results of Varying Sample Size. The baseline experiments sampled the four
most highly ranked documents retrieved for each query.However, the sampling
process could have retrieved more documents, or fewer documents, per query.Doing
so could change the number of queries and or documents required to achieveagiven
level of accuracy, which in turn could a ect the costs of running the algorithm.
A series of experiments was conducted to investigate the e ects of varying the
number of documents examined per query.Valuesof1,2,4,6,8,and10docu-
ments per query were tested. As in the prior experiment, ten trials were conducted
for eachvalue, each trial starting from a di erent randomly selected query term,
2Recall that stopwords were excluded from the comparison. If stopwords were included in the
comparison, the rate of convergencewould be considerably faster.
J. Callan and M. Connell
ctf ratio
CACM data CACM data
4 docs / qry
8 docs / qry
| | | | | | 0.0 | | | | | |
|
|
|
|
|
|
|
|
|
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(a) (b)
ctf ratio
WSJ88 data WSJ88 data
4 docs / qry
8 docs / qry
| | | | | | 0.0 | | | | | |
|
|
|
|
|
|
|
|
|
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(c) (d)
ctf ratio
data TREC123 data
4 docs / qry
8 docs / qry
| | | | | | 0.0 | | | | | |
|
|
|
|
|
|
|
|
|
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
Fig. 2. Measures of howwell a learned resource description matches the actual resource description
of a full-text database. Each pointistheaverage of 10 trials. a , c , and e : Percentage
of database word occurrences covered by terms in the learned resource description. b , d ,
correlation coe cientbetween the term rankings in the learned resource
description and the database.
Query-Based Sampling of Text Databases 13
with subsequent query terms chosen randomly from the resource description being
learned. Each experimental result reported belowisanaverage of the experimental
results from ten trials.
Varying the numberofdocuments per query had little e ect on the speed of
learning, as measured by the average number of documents required to reacha
given level of accuracy. Indeed, the e ect was so small that it is di cult to display
the results of di erentvalues on a single graph. Figure 2 shows results for values of
1, 4, and 8 documents per query on each database. Results for valuesof2,6,and
were very similar.

Table

3 provides another perspective on the experimental results. It shows the
number of documents required to reachactf ratio of 80 . Varying the number
of documents examined per query from 1 to 10 caused only minor variations in
performance for 2 of the 3 databases.
Careful study reveals that examining more documents per query results in slightly
faster learning fewer queries required on the small, homogeneous CACM database;
examining fewer documents per query results in somewhat faster learning on the
larger, heterogeneous TREC123 database. However, the e ects of varying the number
of documents per query are, on average, small. The most noticeable e ect is
that examining fewer documents per query results in a moreconsistent learning
speed on all databases. There was greater variation among the ten trials when
documents were examined per query 3 , 5 than when 1 documentwas
examined per query 1 , 3 .
In this experiment, larger samples worked well with the small homogeneous col-
lection, and smaller samples worked well with the large heterogeneous collection.
We do not nd this result surprising. Samples are biased by the queries that draw
them; the documents within a sample are necessarily similar to some extent. We
would expect that many small samples would better approximate a random sample
than fewer large samples in collections where there is signi cant heterogeneity.The
results support this intuition.
4.5.3 Results of Varying Query Selection Strategies. The baseline experiments
select query terms randomly from the resource description being learned. Other
selection criteria could be used, or terms could be selected from other sources.
One hypothesis was that it would be best to select terms that appear to occur
frequently in the collection, i.e., words that are nearly frequentenoughtobe
stopwords, because they would return the most random sample of documents. We
tested this hypothesis by selecting frequent query terms, as measured by document
frequency df , collection term frequency ctf , and average term frequency avg tf
ctf df .
One early concern was that learned resource descriptions would be strongly biased
by the set of documents that just happened to be examined rst, and that this bias
would be reinforced by selecting additional query terms from the learned resource
description. A solution would be to select terms from a di erent, more complete
resource description. This hypothesis was named the other resource description,
or ord hypothesis, and was compared to the default learnedresource description
or lrd approach used in the other experiments. The complete TREC-123 resource
description served as the other' resource description.
14 J. Callan and M. Connell
ctf ratio
df, ord df, ord
ctf, ord ctf, ord
| | | | 0.0 | | | |
|
|
|
|
|
|
|
|
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(a) (b)
ctf ratio
df, lrd df, lrd
ctf, lrd ctf, lrd
| | | | 0.0 | | | |
|
|
|
|
|
|
|
|
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(c) (d)
Fig. 3. Measures of how di erent query selection strategies a ect the accuracy of a learned
resource description. a and c : Percentage of database word occurrencescovered byterms
in the learned resource description. b and d : Spearman rank correlation coe cientbetween
the term rankings in the learned resource description and the database. 1988 Wall Street Journal
database. Four documents examined per query.Eachpoint for the random and lrd curves is the
average of 10 trials.
The choice of TREC-123 as the other' resource description mightbechallenged,
because WSJ88 is a subset of TREC-123. It is possible that TREC-123 mightbea
biased, or an unrealistically good, other' resource description from which to select
terms for sampling WSJ88. Wewere aware of this possible bias, and were prepared
to conduct more thorough experiments if the initial results appeared to con rm the
other' resource description hypothesis.
A series of experiments was conducted, following the same experimental methodology
used in previous experiments, except in how query terms were selected. Query
terms were selected either randomly or based on one of the frequency criteria,
from either the learned resource description lrd or the other' resource description
ord . Four documents were examined per query.Ten trials were conducted for
Query-Based Sampling of Text Databases 15

Table

4. The di erencesbetween selectingquery terms from an other resource description ord or
learned resource description lrd . Signi cantAt&Above' is the point on the curves in Figure 3 at
which the di erence between selecting from ord and lrd resources becomes statistically signi cant
t test, p 0:01 . Values for learned resource descriptions and the random selection method are
averages of 10 trials.
ctf ratio
Selection Signi cant 100 Documents 200 Documents 300 Documents
Method At & Above ord lrd ord lrd ord lrd
avg tf 20 docs 0.8651 0.8026 0.8989 0.8552 0.9130 0.8779
random 20 docs 0.8452 0.7787 0.8859 0.8401 0.9067 0.8678
ctf 190 docs 0.7920 0.7774 0.8412 0.8310 0.8625 0.8558
df
each method that selected query terms randomly or from the learned resource description
lrd , to compensate for random variation and order e ects. Experiments
were conducted on all three collections, but results were su ciently similar that
only results for the WSJ88 collection are presented here.
In all of the experiments, selecting terms from the other' resource description
produced faster learning, as measured bythenumberofdocuments required to reach
agiven level of accuracy Figure 3 . The di erences were statistically signi cant
for all four term selection methods t test, p 0:01 . However, the di erences were
relatively large for the avg tf and random selection methods, and were statistically
signi cant after only 20 documents were observed; the di erences were small for
the ctf and df selection methods, and required 130 and 190 documents respectively
to achieve statistical signi cance Table 4 . There might be some value to using an
other resource description for avg tf and random term selection methods, but there
appears to be little value for the ctf and df selection methods.
One weakness of selecting query terms from an other resource description is that
it can provide terms that do not appear in the target resource out of vocabulary'
query terms . This characteristic is particularly noticeable with avg tf and random
term selection. Avg tf and random selection from an other resource description
produced the most accurate results Table 4 , but required many more queries to
retrieveagiven number of unique documents due to out of vocabulary' queries

Table

5 . Recall also that the other' resource description TREC-123 was a
superset of the target database WSJ88 . The number of failed queries mighthave
been higher if the other' resource description had been a less similar database.
The experiments demonstrate that selecting query terms from the learned resource
description, as opposed to a more complete other' resource description,
does not produce a strongly skewed sample of documents. Indeed, random and
avg tf selection of query terms from the learned resource description provided the
best balance of accuracy and e ciency in these experiments. The worst-case behav-
ior, obtained with an other resource description that is a poor match for the target
resource, would also favor selecting terms from the learned resource description.
The experiments also demonstrate that selecting query terms randomly from
the learned resource description is more e ective than selecting them based on
high frequency. This result was a surprise, because our hypothesis was that high
J. Callan and M. Connell

Table

5. The number of queries required to retrieve 300 documents using di erent query selection
criteria.
Selection Random, Random, avg tf, avg tf, df, df, ctf, ctf
strategy ord lrd ord lrd ord lrd ord lrd
Number of queries 378 84 6,673 112 78 154 77 154
frequency terms would either occur in manycontexts, or would have relatively weak
contexts, producing a more random sample. That hypothesis was not supported
by the experiments.
4.5.4 Results of Varying the Databases Sampled. The results of the experiments
described in the preceding sections support the hypothesis that database contents
can be determined by query based sampling. However, they do not rule out a
competing hypothesis: That a relatively random sample of documents from nearly
any American English database would produce an equally accurate description of
the three test databases. Perhaps these experiments merely reveal properties of
American discourse, for example, that certain words are used commonly.
If the competing hypothesis is true, then query-based sampling is not necessary; a
partial description from any relatively similar resource would produce similar results
at lower computational cost. More importantly,itwould cast doubt on whether
partial resource descriptions distinguish databases su ciently to enable accurate
database selection. If the partial resource descriptions for most American English
databases are very similar, a database selection algorithm would presumably have
great di culty identifying the databases that best match a speci c information
need.
A series of experiments was conducted to test the hypothesis that relatively
random samples of documents from di erent American English database would
produce equally accurate descriptions of the three test databases.
The experimental method consisted of comparing the resource descriptions created
by query-based sampling of various databases to the actual, complete resource
description for the test databases. For example, resource descriptions created by
query-based sampling of CACM, WSJ88, and TREC-123 databases were compared
to the actual description for the CACM database Figures 4a and 4b . The hypothesis
would be supported if each of the learned resource descriptions were roughly
comparable in howwell they matched the actual, complete resource description of
a particular database.
Experiments were conducted with the CACM, WSJ88, and TREC-123 databases.
Comparisons were performed over 300-500 examined documents. The experimental
results are summarized in Figure 4.
The experimental results indicate that a description learned for one resource,
particularly a large resource, can contain the vocabulary that occurs frequently in
other resources. For example, the resource descriptions learned for the TREC-123
database contained the vocabulary that is frequent, and presumably important, in
the WSJ88 and CACM databases Figures 4a and 4c . The results also suggest
that prior knowledge of database characteristics might be required to decide which
descriptions to use for each database. The CACM resource description, for example,
lacked much of the vocabulary that is important to both the WSJ88 and TREC-123
Query-Based Sampling of Text Databases 17
ctf ratio0.90.70.50.30.1
|
|
|
|
|
|
|
|
|
|
|CACM database (actual) CACM database (actual)0.80.60.4
CACM (learned) 0.3 CACM (learned)
| | | | | 0.0 | | | | | |
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(a) (b)
ctf ratio0.90.70.50.30.1
|
|
|
|
|
|
|
|
|
|
|WSJ88 database (actual) WSJ88 database (actual)0.80.60.4
CACM (learned) 0.3 CACM (learned)
| | | | | 0.0 | | | | | |
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
(c) (d)
ctf ratio0.90.70.50.30.1
|
|
|
|
|
|
|
|
|
|
database (actual) TREC123 database (actual)0.80.60.4
CACM (learned) 0.3 CACM (learned)
| | | | | 0.0 | | | | | |
Spearman Rank Correlation
|
|
|
|
|
|
|
|
|
|
|
Number of documents examined Number of documents examined
Fig. 4. Measures of howwell learned resource descriptions for three di erent databases match
the actual resource description of a given database. a , c and e : Percentage of actual
database term occurrences that are covered by terms in di erent learned resource descriptions.
b , d and f : Spearman rank correlation coe cientbetween the actual term rankings and
term rankings in di erent learned resource description. Four documents examined per query.
J. Callan and M. Connell
resources Figures 4c and 4e .
The problem with using the description learned for one resource to describe
another, di erent resource is more apparent when relative term frequency is con-
sidered. Relative term frequency is important because it indicates which terms are
common in a database, and most database selection algorithms prefer databases
in which query terms are common. In these experiments, the relative frequency of
vocabulary items in the three test databases was rarely correlated Figures 4b, 4d,
and 4f . For example, neither the WSJ88 nor the TREC-123 databases gavean
accurate indication of relative term frequency in the CACM database Figure 4b .
Likewise, neither the CACM nor the TREC-123 database gave an accurate indication
of term frequency for the WSJ88 database Figure 4d . The one exception to
this trend was that the WSJ88 database did appear to give a relatively accurate
indication of relative term frequency in the TREC-123 database Figure 4f .3
These experiments refute the hypothesis that the experimental results of the earlier
sections are based upon language patterns that are common across di erent
collections of American English text. There may be considerable overlap of vocabulary
among the di erent databases, but there are also considerable di erences in
the relative frequencies of terms in each database. For example, the term com-
puter" occurs in all three databases, but its relative frequency is much higher in
the CACM database than in the WSJ88 and TREC-123 databases.
Post-experiment analysis indicates that an improved experimental methodology
would provide even stronger evidence refuting the alternate hypothesis. The ctf
ratio does not measure the fact that the description learned for TREC-123 contains
many terms not in the CACM database Figure 4a . Hence, the ctf ratio results
in Figures 4a, 4c, and 4e can overstate the degree to which the learned vocabulary
from one database re ects the actual vocabulary of a di erent database. A large
dictionary of American English would yield a ctf ratio close to 1.0 for all three of
our databases, but few people would argue that it accurately described anyofthem.
5. EXPERIMENTAL RESULTS: SELECTION ACCURACY
The experiments described in the previous section investigate howquickly and
reliably the learned resource description for a database converges upon the actual
resource description. However, we do not knowhow accurate a resource description
needs to be for accurate resource selection. Indeed, wedonoteven knowthat
description accuracy is correlated with selection accuracy, although wepresume
that it is.
The second group of experiments investigated the accuracy of resource selection
as a function of the number of documents examined. The experimental method
was based on comparing the e ectiveness of the database ranking algorithm when
using complete and learned resource descriptions. Databases were ranked with the
INQUERY IR system's default database ranking algorithm 7 .
The following sections describe the data, the type of resource description used,
the metrics, parameter settings, and nally, experimental results.
3This exception may be caused by the fact that about 10 of the TREC-123 database consists of
Wall Street Journal data.
Query-Based Sampling of Text Databases 19

Table

6. Summary statistics for the 100 databases in the testbed.
Resource Documents Per Database Bytes Per Database
Description Minimum Average Maximum Minimum Average Maximum
Actual 752 10,782 39,723 28,070,646 33,365,514 41,796,822
Learned 300 300 300 229,915 2,701,449 15,917,750
5.1 Data
The TREC-123 database described above Section 4.1 was divided into 100 smaller
databases of roughly equal size about 33 megabytes each , but varying in the number
of documents they contained Table 6 . Each database contained documents
from a single source, ordered as they were found on the TREC CDs; hence documents
in a database were also usually from similar timeframes. CD 1 contributed
37 databases, CD 2 contributed 27 databases, and CD 3 contributed 36 databases.
Queries were based on TREC topics 51-150 17 . We used query sets INQ001 and
INQ026, both created by the UMass CIIR as part of its participation in TREC-2
and Tipster 24 month evaluations 6 . Queries in these query sets are long, complex,
and have undergone automatic query expansion.
The relevance assessments were the standard TREC relevance assessments supplied
by the U.S. National Institute for Standards and Technology 17 .
5.2 Resource Descriptions
Each experiment used 100 resource descriptions one per database . Each resource
description consisted of a list of terms and their document frequencies df , as in
previous experiments. Terms on a stopword list of 418 common or closed-class
words were discarded. The remaining terms were stemmed with KStem 21 .
5.3 Metrics
Several methods have been proposed for evaluating resource selection algorithms
. The most appropriate for our needs is a recall-oriented metric
called that measures the percentage of relevant documents contained in
the n top-ranked databases.4 R is de ned as:
ni 1Ri
Ni 1Ri
where n is the number of databases searched, N is the total number of databases,
and Ri is the number of relevantdocuments contained bythei'th database.
R isacumulative searching the top 3 databases
always returns at least as many relevant documents as searching just the top 2
databases.
R is a desirable metric when the accuracy of the database ranking algorithm is
to be measured independently of other system components, and when the goal is to
rank databases containing many relevant documents ahead of databases containing
few relevant documents.
4The metric called R was called R in 23 . We use the more recent and more widely known name,
R, in this paper.
J. Callan and M. Connell< R
Complete
Learned, 700 docs
Learned, 300 docs
Learned, 100 docs
| | | | | | 0 | | |
|
|
|
|
Complete
Learned, 700 docs
Learned, 300 docs
Learned, 100 docs
| | |
Percentage of collections searched Percentage of collections searched
(a) (b)
Fig. 5. Measures of collection ranking accuracy using resource descriptions of varying accuracy.
a Topics 51-100 TREC query set INQ026 . b Topics 101-150 TREC query set INQ001 . 4
documents examined per query. TREC volumes 1, 2, and 3.
5.4 Parameter Settings
The experiments in Section 4 suggested that any relatively small sample size is
e ective, and that di erentchoices produce only small variations in results. We
chose a sample size of four 4 documents per query , to be consistent with the
baseline results in previous experiments. Query terms were chosen randomly from
the learned resource description, as in the baseline experiments.
It was unclear from the experiments in Section 4 when enough samples had been
taken. Wechose to build resource descriptions from samples of 100 documents
about queries , 300 documents about 75 queries , and 700 documents about
175 queries from each database, in order to cover the space of reasonable" numbers
of samples. If results varied dramatically,wewere prepared to conduct additional
experiments.
The collection ranking algorithm itself forces us to set one additional parameter.
The collection ranking algorithm normalizes term frequency statistics dfi;j using
the length, in words, of the collection cwj 7 . However, we do not knowhow
to estimate collection size with query-based sampling. In our experiments, term
frequency information df was normalized using the length, in words, of the set of
sampled documents used to construct the resource description.
5.5 Experimental Results
The experimental results are summarized in the two graphs in Figure 5 one per
query set . The baseline in each graph is the curveshowing results with the actual
resource description complete resource descriptions" . This is the best result that
the collection ranking algorithm can produce when given a complete description for
each collection.
Our interest is in the di erence between what is achieved with complete information
and what is achieved with incomplete information. Both graphs showonlya
small loss of e ectiveness when resource descriptions are based on 700 documents.
Query-Based Sampling of Text Databases 21
Losses grow as less information is used, but the loss is small compared to the information
reduction. Accuracy at low recall", i.e., when only 10-20 of the databases
are searched, is quite good, even when resource descriptions are based on only 100
documents.
These results are consistent with the results presented in Section 4. The earlier
experiments showed that term rankings in the learned and actual resource descriptions
were highly correlated after examining 100-300 documents.
These experimental results also demonstrate that it is possible to rank databases
without knowing their sizes. The size of the pool of documents sampled from a
database was an e ective surrogate for actual database size in these tests. Our
testing did not reveal whether this result is general, a characteristic of the CORI
database selection algorithm, or a quirk due to the 100 database testbed. The
distribution of database sizes in the testbed ranged from 752 documents to 39,723
documents, and from 28 megabytes to 42 megabytes Table 6 . A more thorough
study of this characteristic would require testbeds with a wider variety of size
distributions.
6. EXPERIMENTAL RESULTS: RETRIEVAL ACCURACY
The experiments described in the previous section demonstrate that resource descriptions
learned with query-based sampling enable accurate resource ranking.
Accurate resource ranking is generally viewed as a prerequisite to accurate document
retrieval, but it is not a guarantee. The nal document ranking depends upon
how results from di erent databases are merged, which can be in uenced bythe
quality of the resource descriptions for each database.
A third group of experiments investigated the accuracy of document retrieval in
the presence of learned resource descriptions. The experimental method was based
on comparing the accuracy of the nal document rankings produced by a distributed
system when it uses complete and learned resource descriptions to make decisions
about where to search. Databases were ranked, selected, and searched, and results
were merged into a nal document ranking by the INQUERY IR system's default
database ranking and result merging algorithms 7 .
6.1 Data
The data consisted of the same 100 databases that were used to test database
selection accuracy. Section 5.1 provides details.
6.2 Resource Descriptions
Each database was described by a learned resource description created from a sample
of 300 documents, as done in other experiments 4 documents per query,query
terms chosen randomly from the learned resource description . A sample size of
300 documents was chosen because in previous experiments it provided reasonably
accurate resource descriptions at a relatively low cost about 75 queries per
database .
Each of the 100 resource descriptions one per database consisted of a list of
terms and their document frequencies df , as in previous experiments. Terms on a
stopword list of 418 common or closed-class words were discarded. The remaining
terms were stemmed with KStem 21 .
22 J. Callan and M. Connell
6.3 Metrics
The e ectiveness of archival search systems is often measured either by Precision
at speci ed documentranks,orby Precision at speci ed Recall points. Precision at
speci ed Recall points e.g., 11-point Recall" was the standard for manyyears,
because it normalizes results based on the number of relevant documents; results
for easy" queries many relevantdocuments and  hard" queries few relevantdoc-
uments are more comparable. However, when there are many relevantdocuments,
as can be the case with large databases, Precision at speci ed Recall points focuses
attention on results that are irrelevanttomany search patrons e.g., at rank 50 and
100 .
Precision at speci ed document ranks is often used when the emphasis is on the
results a person would see in the rst few screens of an interactive system. Precision
at rank n is de ned as:
Rr
where Rr is the number of retrieved relevantdocuments in ranks 1 through n.
Precision in our experiments was measured at ranks 5, 10, 15, 20, and
uments, as is common in experiments with TREC data 17; These values
indicate the accuracy that would be observed at various points on the rst twoor
three screens of an interactive system.
6.4 Parameter Settings
All INQUERY system parameters were set to their default values for this experi-
ment. The only choices made for these experiments were decisions about howmany
databases to search, and howmany documents to return from each database.
INQUERYsearched the 10 databases ranked most highly for the query byits
database selection algorithm. The number10was chosen because it has been
used in other recent research on distributed search with the INQUERY system 39;
. The database selection algorithm ranked databases using either the learned
resource descriptions or the complete resource descriptions, as determined bythe
experimenter.
Each searched database returned its most highly ranked documents. The
number chosen because Precision was measured up to, but not beyond,
rank 30.
The returned documents 10 were merged, using INQUERY's default algorithm
for merging multi-database" search results. The algorithm for merging
results from multiple searches is based on estimating an idf,normalized score D0
for a document with a score of D in a collection with a score of C as:
Ds D , Dmin Dmax , Dmin 5
where Dmax and Dmin are the maximum and minimum possible scores anydocu-
ment in that database could obtain for the particular query,andCmax and Cmin are
Query-Based Sampling of Text Databases 23

Table

7. Precision of a search system using complete and learned resource descriptions for
database selection and result merging. TREC volumes 1, 2, and 3, divided into 100 databases. 10
databases were searched for eachquery.
Topics 51-100 query set INQ026 Topics 101-150 query set INQ001
Complete Learned Complete Learned
Document Resource Resource Resource Resource
Rank Descriptions Descriptions Descriptions Descriptions
the maximum and minimum scores any collection could obtain for the particular
query. This scaling compensates for the fact that while a system like INQUERY
can in theory produce document scores in the range 0; 1 , in practice the tf.idf algorithm
makes it mathematically impossible for a documenttohave a score outside
a relatively narrow range. Dmin and Cmin are usually 0.4, and Dmax and Cmax are
usually about 0.6. Their exact values are query-dependent, and are calculated by
setting the tf componentofthetf:idf formula to 0.0 and 1.0 for every query term
4 .
Although the theoretical justi cation for this heuristic normalization is weak, it
has been e ective in practice 1; 2; 4; 22 and has been used in INQUERY since
1995.
6.5 Experimental Results
were ranked with either an index of complete resource descriptions base-line
condition or an index of learned resource descriptions test condition . The
were searched; each returned documents. The result lists returned
by each database were merged to produce a nal result list of documents.
The scores used to rank the databases determined the value of C in Equation 6.
Precision was measured at ranks 5, 10, 15, 20, and documents. The experimental
results are summarized in Table 7.
The experimental results indicate that distributed, or multi-database", retrieval
is as e ective with learned resource descriptions as it is with complete resource
descriptions. Precision with one query set INQ026, topics 51-100 averaged 4.8
higher using learned descriptions, with a range of 2:0to7:2 . Precision with
the other query set INQ001, topics 101-150 averaged 3:2 lower using learned
descriptions, with a range of ,1:1 to ,6:1 . Both the improvement and the loss
were too small for a person to notice.
These experimental results extend the results of Section 5, which indicated that
using learned resource descriptions to rank collections introduced only a small
amount of error into the ranking process. One might argue that the amountof
error was too small to cause a noticeable change in search results, but there was no
evidence to support that argument. These results demonstrate that the small errors
introduced by learned resource descriptions do not noticeably reduce the accuracy
of the nal search results.
The accuracy of the document ranking depends also on merging results from
J. Callan and M. Connell

Table

8. A comparison of the 50 most frequent terms, as measured by document frequency,in
a text database and in a learned resource description constructed for that database. 1988 Wall
Journal database. 300 documents examined 4 documents per query .
Text Learned Text Learned
Rank Database Vocabulary Rank Database Vocabulary
million company 26 group york
new million 27 concern operate
3 company new 28 exchange stock
4 make make 29 high hold
executive
6 base base 31 operate close
7 business business price group
8 two market 33 unit international
9 trade co 34 increase increase
hold general
president 36 billion time
close two 37 end exchange
president billion 38 yesterday sale
14 stock say 39 product change
interest result
er service
month share 42 recent manage
u.s. unit 43 america made
19 sta plan 44 manage work
report expect 45 current america
plan three 46 part buy
22 say trade national
interest 48 bank
expect product 49 executive end
di erent collections accurately. The experimental results indicate that learned resource
descriptions support this activityaswell. This result is important because
INQUERY's result merging algorithm estimates a normalized document score as
a function of the collection's score and the document's score with respect to its
collection. The results indicate that not only are collections ranked appropriately
using learned descriptions, but that the scores used to rank them are highly correlated
with the scores produced with complete resource descriptions. This is further
evidence that query-based sampling produces very accurate resource descriptions.
7. A PEEK INSIDE: SUMMARIZING DATABASE CONTENTS
Our interest is primarily in an automatic method of learning resource descriptions
that are su ciently accurate and detailed for use by automatic database selection
algorithms. However, a resource description can also be used to indicate to a person
the general nature of a given text database.
The simplest method is to display the terms that occur frequently and are not
Query-Based Sampling of Text Databases 25

Table

9. The covered by the Combined Health Information database.
AIDS education Disease Prevention Health Promotion
Alzheimer's Disease Epilepsy Education and Prevention
Arthritis; Musculoskeletal and Skin Diseases Health Promotion and Education
Cancer Patient Education Kidney and Urologic Diseases
Cancer Prevention and Control Maternal and Child Health
Complementary and Alternative Medicine Medical Genetics and Rare Disorders
Deafness and Communication Disorders Oral Health
Diabetes Prenatal Smoking Cessation
Digestive Diseases Weight Control
stopwords. This method can be e ective just because the database is, in some
sense, guaranteed to be about the words that occur most often. For example, the
list of the top 50 words found by sampling the 1988 Wall Street Journal Table
8 contains words such as market", interest", trade", million", stock", and
exchange", which are indeed suggestiveoftheoverall subject of the database.

Table

8 also compares the top 50 words in the learned resource description with
the top 50 words in the database. It demonstrates that after 300 documents the
learned resource description is reasonably representativeofthevocabulary in the
target text database and it is representative of the relative importance ranks of
the terms; in this example, there is 76 agreement on the top 50 terms after seeing
just 300 documents.
Controlled experiments are essential to understanding the characteristics of a
new technique, but less controlled, real world' experimentscanalsoberevealing.
A simple database sampling system was built to test the algorithm on databases
found on the Web. The program was tested initially on the Microsoft Customer
Support Database at a time when we understood less about the most e ective
parameter settings. Accurate resource descriptions were learned, but at the cost of
examining many documents 5 .
Wechose for this paper to reproduce the earlier experiment on a more easily
accessible Web database, using sampling parameters that were consistent with
parameter settings described elsewhere in this paper. The Combined Health Information
Database 29 , which is published by several health-related agencies of the
U.S. government National Institutes of Health, Centers for Disease Control and
Prevention, and Health Resources and Services Administration was selected. The
database contains health-related information on topics, which are summarized
in

Table

9.
The initial query term was chosen randomly from the TREC-123 database. Subsequent
query terms were chosen randomly from the resource description that was
being learned. Four documents were examined per query. The experimentwas
ended after 300 documents were examined. Terms in the resource description were
sorted by collection term frequency ctf , and the top 100 terms were displayed.
The results are shown in Table 10.
One can see easily that the database contains documents about health-related
topics. Terms such as hiv", aids", health", prevention", risk", cdc", trans-
mission", medical", disease", virus", drug" and immunode ciency" showup
26 J. Callan and M. Connell

Table

10. The top 100 words found by sampling the U.S. National Institutes of Health NIH
Combined Health Information database. Terms are ranked by collection term frequency ctf in
the sampled documents. 300 documents were examined 4 documents per query .
hiv 1931 254 lg 296 296 control 168 86
aids 1561 291 mj 296 296 department 166 90
health 1161 237 ve 296 296 notes 163 163
prevention 666 195 veri cation 296 296 nt 163 163
education 534 293 yr 296 296 state 160 64
information 439 184 code 295 292 program 158 80
persons 393 174 english 294 280 video 148
number 384 296 ac 292 292 acquired 144 140
author 370 294 physical 282 267 de ciency 139 137
material 361 293 print 281 257 research 138 74
document 356 296 treatment 280 127 syndrome 138 138
human 355 212 cn 279 279 factors 137 95
source 346 296 corporate 279 279 drugs 132 68
report 328 89 description 278 266 united 132 80
accession 323 296 pd 266 266 centers 131 67
public 323 156 programs 264 112 world 131 55
update 317 296 organizations 261 126 box 130 121
community 313 107 positive 254 150 cdc 128 75
language 310 296 care 248 83 children 122 45
services 310 129 virus 246 192 patient 119 42
descriptors 308 296 disease 241 120 center 118 67
format 308 296 service 241 133 people 117 68
major 305 296 discusses 226 152 agencies 112
national 304 132 provides 226 154 government 112 63
transmission 304 114 professionals 217 167 nations 112 41
published 303 296 medical 212 117 describes 110 87
audience 302 293 immunode ciency 193 180 organization 109 51
availability 302 293 drug 190 74 sex 108
abstract 299 296 risk 185 99 std 107 50
date 299 296 issues 182 96 counseling 106 50
chid 297 296 brochure 180 54 refs 103 103
sub le 297 296 immune 179 144 surveillance 103 35
ab 296 296 examines 173 132
fm 296 296 women 171 61
high in the list.
Several of the most frequentwords appear to indicate little about the database
contents, such as update",  published", format", and   abstract". These terms
could have been removed by using a larger stopword list. However, in general
it is unclear whichwords in a multi-database environment should be considered
stopwords, since words that are unimportant in one database maybecontentwords
for others.
Query-Based Sampling of Text Databases 27

Table

11. The top 50 words found by sampling TREC-123 Terms are ranked by documentfre-
quency df in the sampled documents. 500 documents were examined 4 documents per query .
two 460 159 say 228 94 plan 163 79
new 553 158 made 246 94 million 199 79
time 437 135 result 249 93 end 556 78
three 269 128 information 706 93 allow 190 78
system 1609 122 develop 525 91 month 222 78
base 421 115 accord 322 91 set 278 77
high 585 115 service 468 90 manage 302 77
make 254 115 general 479 87 national 209 77
state 446 114 call 432 86 change 311 76
report 336 104 number 292 86 long 153 76
product 549 103 company 304 85 problem 170 75
part 371 101 show 223 83 line 271 75
group 513 101 president 339 82 close 207 75
work 256 98 require 432 80 increase 173 75
relate 269 96 people 181 79 second 882 75
operate 396 95 support 283 79 order 236 74
follow 262 94 data 608 79
This particular resource description was based on a very simple approachto
tokenizing, case conversion, and stopword removal. For example, all terms were
converted to lower case, hence it does not distinguish among terms that di er only
in case, such as aids" and   AIDS". This distinction is important in this particular
database, and illustrates some of the issues that a real world' system must address.
Appropriate lexical processing is not necessarily a major barrier, but accuracy in
real world' settings probably requires that it be addressed.
The Wall Street Journal and Combined Health Information databases are homogeneous
to varying degrees, whichmaymake it easier to summarize their contents
with brief lists of frequent terms. This summarization technique may be less e ective
with larger, heterogeneous databases such as TREC-123. The top 50 words in
the TREC-123 database Table 11 provide some evidence that the database contains
documents about U.S. national and business news, but it would be di cult
to draw rm conclusions about the database contents from this list of words alone.
Although simple word lists are e ective for summarizing database contents in
some situations, they are not necessarily the most e ectivetechniques. Frequent
phrases and common relationships can be better.
Indeed, one consequence of the sampling approach to creating learned resource
descriptions is that it makes more powerful summarizations possible. The sampling
process is not restricted just to word lists and frequency tables, nor is it restricted
to just the information the database chooses to provide. Instead, it has a set
of several hundred documents from which to mine frequent phrases, names, dates,
relationships, and other interesting information. This information is likely to enable
construction of more powerful and more informative summaries than is possible with
the simple resource descriptions used by cooperative methods.
28 J. Callan and M. Connell
8. OTHER USES
The set of documents sampled from a single database re ects the contents of that
database. One use of these documents is to build a resource description for a single
database, as described above. However, other uses are possible.
One potential use is in a query expansion database. Recent research showed that
query expansion signi cantly improves the accuracy of database selection 39 . The
state-of-the-art in query expansion is based upon analyzing the searched corpus
for co-occurrence patterns, but what database s should be used when the task is
database selection? This question has been unanswered.
If the documents sampled from each database were combined into a query expansion
corpus, the result would be a set of documents that re ects the contents and
word co-occurrence patterns across all of the available databases. It would require
little additional e ort for a database selection service to create a query expansion
database in this manner.
Co-occurrence-based query expansion can be viewed as a form of data mining.
Other forms of data mining could also be applied to the set of documents sampled
from all databases. For example, frequent concepts, names, or relationships might
be extracted and used in a visualization interface.
The ability to construct a single database that acts as a surrogate for a set of
databases is signi cant, because it could be a way of rapidly porting manyfamiliar
Information Retrieval tools to environments containing many databases. Although
there are many unanswered questions, this appears to be a promising direction for
future research.
9. CONCLUSIONS
Our hypothesis was that an accurate description of a text database can be constructed
from documents obtained by running queries on the database. Preliminary
experiments 5 supported the hypothesis, but were not conclusive. The
experiments presented in this paper test the hypothesis extensively,frommulti-
ple perspectives, and con rm the hypothesis. The resource descriptions created by
query-based sampling are su ciently similar to resource descriptions created from
complete information that it makes little di erence which is used for database selection

Query-based sampling avoids many of the limitations of cooperative protocols
suchasSTARTS. Query-based sampling can be applied to older legacy' databases
and to databases that have no incentive to cooperate. It is not as easily defeated
byintentional misrepresentation. It also avoids the problem of needing to reconcile
the di ering tokenizing, stopword lists, word stemming, case conversion, name
recognition, and other representational choices made in each database. These representation
problem are perhaps the most serious weakness of cooperative protocols,
because they exist even when all parties intend to cooperate.
The experimental results also demonstrate that the cost of query-based sampling,
as measured bythenumber of queries and documents required, is reasonably low,
and that query-based sampling is robust with respect to variations in parameter
settings.
Finally, and perhaps most importantly, the experiments described in this paper
Query-Based Sampling of Text Databases 29
demonstrate that a fairly small partial description of a resource can be as e ective
for distributed search as a complete description of that resource. This result
suggests that much of the information exchanged by cooperative protocols is un-
necessary, and that communications costs could be reduced signi cantly without
a ecting results.
The demonstrated e ectiveness of partial resource descriptions also raises questions
about which terms are necessary for describing text collections. Query-based
sampling identi es terms across a wide frequency range, but it necessarily favors
the frequent, non-stopword terms in a database. Luhn suggested that terms in the
middle of the frequency range would be best for describing documents 24 . It is an
open question whether terms in the middle of the frequency range would be best
for describing collections, too.
Several other open questions remain, among them whether the numberofdocu-
ments in a database can be estimated with query-based sampling. Wehaveshown
that this information may not be required for database selection, but it is nonetheless
desirable information. It is also an open question howmany documents must
be sampled from a resource to obtain a description of a desired accuracy, although
300-500 documents appears to be very e ective across a range of database sizes.
The work reported here can be extended in several directions, to provide a more
complete environment for searching and browsing among many databases. For ex-
ample, the documents obtained by query-based sampling could be used to provide
query expansion for database selection, or to drive a summarization or visualization
interface showing the range of information available in a multi-database environ-
ment. More generally, the ability to construct a single database that acts as a
surrogate for a large set of databases o ers many possibilities for interesting re-search

ACKNOWLEDGMENTS

We thank Aiqun Du for her work in the early stages of the research reported here.
We also thank the reviewers for their many helpful suggestions, and a reviewer for
the SIGIR conference for suggesting the experiments in Section 4.5.4.
This material is based on work supported in part by the Library of Congress
and Department of Commerce under cooperative agreementnumber EEC-9209623,
andinpartby NSF grants IIS-9873009, EIA-9983253, and EIA-9983215. Any
opinions, ndings, conclusions or recommendations expressed in this material are
the authors', and do not necessarily re ect those of the sponsors.


--R



Comparing the performance of database selection algorithms.
Evaluating database selection techniques: A testbed and experiment.
A decision-theoretic approach to database selection in networked IR
STARTS Stanford proposal for Internet meta-searching
Generalizing GLOSS to vector-space databases and broker hierarchies
The e ectiveness of GLOSS for the text database discovery problem.
Precision and recall of GLOSS estimators for database discovery.
The Second Text REtrieval Conference TREC2

Methods for informationserver selection.
Information Retrieval: Computational and Theoretical Aspects.
Word Sense Disambiguation for Large Text Databases.
Collection selection and results merging with topically organized U.
Measures in collection ranking evaluation.

The automatic creation of literature abstracts.
An experimental comparison of the e ectiveness of computers and humans as searchintermediaries.
Determiningtext databases to searchintheInternet.
Estimating the usefulness of search engines.
Facts from gures.
National Institutes of Health
National Information Standards Organization.
The impact of database selection on distributedsearching.
Numerical recipies in C: The art of scienti c computing.
Inference Networks for Document Retrieval.
Evaluation of an inference network-based retrieval model
Dissemination of collection wide information in a distributed Information Retrieval system.
Learning collection fusion strategies.
Multiple search engines in databasemerging.

ectiveretrieval of distributed collections.

Search and ranking algorithms for locating resources on the World Wide Web.
Server ranking for distributedtext retrieval systems on the Internet.
Human Behavior and the Principle of Least E ort: AnIntroduction to Human Ecology.
--TR
Evaluation of an inference network-based retrieval model
Inference networks for document retrieval
Numerical recipes in C (2nd ed.)
The effectiveness of GIOSS for the text database discovery problem
TREC and TIPSTER experiments with INQUERY
Dissemination of collection wide information in a distributed information retrieval system
Searching distributed collections with inference networks
Learning collection fusion strategies
HyPursuit
Word sense disambiguation for large text databases
A probabilistic model for distributed information retrieval
Multiple search engines in database merging
Effective retrieval with distributed collections
Evaluating database selection techniques
Methods for information server selection
Automatic discovery of language models for text databases
Comparing the performance of database selection algorithms
Cluster-based language models for distributed retrieval
A decision-theoretic approach to database selection in networked IR
Server selection on the World Wide Web
The impact of database selection on distributed searching
Collection selection and results merging with topically organized U.S. patents and TREC data
Precision and recall of <italic>GIOSS</italic> estimators for database discovery
Information Retrieval
Search and Ranking Algorithms for Locating Resources on the World Wide Web
Determining Text Databases to Search in the Internet
Generalizing GlOSS to Vector-Space Databases and Broker Hierarchies
Server Ranking for Distributed Text Retrieval Systems on the Internet
Estimating the Usefulness of Search Engines

--CTR
Leif Azzopardi , Mark Baillie , Fabio Crestani, Adaptive query-based sampling for distributed IR, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Henrik Nottelmann , Norbert Fuhr, Evaluating different methods of estimating retrieval quality for resource selection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Panagiotis G. Ipeirotis , Luis Gravano, When one sample is not improving text database selection using shrinkage, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
W. Bruce Croft , Jamie Callan, Collaborative research - digital government: a language modeling approach to metadata for cross-database linkage and search, Proceedings of the 2004 annual national conference on Digital government research, p.1-2, May 24-26, 2004, Seattle, WA
Y. L. Hedley , M. Younas , A. James , M. Sanderson, Query-related data extraction of hidden web documents, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Jared Cope , Nick Craswell , David Hawking, Automated discovery of search interfaces on the web, Proceedings of the fourteenth Australasian database conference, p.181-189, February 01, 2003, Adelaide, Australia
Ronak Desai , Qi Yang , Zonghuan Wu , Weiyi Meng , Clement Yu, Identifying redundant search engines in a very large scale metasearch engine context, Proceedings of the eighth ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA
Mark Baillie , Leif Azzopardi , Fabio Crestani, An evaluation of resource description quality measures, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Henrik Nottelmann , Norbert Fuhr, From Retrieval Status Values to Probabilities of Relevance for Advanced IR Applications, Information Retrieval, v.6 n.3-4, p.363-388, September-December
Y. L. Hedley , M. Younas , A. James , M. Sanderson, A two-phase sampling technique for information extraction from hidden web databases, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA
Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
Mark Baillie , Leif Azzopardi , Fabio Crestani, Towards better measures: evaluation of estimated resource description quality for distributed IR, Proceedings of the 1st international conference on Scalable information systems, p.41-es, May 30-June 01, 2006, Hong Kong
James Caverlee , Ling Liu , Joonsoo Bae, Distributed query sampling: a quality-conscious approach, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Jamie Callan , Fabio Crestani , Henrik Nottelmann , Pietro Pala , Xiao Mang Shou, Resource selection and data fusion in multimedia distributed digital libraries, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Demet Aksoy, Information source selection for resource constrained environments, ACM SIGMOD Record, v.34 n.4, p.15-20, December 2005
Leif Azzopardi , Maarten de Rijke, Automatic construction of known-item finding test beds, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Stefano Berretti , Alberto Del Bimbo , Pietro Pala, Merging Results for Distributed Content Based Image Retrieval, Multimedia Tools and Applications, v.24 n.3, p.215-232, December 2004
Jie Lu , Jamie Callan, Pruning long documents for distributed information retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
James Caverlee , Ling Liu , Daniel Rocco, Discovering and ranking web services with BASIL: a personalized approach with biased focus, Proceedings of the 2nd international conference on Service oriented computing, November 15-19, 2004, New York, NY, USA
semisupervised learning method to merge search engine results, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.457-491, October
Jack G. Conrad , Xi S. Guo , Cindy P. Schriber, Online duplicate document detection: signature reliability in a dynamic retrieval environment, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
Luo Si , Jamie Callan, Using sampled data and regression to merge search engine results, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland
Panagiotis G. Ipeirotis , Tom Barry , Luis Gravano, Extending SDARTS: extracting metadata from web databases and interfacing with the open archives initiative, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA
Henrik Nottelmann , Norbert Fuhr, Evaluating different methods of estimating retrieval quality for resource selection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Jack G. Conrad , Xi S. Guo , Peter Jackson , Monem Meziou, Database selection using actual physical and acquired logical collection resources in a massive domain-specific operational environment, Proceedings of the 28th international conference on Very Large Data Bases, p.71-82, August 20-23, 2002, Hong Kong, China
Milad Shokouhi , Justin Zobel , Saied Tahaghoghi , Falk Scholer, Using query logs to establish vocabularies in distributed information retrieval, Information Processing and Management: an International Journal, v.43 n.1, p.169-180, January 2007
Henrik Nottelmann , Gudrun Fischer, Search and browse services for heterogeneous collections with the peer-to-peer network Pepper, Information Processing and Management: an International Journal, v.43 n.3, p.624-642, May, 2007
Bei Yu , Guoliang Li , Karen Sollins , Anthony K. H. Tung, Effective keyword-based selection of relational databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Luo Si , Rong Jin , Jamie Callan , Paul Ogilvie, A language modeling framework for resource selection and results merging, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
M. Elena Renda , Umberto Straccia, Automatic structured query transformation over distributed digital libraries, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Yih-Ling Hedley , Muhammad Younas , Anne James , Mark Sanderson, Sampling, information extraction and summarisation of hidden web databases, Data & Knowledge Engineering, v.59 n.2, p.213-230, November 2006
Paul Ogilvie , Jamie Callan, The effectiveness of query expansion for distributed information retrieval, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
Luis Gravano , Panagiotis G. Ipeirotis , Mehran Sahami, QProber: A system for automatic classification of hidden-Web databases, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.1-41, January
Milad Shokouhi , Justin Zobel , Falk Scholer , S. M. M. Tahaghoghi, Capturing collection size for distributed non-cooperative retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Yang , Minjie Zhang, Two-stage statistical language models for text database selection, Information Retrieval, v.9 n.1, p.5-31, January   2006
Fabio Simeoni , Murat Yakici , Steve Neely , Fabio Crestani, Metadata harvesting for content-based distributed information retrieval, Journal of the American Society for Information Science and Technology, v.59 n.1, p.12-24, January 2008
Jack G. Conrad , Joanne R. S. Claussen, Early user---system interaction for database selection in massive domain-specific online environments, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.94-131, January
Jack G. Conrad , Joanne R. S. Claussen, Client-system collaboration for legal corpus selection in an online production environment, Proceedings of the 9th international conference on Artificial intelligence and law, June 24-28, 2003, Scotland, United Kingdom
Henri Avancini , Leonardo Candela , Umberto Straccia, Recommenders in a personalized, collaborative digital library environment, Journal of Intelligent Information Systems, v.28 n.3, p.253-283, June      2007
Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, To search or to crawl?: towards a query optimizer for text-centric tasks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Milad Shokouhi , Justin Zobel , Yaniv Bernstein, Distributed text retrieval from overlapping collections, Proceedings of the eighteenth conference on Australasian database, p.141-150, January 30-February 02, 2007, Ballarat, Victoria, Australia
John Gerdes, Jr., EDGAR-analyzer: automating the analysis of corporate data contained in the SEC's EDGAR database, Decision Support Systems, v.35 n.1, p.7-29, 01 April
Brian F. Cooper, Guiding queries to information sources with InfoBeacons, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
Andrei Broder , Marcus Fontura , Vanja Josifovski , Ravi Kumar , Rajeev Motwani , Shubha Nabar , Rina Panigrahy , Andrew Tomkins , Ying Xu, Estimating corpus size via queries, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Alexandros Ntoulas , Petros Zerfos , Junghoo Cho, Downloading textual hidden web content through keyword queries, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA
Massimo Melucci, On rank correlation in information retrieval evaluation, ACM SIGIR Forum, v.41 n.1, p.18-33, June 2007
resource selection;resource ranking;server selection;distributed information retrieval;query-based sampling