Efficient and effective metasearch for text databases incorporating linkages among documents.
Linkages among documents have a significant impact on the importance of documents, as it can be argued that important documents are pointed to by many documents or by other important documents. Metasearch engines can be used to facilitate ordinary users for retrieving information from multiple local sources (text databases). There is a search engine associated with each database. In a large-scale metasearch engine, the contents of each local database is represented by a representative. Each user query is evaluated against he set of representatives of all databases in order to determine the appropriate databases (search engines) to search (invoke) In previous word, the linkage information between documents has not been utilized in determining the appropriate databases to search. In this paper, such information is employed to determine the degree of relevance of a document with respect to a given query. Specifically, the importance (rank) of each document as determined by the linkages is integrated in each database representative to facilitate the selection of databases for each given query. We establish a necessary and sufficient condition to rank databases optimally, while incorporating the linkage information. A method is provided to estimate the desired quantities stated in the necessary and sufficient condition. The estimation method runs in time linearly proportional to the number of query terms. Experimental results are provided to demonstrate the high retrieval effectiveness of the method.
The Internet has become a vast information resource in recent years. To help ordinary users find
desired data in this environment, many search engines have been created. Each search engine has
a text database that is defined by the set of documents that can be searched by the search engine.
Usually, an inverted file index for all documents in the database is created and stored in the search
engine. For each term which can represent a significant word or a combination of several (usually
adjacent) significant words, this index can identify quickly the documents that contain the term.
Frequently, the information needed by a user is stored in the databases of multiple search
engines. As an example, consider the case when a user wants to find research papers in some
subject area. It is likely that the desired papers are scattered in a number of publishers' and/or
universities' databases. Substantial effort would be needed for the user to search each database
and identify useful papers from the retrieved papers. From a different perspective, as more and
more data are put on the Web at faster paces, the coverage of the Web by any single search
engine has been steadily decreasing. A solution to these problems is to implement a metasearch
engine on top of many local search engines. A metasearch engine is just an interface. It does not
maintain its own index on documents. However, a sophisticated metasearch engine may maintain
representatives which provide approximate contents of its underlying search engines in order to
provide better service. When a metasearch engine receives a user query, it first passes the query
to the appropriate local search engines, and then collects (sometimes, reorganizes) the results from
its local search engines. With such a metasearch engine, only one query is needed from the above
user to invoke multiple search engines.
A closer examination of the metasearch approach reveals the following problems. If the number
of local search engines in a metasearch engine is large, then it is likely that for a given query, only
a small percentage of all search engines may contain sufficiently useful documents to the query. In
order to avoid or reduce the possibility of invoking useless search engines for a query, we should
first identify those search engines that are most likely to provide useful results to the query and
then pass the query to only the identified search engines. Examples of systems that employ this
approach include WAIS [12], ALIWEB [15], gGlOSS [8], SavvySearch [10], ProFusion [7, 6] and
D-WISE [36]. The problem of identifying potentially useful databases to search is known as the
database selection problem. Database selection is done by comparing each query with all database
representatives. If a user only wants the m most desired documents across all local databases, for
some positive integer m, then the m documents to be retrieved from the identified databases need
to be specified and retrieved. This is the collection fusion problem.
In this paper, we present an integrated solution to the database selection problem and the
collection fusion problem, while taking into consideration the linkages between documents. In the
Web environment, documents (web pages) are linked by pointers. These linkages can indicate the
degrees of importance of documents. It may be argued that an important document is pointed to by
many documents or by important documents. For example, the home page of IBM is an important
document, as there are numerous documents on the Web pointing to it. Consider a query which
consists of a single term "IBM". There could be thousands of documents in the Internet having
such a term. However, it is likely that the user is interested in the home page of IBM. One way to
retrieve that home page is to recognize that among all the documents containing the term "IBM",
the home page of IBM is the most important one due to the numerous links pointing to it. This
phenomenon has been utilized in [22, 14] for retrieving documents in a centralized environment. In
this paper, we generalize the use of linkages in distributed text database environments to tackle the
database selection problem and the collection fusion problem. We believe that this is the first time
that the linkage information is utilized in distributed database environments involving a metasearch
engine. Our techniques for retrieval in a distributed environment yield retrieval performance that
is close to that as if all documents were stored in one database.
The rest of the paper is organized as follows. In Section 2, we incorporate the linkage information
into a similarity function so that the degree of relevance of a document to a query is determined
by both its similarity to the query as well as its degree of importance. In Section 3, we sketch our
solutions to the database selection problem and the collection fusion problem. In Section 4, we
describe the construction of the representative of a database, which indicates approximately the
contents of the database. More importantly, the representative permits the degree of relevance of
the most relevant document in the database to be estimated. This estimated quantity is central
to the database selection problem and the collection fusion problem. An estimation process is
presented. In Section 5, experimental results are provided. Very good performance is obtained for
the integrated solution of the database selection and the collection fusion problems. The conclusion
is given in Section 6.
1.1 Related Works
In the last several years, a large number of research papers on issues related to metasearch engines
or distributed collections have been published. In this subsection, we first identify the critical
difference between our work here and existing works. It is followed by other differences which are
individually identified. Only the most closely related differences are presented. Please see [21] for
a more comprehensive review of other work in this area.
1. We are not aware of any solution utilizing the linkage information among documents in
solving the database selection problem and the collection fusion problem in a metasearch
engine environment, although such information has been utilized [22, 14] in determining
the importance of documents and in their retrieval in a single search engine environment.
Thus, this is the first time that such information is utilized in a distributed text database
environment.
2. Our earlier work [32] utilizes the similarity of the most similar document in each database to
rank databases. However, in [32], we stated the condition as sufficient for ranking databases
optimally. It turns out the condition is both necessary and sufficient and is generalized in
this paper to incorporate the linkage information among documents.
3. The gGlOSS project [8] is similar in the sense that it ranks databases according to some mea-
sure. However, there is no necessary and sufficient condition for optimal ranking of databases;
there is no precise algorithm for determining which documents from which databases are to
be returned.
4. A necessary and sufficient condition for ranking databases optimally was given in [13]. How-
ever, [13] considered only the databases and queries that are for structured data. In contrast,
unstructured text data is considered in this paper. In [2], a theoretical framework was provided
for achieving optimal results in a distributed environment. Recent experimental results
reported in [3] show that if the number of documents retrieved is comparable to the number
of databases, then good retrieval effectiveness can be achieved; otherwise, there is substantial
deterioration in performance. We show good experimental results in both situations [33]. Our
theory differs from that given in [2] substantially.
5. In [29], experimental results were given to demonstrate that it was possible to retrieve documents
in distributed environments with essentially the same effectiveness as if all data were
in one site. However, the results depended on the existence of a training collection which have
similar coverage of subject matters and terms as the collection of databases to be searched.
Upon receiving a query, the training collection is searched, terms are extracted and then
added to the query before retrieval of documents from the actual collection takes place. In
the Internet environment where data are highly heterogeneous, it is unclear whether such a
training collection can in fact be constructed. Even if such a collection can be constructed,
the storage penalty could be very high in order to accommodate the heterogeneity. In [30],
it was shown that by properly clustering documents, it was possible to retrieve documents in
distributed environments with essentially the same effectiveness as in a centralized environ-
ment. However, in the Internet environment, it is not clear whether it is feasible to cluster
large collections and to perform re-clustering for dynamic changes. Our technique does not
require any clustering of documents. In addition, linkage information was not utilized in
[30, 29].
Incorporating Linkage Information into a Similarity Function
A query in this paper is simply a set of words submitted by a user. It is transformed into a vector
of terms with weights [23], where a term is essentially a content word and the dimension of the
vector is the number of all distinct terms. When a term appears in a query, the component of
the query vector corresponding to the term, which is the term weight, is positive; if it is absent,
the corresponding term weight is zero. The weight of a term usually depends on the number of
occurrences of the term in the query (relative to the total number of occurrences of all terms in
the query) [23, 34]. This is the term frequency weight. The weight of a term may also depend
on the number of documents having the term relative to the total number of documents in the
database. The weight of a term based on such information is called the inverse document frequency
weight [23, 34]. A document is similarly transformed into a vector with weights. The similarity
between a query and a document can be measured by the dot product of their respective vectors.
Often, the dot product is divided by the product of the norms of the two vectors, where the norm
of a vector
. This is to normalize the similarity between 0 and 1. The
similarity function with such a normalization is known as the Cosine function [23, 34]. For the
sake of concreteness, we shall use in this paper the version of the Cosine function [28] where the
query uses the product of the inverse document frequency weight and the term frequency weight
and the document uses the term frequency weight only. Other similarity functions, see for example
[26], are also possible.
We first define a function R which assigns the degree of relevance of a document d with respect
to a query q based on two factors: one based on the similarity between the document d and the
query q, and the other based on the rank (degree of importance) of the document. The rank of a
document in a Web environment usually depends on the linkages between the document and other
documents. For example, if a document d is linked to by many documents and/or by important
documents, then document d is an important document. Therefore, d will have a high rank. This
definition is recursive and an algorithm is given in [22] to compute the ranks of documents. The
following function incorporates both similarity and rank.
(1)
where sim() is a similarity function such as the Cosine function, NRank(d) is the normalized
rank of document d and w is a parameter between 0 and 1. In order to avoid the retrieval of
very important documents (i.e., documents with high normalized ranks) which are unrelated to
the query, the degree of relevance of a document is greater than zero only if its similarity with the
query is greater than zero. The normalized rank of a document can be obtained from the rank
computed in [22] by dividing it by the maximum rank of all documents in all databases, yielding a
value between 0 and 1. The higher the normalized rank a document has, the more important it is.
When it takes on the value 1, it is the most important document. The intuition for incorporating
rank is that if two documents have the same or about the same similarity with a query, then a user
is likely to prefer the more important document, i.e., the document with a higher rank. We assume
that the normalized ranks have been pre-computed and we are interested in finding the m most
relevant documents, i.e., the m documents with the highest degrees of relevance with respect to a
given query as defined by formula (1) in a distributed text database environment. This involves
determining the databases containing these m most relevant documents and determining which
documents from these databases need to be retrieved and transmitted to the user. In the next
section, we shall present our solution to the database selection problem and the collection fusion
problem.
Two-Level Architecture of Metasearch
In this architecture, the highest level (the root node) contains the representative for the "global
database". The global database which logically contains all documents from all local databases does
not exist physically. (Recall that all documents searchable by a search engine form a local database.
Although we call it a "local" database, it may contain documents from multiple locations.) The
representative for the global database contains all terms which appear in any of the databases and
for each such term, it stores the number of documents containing the term (i.e., the global document
frequency). This permits the global inverse document frequency weight of each query term to be
computed. There is only one additional level in the hierarchy. This level contains a representative
for each local database. The representative of each local database will be defined precisely in the
next section. When a user query is submitted, it is processed first by the metasearch engine against
all these database representatives. The databases are then ranked. Finally, the metasearch engine
invokes a subset of the search engines and co-ordinates the retrieval and merging of documents
from individual selected search engines.
3.1 Optimal Ranking of Databases
We assume that a user is interested in retrieving the m most relevant documents to his/her query
for a given m.
set of databases is said to be optimally ranked in the order [D
respect to a given query q if for every positive integer m, there exists a k such that
contain the m most relevant documents and each D i , 1  i  k, contains at least one of the m
most relevant documents.
A necessary and sufficient condition to rank databases optimally is as follows. For ease of
presentation, we shall assume that all degrees of relevance of the documents with the query are
distinct so that the set of the m most relevant documents to the query is unique.
are ranked optimally if and only if the degree of relevance
of the most relevant document in D i is larger than that of the most relevant document in
Proof:
Sufficiency: Let R i be the degree of relevance of the most relevant document in database D i .
. We need to show that [D 1
is an optimal order. We
establish by induction that for any given m, there exists a k such that are the only
databases containing the m most relevant documents with each of them containing at least one
such document.
For contains the most relevant document. Thus,
For contain the i most relevant documents with each of them containing
at least one of the i most relevant documents. When consider the (i + 1)-th most
relevant document. It appears either in one of the databases D 1 ; :::; D s
or in one of the remaining
databases. In the former case, D 1 ; :::; D s contain all of the relevant documents and
In the latter case, the (i + 1)-th most relevant document must appear in D s+1
because
. Thus, for the latter case,
Necessity: Suppose the optimal rank order of the databases is [D We now show that
the most relevant document is in database D 1 . Thus, R 1
be increased to i 1 so that the most relevant documents appear in database
1 and the i 1 -th most relevant document appears in another database D. This i 1 -th most relevant
document must be the most relevant document in D and because
are optimally
ranked, the database D must be D 2 . Thus, R 2 be increased from i 1 to
so that the i 1 -th to (i 2 \Gamma 1)-th most relevant documents appear in database D 1 or database D 2
and the i 2 -th most relevant document appears in another database D 0 . Again by the optimal rank
ordering of [D database D 0 must be D 3 and hence, R 3 repeatedly
increasing m in the manner described above, we obtain R 4
. By
combining all these derived inequalities, we obtain R 1
Example 1 Suppose there are 4 databases. For a query q, suppose the degrees of relevance of the
most relevant documents in databases are 0.8, 0.5, 0.7 and 0.2, respectively.
Then the databases should be ranked
This result applies to any similarity function as well as any function which assigns degrees of
importance to documents. It is also independent of data types. Thus, it can be applied to any type
of databases, including text databases, image databases, video databases and audio databases. The
necessary and sufficient condition to rank databases optimally is also independent of the number
of documents desired by the user.
In [32], we ranked databases in descending order of the similarity of the most similar document
in each database and its sufficiency of optimal ranking of databases was proved. The result turns
out to be generalizable to capture the degrees of relevance of documents and it is a necessary
condition as well, as stated above in Proposition 1.
3.2 Estimation of the Degree of Relevance of the Most Relevant Document in
Each Database
In the last subsection, we showed that the best way to rank databases is based on the degree
of relevance of the most relevant document in each database. Unfortunately, it is not practical
to retrieve the most relevant document from each database, obtain its degree of relevance and
then perform the ranking of the databases. However, it is possible to estimate the degree of
relevance of the most relevant document in each database, using an appropriate choice of a database
representative. This will be given in Section 4.
3.3 Coordinate the Retrieval of Documents from Different Search Engines
Suppose the databases have been ranked in the order [D briefly review an algorithm
which determines (1) the value of k such that the first k databases are searched, and (2)
which documents from these k databases should be used to form the list of m documents to be
returned to the user. Suppose the first s databases have been invoked from the metasearch engine.
Each of these search engines returns the degree of relevance of its most relevant document to the
metasearch engine which then computes the minimum of these s values. Each of the s search
engines returns documents to the metasearch engine whose degrees of relevance are greater than
or equal to the minimum. (If the number of documents in a single search engine whose degrees
of relevance are greater than or equal to the minimum value is greater than m, then that search
engine returns the m documents with the largest degrees of relevance. The remaining ones will
not be useful as the user wants only m documents with the largest degrees of relevance.) If an
accumulative total of m+add doc, where add doc is some constant which can be used as a tradeoff
between effectiveness and efficiency of retrieval, or more documents have been returned from multiple
search engines to the metasearch engine, then these documents are sorted in descending order
of degree of relevance and the first m documents are returned to the user. Otherwise, the next
database in the order will be invoked and the process is repeated until documents
are returned to the metasearch engine. It can be shown that if the databases have been ranked
optimally (with the databases containing the desired documents ahead of other databases) for a
given query, then this algorithm will retrieve all the m most relevant documents with respect to
the query. (The proof is essentially the same as that given in [32], except we replace the similarity
of a document by its degree of relevance.) When add doc ? 0, more documents will be received
by the metasearch engine (in comparison to the case add doc =0). As a result, it can select the m
best documents from a larger set of retrieved documents, resulting in better retrieval effectiveness.
However, efficiency will decrease.
4 Estimate the Degree of Relevance of the Most Relevant Document
in Each Database
We first define the representative of a database so that the degree of relevance of the most relevant
document can be estimated. It consists of all terms which appear in any document in the database.
For each term, three quantities are kept. They are the maximum integrated normalized weight, the
average normalized weight and the normalized rank of the document where the maximum integrated
normalized weight is attained. They are defined as follows. The normalized weight of the ith term
of a document
is the length or norm of document
vector d. The average normalized weight of the ith term, aw i , is simply the average value of the
normalized weights over all documents in the database, including documents not containing the
term. The integrated normalized weight of the ith term is w   d
otherwise, the integrated normalized weight is defined to be 0. In the above expression, r is the
normalized rank of document d and w is the weight of similarity relative to normalized rank in
determining the degree of relevance of a document (see formula (1)). The maximum integrated
normalized weight of the term, miw i , is the maximum value of the integrated normalized weights
over all documents in the database. Suppose the maximum value is attained by a document with
normalized rank r i . Then, for term t i , the three quantities (miw are kept.
Consider a query frequency information and inverse
document frequency information have been integrated into the query vector and the components
have been normalized.
Consider a document
is the normalized weight of term t i
and r is
the normalized rank of d. Its degree of relevance with respect to query q is w   sim(q;
This document d may have the maximum integrated normalized weight for the term t 1 and
the average normalized weights for the other terms. In that case, the above expression becomes
Finally, the rank of d is the normalized
rank of the document where the maximum integrated normalized weight (miw 1 ) for the term t 1 is
attained. As described earlier, this rank is stored in the database representative. Let it be denoted
by r 1 as it is associated with term t 1 .
In general, we estimate the degree of relevance of the most relevant document in the database by
assuming that the document contains one of the query terms having the new maximum normalized
weight. Thus, its degree of relevance may be estimated by the following expression
where the maximum is over all query terms. It is easy to see that the estimation takes time linearly
proportional to the number of query terms.
One important property of this method is that it guarantees optimal retrieval for single term
queries which are submitted frequently in the Internet. The reason is that this method estimates
the degree of relevance of the most relevant document for any given single-term query exactly. As
a result, the necessary and sufficient condition for ranking the databases optimally is satisfied. For
optimally ranked databases, the algorithm to co-ordinate the retrieval of documents from multiple
databases guarantees optimal retrieval.
Lemma 1 For any single term query, the estimate given by the above estimation method for the
degree of relevance of the most relevant document in a database is exact.
Proof: For a single term query, say the estimate given by the above method =
miw 1 . This can be obtained by setting equation (2). A
document having that term has degree of relevance
r is the rank of the document d. By the definition of the maximum integrated normalized rank of
. Thus, since miw 1 is actually achieved by a document in the database, it is the
degree of relevance of the most relevant document in the database.
Proposition 2 For any single term query, optimal retrieval of documents for the query using this
method and the co-ordination algorithm is guaranteed.
Proof: By Lemma 1, the degree of relevance of the most relevant document in each database
is estimated exactly. Using these estimates for each database guarantees optimal ranking of
databases, since the necessary and sufficient condition for optimal ranking is satisfied. Finally,
the co-ordination algorithm guarantees optimal retrieval of documents, if databases are optimally
ranked.
5 Experimental Results
In this section, we report some experimental results. Two sets of data and queries with different
characteristics are utilized. The first set of data consists of 15 databases. These databases are
formed from articles posted to 52 different newsgroups in the Internet. These articles were collected
at Stanford University [8]. Each newsgroup that contains more than 500 articles forms a separate
database. Smaller newsgroups are merged to produce larger databases. Table 1 shows the number
of documents in each database. There are altogether 6,597 queries submitted by real users. Both
database
#docs 761 1014 705 682 661 622 526 555 629 588 558 526 607 648 564

Table

1: Databases Used in Experiments
the data and the queries were used in the gGlOSS project [8]. From these 6,597 queries, we obtain
two subsets of queries. The first subset consists of the first 1,000 queries, each having no more than
6 words. They will be referred later as short queries. The second subset consists all queries having
7 or more words. There are long queries.
The second set of data consists of a subset of TREC data which were collected by NIST. We
use the first databases (20 from FBIS - Foreign Broadcast Information Service and 10 from
Congressional Record) and all of the 400 queries used in the first 8 TREC conferences.
There are approximately 57,000 documents in these databases. A typical TREC query consists
of three parts (i.e., topic, description and narrative). Since real user queries are typically short,
we only used the topic part of each query in our experiments. They are on the average longer
than the Stanford queries. Specifically, the average numbers of words in a short query (no more
than 6 words each) and in a long query (more than 6 words each) in the TREC query set are 3.29
and 12.62, respectively; the corresponding numbers for the Stanford query set are 2.3 and 10.3,
respectively. Studies show that a typical Internet queries has 2.2 terms. Thus, the Stanford short
queries resemble typical Internet queries better.
One problem we have is that the documents in these two sets do not have linkages among them-
selves. In order to simulate the effect of linkages among documents on their degrees of importance,
we assign normalized ranks to documents based on some distribution. We note that if normalized
ranks were randomly assigned to documents, then since each database has quite a few documents,
then the maximum normalized rank and the average normalized rank of each database would be
close to 1 and 0.5, respectively. This would not reflect reality. Instead, for each database, we
randomly generate a number, say x. Then the normalized ranks of the documents in that database
will be randomly assigned in the range between 0 and x. In this way, some databases have much
higher maximum normalized rank than others.
The performance measures of an algorithm to search for the m most relevant documents in a set
of databases are given as follows. The first two measures provide effectiveness (quality) of retrieval
while the last two measures provide efficiency of retrieval.
1. The percentage of correctly identified documents, that is, the ratio of the number of documents
retrieved among the m most relevant documents over m. This percentage is denoted by
cor iden doc.
2. The percentage of the sum of the degrees of relevance of the m most relevant documents
retrieved, that is, the ratio of the sum of the degrees of relevance of the m retrieved documents
over the sum of the degrees of relevance of the m most relevant documents. This percentage is
denoted by per rel doc. This represents the percentage of the expected number of relevant
documents retrieved.
Suppose a user is interested in retrieving the most relevant document which has degree of
relevance 0.95. If the retrieval system retrieves the second most relevant document with degree
of relevance 0.9 but not the most relevant document. According to the measure cor iden doc,
the percentage is 0, as none of the m 1 in this example) most relevant documents is
retrieved. Using the measure per rel doc, the percentage is 0.9/0.95. Thus, this measure is
more lenient than the measure cor iden doc. In information retrieval, the standard recall
and precision measures are related with the number of retrieved relevant documents. They
are not concerned with specific documents. In other words, if k relevant documents out of m
retrieved documents are replaced by k other relevant documents, then both recall and precision
remain unchanged. Thus, the measure per rel doc is more indicative of the standard recall
and precision measure than the measure cor iden doc.
3. The database search effort is the ratio of the number of databases searched by the algorithm
over the number of databases which contain one or more of the m most relevant documents.
This ratio is denoted by db effort. The ratio is usually more than 1.
4. The document search effort is the ratio of the number of documents received by the metasearch
engine (see Section 3.3) over m. This is a measure of the transmission cost. This ratio is
denoted by doc effort.
The experimental results for short and long queries for the Stanford data when the parameter
w in formula (1) is 0.8 are presented in Tables 2 and 3, respectively. Those for the TREC data
are given in Tables 4 and 5, respectively. The reasons for choosing w ? 0:5 are as follows: (i)
the similarity between a document and a query should play a more important role in determining
its degree of relevance between the document and the query; (ii) the way the normalized ranks of
documents are assigned makes it possible for the normalized rank of a document to be close to 1,
while in most cases, the similarity between a similar document and a query is usually no higher
than 0.3 (since a document has many more terms than the number of terms in common between
the document and a query).
cor iden doc db effort doc effort per rel doc
5 96.1% 122.0% 135.7% 99.7%

Table

2: Short queries with data
cor iden doc db effort doc effort per rel doc
5 94.7% 132.5% 150.8% 99.6%

Table

3: Long queries with data
cor iden doc db effort doc effort per rel doc

Table

4: Short queries with data
A summary of the results from Tables 2 to 5 are given as follows.
1. The method gives very good retrieval effectiveness for short queries. For the Stanford data,
the percentages of the m most relevant documents retrieved range from 96% to 98%; the
corresponding figures for the TREC data are from 88% to 96%. Recall that the short queries
cor iden doc db effort doc effort per rel doc

Table

5: Long queries with data
and in particular the Stanford queries resemble the Internet queries. The percentage of the
number of relevant documents retrieved is more impressive; it ranges from 99.7% to 99.9%
for the Stanford data; the range is from 98.8% to 99.7% for the TREC data. Thus, there is
essentially little or no loss of the number of useful documents using the retrieval algorithm in
the distributed environment versus the environment in which all documents are placed in one
site. As the number of documents to be retrieved increases, it is usually the case that both
the percentage of the most relevant documents retrieved and the percentage of the number
of relevant documents retrieved increase. The reason is that as the number of databases
accessed increases, the chance of missing desired databases will be reduced.
2. For long queries, the retrieval performance of the method is still very good, although there
is a degradation in performance. The degradation in the percentage of the most relevant
documents varies from less than 1% to 2.2% for the Stanford data; it is less than 5% for the
TREC data. As the number of terms in a query increases, the estimation accuracy decreases,
causing the degradation. The degradation is higher for the TREC data, because TREC
queries are longer. When the percentage of the number of relevant documents retrieved is
considered, there is essentially no change for the Stanford data; for the TREC data, the
percentage varies from 98.4% to 99.5%, essentially giving the same performance as if all data
were in one location.
3. The number of databases accessed by the methods is on the average at most 32.5% more than
the ideal situation in which only databases containing the desired documents are accessed. In
the tables, there are a few cases where the number of databases accessed is less than the ideal
situation. The reason is that when an undesired database is accessed, the degree of relevance,
say d, of the most relevant document in that database is obtained. If d is significantly less than
the degree of relevance of the most relevant document in a desired database D, it will cause
substantial number of documents, including some undesired documents, to be retrieved from
D. When the total number of retrieved documents is m or higher, the algorithm terminates
without accessing some desired databases.
4. The number of documents transmitted from the databases to the metasearch engine by the
method can on the average be up to 156.8% times the number of documents desired by
the user. The reason for this behavior is, based on thoroughly analyzing the results for
several queries, as follows. Suppose for a query q, the databases containing the desired
documents are fD 1 documents are to be retrieved. Suppose the ranking of
the databases is This gives optimal retrieval, guaranteeing that all the m
most relevant documents to be retrieved. However, the number of documents retrieved can
be very substantial, because after accessing the first 3 databases, finding the degrees of the
most relevant documents in these databases, taking the minimum of these degrees and then
retrieving all documents from these databases with degrees of relevance larger than or equal
to the minimum, it is possible that fewer than m documents are retrieved. As a consequence,
after accessing database D 4 , obtaining the degree of relevance of the most similar document
in D 4 and using it to retrieve more documents from the first three databases, then a lot
more documents are retrieved from these databases. However, it should be noted that in
practice, the actual documents are not transmitted from the databases to the metasearch
engine. Instead, only the titles of the documents and their URLs are transmitted. Thus, the
transmission costs would not be high.
There is a tradeoff between efficiency and effectiveness of retrieval which can be achieved using
the co-ordination algorithm given in Section 3.3. The results in Tables 2 to 5 were produced when
the metasearch engine received at least m documents. If the number of documents received by the
metasearch engine is at least m + add doc with the m most relevant documents being returned to
the user, then higher effectiveness will be achieved at the expense of more retrieved documents and
more accessed databases. Tables 6 to 9 show the results when add doc is 5, i.e., 5 more documents
are to be received at the metasearch engine. It is observed from these tables that as far as measure
per rel doc is concerned, close to optimal retrieval (at least 99.1% of the number of relevant
documents) is achieved. If the measure to retrieve the m most relevant documents is used, close to
optimal retrieval results are obtained for both the short and the long queries for the Stanford data,
but there is some room for improvement for the long queries for the TREC data. The number of
databases accessed is on the average at most 93.4% beyond what are required and the number of
documents transmitted is on the average at most 157.2% beyond what are required. These excess
high values are obtained when the method is used on long queries and
5, at least 10 documents are to be retrieved by the metasearch engine and thus doc effort is at
least 200%. As m increases and add doc stays constant, the percentage of additional documents
received at the metasearch engine decreases and thus doc effort decreases. Although doc effort
is still reasonably high for the transmission cost should not be excessive, as usually only
document titles and URLs are transmitted. The number of databases accessed is on the average
only 19.5% higher than the ideal situation, when
cor iden doc db effort doc effort per rel doc
5 99.0% 171.2% 220.6% 99.9%

Table

Short queries with additional documents retrieved
cor iden doc db effort doc effort per rel doc
5 98.4% 193.4% 257.2% 99.9%

Table

7: Long queries with additional documents retrieved
cor iden doc db effort doc effort per rel doc

Table

8: Method ITR for short queries with additional documents
retrieved
6 Conclusion
We have shown that linkage information between documents can be utilized in their retrieval from
distributed databases in a metasearch engine. This is the first time the information is employed in a
metasearch engine. Our experimental results show that the techniques we provide can yield retrieval
effectiveness close to the situation as if all documents were located in one database. The strengths
of our techniques are their simplicity (the necessary and sufficient conditions for optimal ranking
of databases, the co-ordination algorithm which guarantees optimal retrieval if the databases are
optimally ranked) and flexibility (the estimation algorithms to rank databases, while taking into
cor iden doc db effort doc effort per rel doc
5 90.6% 157.0% 264.3% 99.1%

Table

9: Long queries with additional documents retrieved
consideration the linkage information between documents). The techniques given here are readily
generalizable to the situation where there are numerous databases. In that case, it may be desirable
to place database representatives in a hierarchy and search the hierarchy so that most database
representatives need not be searched and yet the same retrieval effectiveness is achieved as if all
database representatives were searched [35].
It should be noted that the linkage information in the two collections is simulated. On the
other hand, we are not aware of an existing data collection, which has linkage information, has
information about which documents are relevant to which queries and its queries resemble Internet
queries. When such a collection is made available to us, we will perform experiments on it.

Acknowledgement

: We are grateful to L. Gravano and H. Garcia-Molina for providing us with
one of two collections of documents and queries used in our experiments. We also like to thank W.
Wu for writing some programs used in the experiments.



--R

Characterizing World Wide Web Queries.
A Probabilistic Model for Distributed Information Retrieval.
A Probabilistic solution to the selection and fusion problem in distributed Information Retrieval
Combining the Evidence of Multiple Query Representations for Information Retrieval.
Searching Distributed Collections with Inference Networks.
Adaptive Agents for Information Gathering from Multiple
Intelligent Fusion from Multiple
Generalizing GlOSS to Vector-Space databases and Broker Hierar- chies
Merging Ranks from Heterogeneous Internet sources.

Real Life Information Retrieval: A Study of User Queries on the Web.
An Information System for Corporate Users: Wide Area information Servers.
The Information Manifold.
Authoritative sources in Hyperlinked Environment.

A Statistical Method for Estimating the Usefulness of Text Databases.
The Search Broker.
Determining Text Databases to Search in the Internet.
Estimating the Usefulness of Search Engines.
Detection of Heterogeneities in a Multiple Text Database Environ- ment
Challenges and Solutions for Building an Efficient and Effective Metasearch Engine.
The PageRank Citation Ranking: Bring Order to the Web.
Introduction to Modern Information Retrieval.
Automatic Text Processing: The Transformation
The MetaCrawler Architecture for Resource Aggregation on the Web.

Learning Collection Fusion Strategies for Information Retrieval.
Learning Collection Fusion Strategies.
Effective Retrieval with Distributed Collections.


Finding the Most Similar Documents across Multiple Text Databases.
A Methodology to Retrieve Text Documents from Multiple Databases.
Principles of Database Query Processing for Advanced Applications.
Efficient and Effective Metasearch for a Large Number of Text Databases.
Server Ranking for Distributed Text Resource Systems on the Internet.
--TR
ALIWEBMYAMPERSANDmdash;Archie-like indexing in the WEB
Combining the evidence of multiple query representations for information retrieval
Searching distributed collections with inference networks
Learning collection fusion strategies
Pivoted document length normalization
A probabilistic model for distributed information retrieval
Principles of database query processing for advanced applications
Real life information retrieval: a study of user queries on the Web
Effective retrieval with distributed collections
Infoseek''s experiences searching the internet
Phrase recognition and expansion for short, precision-biased queries based on a query log
A probabilistic solution to the selection and fusion problem in distributed information retrieval
Cluster-based language models for distributed retrieval
Authoritative sources in a hyperlinked environment
Efficient and effective metasearch for a large number of text databases
The impact of database selection on distributed searching
Towards a highly-scalable and effective metasearch engine
Introduction to Modern Information Retrieval
A Methodology to Retrieve Text Documents from Multiple Databases
A Statistical Method for Estimating the Usefulness of Text Databases
Merging Ranks from Heterogeneous Internet Sources
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
Finding the Most Similar Documents across Multiple Text Databases

--CTR
King-Lup Liu , Adrain Santoso , Clement Yu , Weiyi Meng, Discovering the representative of a search engine, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
King-Lup Liu , Clement Yu , Weiyi Meng, Discovering the representative of a search engine, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Clement Yu , George Philip , Weiyi Meng, Distributed top-N query processing with possibly uncooperative local systems, Proceedings of the 29th international conference on Very large data bases, p.117-128, September 09-12, 2003, Berlin, Germany
Fang Liu , Clement Yu , Weiyi Meng, Personalized web search by mapping user queries to categories, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Zonghuan Wu , Weiyi Meng , Clement Yu , Zhuogang Li, Towards a highly-scalable and effective metasearch engine, Proceedings of the 10th international conference on World Wide Web, p.386-395, May 01-05, 2001, Hong Kong, Hong Kong
Fang Liu , Clement Yu , Weiyi Meng, Personalized Web Search For Improving Retrieval Effectiveness, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.28-40, January 2004
Weiyi Meng , Zonghuan Wu , Clement Yu , Zhuogang Li, A highly scalable and effective method for metasearch, ACM Transactions on Information Systems (TOIS), v.19 n.3, p.310-335, July 2001
Weiyi Meng , Clement Yu , King-Lup Liu, Building efficient and effective metasearch engines, ACM Computing Surveys (CSUR), v.34 n.1, p.48-89, March 2002
J. Bhogal , A. Macfarlane , P. Smith, A review of ontology based query expansion, Information Processing and Management: an International Journal, v.43 n.4, p.866-886, July, 2007
metasearch;linkages among documents;information retrieval;distributed collection