Data structures for efficient broker implementation.
With the profusion of text databases on the Internet, it is becoming increasingly hard to find the most useful databases for a given query. To attack this problem, several existing and proposed systems employ brokers to direct user queries, using a local database of summary information about the available databases. This summary information must effectively distinguish relevant databases and must be compact while allowing efficient access. We offer evidence that one broker, GlOSS, can be effective at locating databases of interest even in a system of hundreds of databased and can examine the performance of accessing the GlOSS summeries for two promising storage methods: the grid file and partitioned hashing. We show that both methods can be tuned to provide good performance for a  particular workload (within a broad range of workloads), and we discuss the tradeoffs between the two data structures. As a side effect of our work, we show that grid files are more broadly applicable than previously thought; inparticular, we show that by varying the policies used to construct the grid file we can provide good performance for a wide range of workloads even when storing highly skewed data.
Introduction
The last few years have seen an explosion in the amount of information that is available online.
The falling costs of storage, processing, and communications have all contributed to this explosion,
as has the emergence of the infrastructure provided by the World-Wide Web and its associated
applications. Increasingly, the key issue is not whether some piece of information is available online,
but where. As a result, an emerging area of research concerns brokers, systems that help users locate
the text databases that are most likely to contain answers to their queries. To perform this service,
brokers use summary information about the available databases. Brokers must be able both to
query and to update this summary information. A central problem in broker design is to find a
representation for summary information that is both effective in its ability to select appropriate
information resources, and efficient to query and maintain.
GlOSS (Glossary-Of-Servers Server) [17, 18] is one broker that keeps database summaries to
choose the most promising databases for a given query. Initial studies of GlOSS are encouraging.
This work was partially supported by ARPA Contract F33615-93-1-1339.
y INRIA Rocquencourt, 78153 Le Chesnay, France. E-mail: Anthony.Tomasic@inria.fr
z Computer Science Department, Stanford University, Stanford, CA 94305-2140, USA. E-mail:
x Current address: Trident Systems, Sunnyvale, CA, USA. E-mail: clue@tridmicr.com
Department K55/801, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120-6099, USA. E-mail:
schwarz@almaden.ibm.com, laura@almaden.ibm.com
Experiments with a small number of databases indicate that although the GlOSS summaries are
orders of magnitude smaller than the information that they summarize, they contain enough information
to select the best databases for a query. In this paper, we show that the GlOSS summaries
can be employed as the representation for summary information in a large scale system. In par-
ticular, we offer evidence that GlOSS can effectively locate databases of interest even in a system
of hundreds of databases, and we suggest appropriate data structures for storing such large scale
GlOSS summaries.
We experiment with two data structures, partitioned (multi-attribute) hashing and the grid
file. Partitioned hashing offers the best average case performance for a wide range of workloads -
if the number of hash buckets is chosen correctly. However, the grid file performs well, and grows
more gracefully as the number or size of the summaries increases.
Grid files were developed to store spatial data, and are typically employed for data that is
fairly uniformly distributed. The GlOSS summaries we store are highly skewed. We show that by
varying the splitting policy used to construct a grid file we can provide good performance for a
wide range of workloads even when storing such highly skewed data. Thus, as a side effect of our
work, we demonstrate that grid files are more generally applicable than previously believed, and
provide an exploration of the effect of different splitting policies on grid file performance.
In summary, this paper studies an emerging problem in the construction of distributed information
retrieval systems, namely, the performance of brokers for accessing and updating summary
information. Section 2 reviews the GlOSS representation of summary information. Section 3 discusses
GlOSS's effectiveness when there are large numbers of databases. The next four sections
focus on choosing a storage method for the summary information. Section 4 discusses the issues
involved in choosing a storage method, and describes some alternatives. Section 5 introduces the
idea of using a grid file to store the GlOSS summaries, describes various splitting policies for managing
grid file growth, and presents a simulation study of grid file performance over a range of
workloads, for several splitting policies. Section 6 examines partitioned hashing as an alternative
method for efficiently storing GlOSS summaries. Section 7 compares the results from the two
storage methods, and explains why we recommend the grid file. Section 8 positions our work with
respect to other work on brokers, and the last section summarizes our results and our conclusions,
and provides some ideas for future work.
GlOSS-Glossary-Of-Servers Server
In this section we briefly describe how GlOSS helps users choose databases at which a query
should be evaluated. Users first submit their query to GlOSS to obtain a ranking of the databases
according to their potential usefulness for the given query. The information used by GlOSS to
produce this ranking consists of a vector that indicates how many documents in the database
contain each word in the database vocabulary, and a count of the total number of documents in
the database [17]. This summary information is much smaller than the complete contents of the
database, so this approach scales well as the number of available databases increases.

Table

1 shows a portion of the GlOSS summaries for two databases. Each row corresponds
to a word and each column to a database. For example, the word "information" appears in 1234
documents in database db 1 , and in 30 documents in database db 2 . The last row of the table shows
the total number of documents in each database: database db 1 has 1234 documents, while database
db 2 has 1000 documents.
To rank the databases for a given query, GlOSS estimates the number of documents that match
the query at each database. GlOSS can produce these estimates from the GlOSS summaries in
a variety of ways. One possibility for GlOSS is to assume that the query words appear in docu-
database
word db 1 db 2
information 1234
retrieval
documents 1234 1000

Table

1: Part of the GlOSS summaries of two databases.
ments following independent and uniform probability distributions, and to estimate the number
of documents matching a query at a database accordingly. For example, for query "information
AND retrieval," the expected number of matches in db 1 (using the GlOSS summary information of

Table

and the expected number of matches in db 2 is 9.
GlOSS would then return db 1 as the most promising database for the query, followed by db 2 . Several
other estimation functions are given in [18].
3 Effectiveness of GlOSS
Given a set of candidate databases and a set of queries, we explored the ability of GlOSS to suggest
appropriate databases for each query. The original GlOSS studies [17, 18] tested GlOSS's ability
to select among six databases. To be sure that GlOSS would be useful as a large scale broker, we
scaled up the number of databases by about two orders of magnitude. In this section, we describe
a set of experiments that demonstrate that GlOSS can select relevant databases effectively from
among a large set of candidates. We present a metric for evaluating how closely the list of databases
suggested by GlOSS corresponds to an "optimal" list, and evaluate GlOSS based on this metric.
For our experiments, we used as data the complete set of United States patents for 1991. Each
patent issued is described by an entry that includes various attributes (e.g., names of the patent
owners, issuing date) as well as a text description of the patent. The total size of the patent data
is 3.4 gigabytes. We divided the patents into 500 databases by first partitioning them into fifty
groups based on date of issue, and then dividing each of these groups into ten subgroups, based on
the high order digit of a subject-related patent classification code. This partitioning scheme gave
databases that ranged in size by an order of magnitude, and were at least somewhat differentiated
by subject. Both properties are ones we would expect to see in a real distributed environment.
For test queries, we used a set of 3,719 queries submitted against the INSPEC database offered
by Stanford University through its FOLIO boolean information retrieval system. INSPEC is not a
patent database, but it covers a similar range of technical subjects, so we expected a fair number
of hits against our patent data. Each query is a boolean conjunction of one or more words, e.g.,
"microwave AND interferometer." A document is considered to match a query if it contains all
the words in the conjunction.
To test GlOSS's ability to locate the databases with the greatest number of matching docu-
ments, we compared its recommendations to those of an "omniscient" database selection mechanism
implemented using a full-text index of the contents of our 500 patent databases. For each query,
we found the exact number of matching documents in each database, using the full-text index, and
ranked the databases accordingly. We compared this ranking with the ranking suggested by GlOSS
by calculating, for various values of N , the ratio between the total number of matching documents
in the top N databases recommended by GlOSS and the total number of matching documents
in the N best databases according to the ideal ranking. This metric, the normalized cumulative
Mean Std. Dev.
9 0.764 0.299

Table

2: Normalized cumulative recall for 500 databases for the INSPEC trace.
recall, approaches 1.0 as N approaches 500, the number of databases, but is most interesting when
N is small. Because this metric is not meaningful for queries with no matching documents in any
database, we eliminated such queries, reducing the number of queries in our sample to 3,286.

Table

2 shows the results of this experiment. The table suggests that compared to an omniscient
selector, GlOSS does a reasonable job of selecting relevant databases, on average finding over
seventy percent of the documents that could be found by examining an equal number of databases
under ideal circumstances, with gradual improvement as the number of databases examined in-
creases. The large standard deviations arise because although GlOSS performs very well for the
majority of queries, there remains a stubborn minority for which performance is very poor. Nev-
ertheless, using GlOSS gives a dramatic improvement over randomly selecting databases to search,
for a fraction of the storage cost of a full-text index.
We felt these initial results were promising enough to pursue the use of GlOSS's representation
for summary information. A more rigorous investigation is in progress. Ideally, we would like
to use a real set of test databases instead of one constructed by partitioning, and a matching
set of queries submitted against these same databases, including boolean disjunctions as well as
conjunctions. We will try to characterize those queries for which GlOSS performs poorly, and to
study the impact of the number of query terms on effectiveness. Other metrics will be included.
For example, a metric that revealed whether the matching documents were scattered thinly across
many databases or concentrated in a few large clumps would allow us to measure the corresponding
impact on effectiveness. Effectiveness can also be measured using information retrieval metrics [7].
4 Alternative Data Structures for GlOSS Summaries
The choice of a good data structure to store the GlOSS summaries depends on the type and
frequency of operations at the GlOSS servers. A GlOSS server needs to support two types of
operations efficiently: query processing and summary updates. When a query arrives, GlOSS has
to access the complete set of document frequencies associated with each query keyword. When
new or updated summaries arrive, GlOSS has to update its data structure, operating on the
frequencies associated with a single database. Efficient access by database might also be needed
if different brokers exchange database summaries to develop "expertise" [32], or if we allow users
to do relevance feedback [31] and ask for databases "similar" to some given database. The two
types of operations pose conflicting requirements on the GlOSS data structure: to process queries,
GlOSS needs fast access to the table by word, whereas to handle frequency updates, GlOSS needs
fast access to the table by database.
Thus, ideally we would like to simultaneously minimize the access cost in both dimensions. In
general, however, the costs of word and database access trade off. Consequently, one must consider
the relative frequencies of these operations, and try to find a policy that minimizes overall cost.
Unfortunately, the relative frequencies of word and database access are difficult to estimate. They
depend on other parameters, such as the number of databases covered by GlOSS, the intensity of
query traffic, the actual frequency of summary updates, etc.
Just to illustrate the tradeoffs, let us assume that query processing is the most frequent opera-
tion, and that a GlOSS server receives 200,000 query requests per day (a typical rate for the Lycos
World-Wide Web index 1 ). Likewise, let us assume that we update each database summary once
a day. Given this scenario, and if GlOSS covers 500 databases, the ratio of accesses by word to
accesses by database would be about 400:1, and our data structure might therefore favor the performance
of accesses by word over that by database in the same proportion. However, if the server
received 350,000 queries a day, or covered a different number of databases, or received updates
more frequently, a vastly different ratio could occur. Therefore, GlOSS needs a data structure that
can be tuned to adapt to the actual conditions observed in practice.
A simple data organization for GlOSS is to cluster the records according to their associated
word, and to build some index on the words (e.g., a sparse B + tree), to provide efficient access
by word [17], thus yielding fast query processing. To implement GlOSS using this approach, we
could adapt any of the techniques for building inverted files for documents (e.g.,[8], [42], [37],
[6]). However, this approach does not support fast access by database, for updating summaries or
exchanging them with other brokers.
Organizations for "spatial" data provide a variety of techniques that we can apply for GlOSS.
In particular, we are interested in techniques that support partial-match queries efficiently, because
we need to access the GlOSS records by word and by database. Tree-based approaches, including
quad trees, k-d trees, K-D-B trees [39], R trees [19], R trees [34], and BV trees [15], are not
well suited for this type of access: to answer a partial-match query, we might have to follow too
many paths from the root of the tree to its leaves. A similar problem arises with techniques like
the ones based on the "z order" [29]. In contrast, the directory structure of grid files [26] and
the addressing scheme for partitioned or multiattribute hashing [22] make them well suited for
answering partial-match queries.
5 Using Grid Files for GlOSS
In this section we describe how grid files [26] can be used to store the GlOSS summaries, and
describe a series of experiments that explore their performance. We show how to tune the grid file
to favor access to the summary information by word or by database.
5.1 Grid File Basics
A grid file consists of data blocks, stored on disk and containing the actual data records, and a
directory that maps multi-dimensional keys to data blocks. For GlOSS, the (two-dimensional)
are (word, database identifier) pairs. Initially there is only one data block, and the directory
consists of a single entry pointing to the only data block. Records are inserted in this data block
until it becomes full and has to be split into two blocks. The grid file directory changes to reflect
1 Lycos is accessible at http://lycos.cs.cmu.edu.
Directory
db1 db6
a
(ostrich, db3, 2)
Data Block
Directory
db1 db3 db6
Directory
a
db1 db3 db6
Data Block Data Block
z z
(1) (2)
(llama, db5, 5)
Data Block
Data Block
(buffalo, db2, 2) (llama, db5, 5)
(llama, db5, 5)
a
z
(ostrich, db3, 2)
Data Block

Figure

1: The successive configurations of a grid file during record insertion.
the splitting of the data block.

Figure

1 shows a grid file where the data blocks have capacity for two records. In (1), we have
inserted two records into the grid file: (llama, db 5 , 5) and (zebra, db 1 , 2). There is only one data
block (filled to capacity) containing the two records, and only one directory entry pointing to the
only data block.
To insert record (ostrich, db 3 , 2), we locate the data block where the record belongs by first
reading the directory entry corresponding to word ostrich and database db 3 . Since the data block
is full, we have to split it. We can split the data block between different databases, or between
different words. In (2), we split the data block between databases: all records with databases in
the range go to one block, and all records with databases in the (db 4 range go to
the other block. We also split the grid file directory to contain two entries, one pointing to each of
the data blocks.
To insert record (buffalo, db 2 , 2), we first locate the data block where the record belongs: by
looking at the directory, we find the pointer associated with range (db 1 ; db 3 ) and (a; z), and the
corresponding data block. This data block already has two records in it, (ostrich, db 3 , 2) and
so the insertion of the new tuple causes the data block to overflow. In (3), we split
the data block between words, and we reflect this splitting in the directory by creating a new row
in it. The first row of the directory corresponds to word range (a; m), and the second to word range
(n; z). Thus, the overflowed data block is split into one block with record (buffalo, db 2 , 2), and
another block with records (ostrich, db 3 , 2) and (zebra, db 1 , 2). Note that both directory entries
corresponding to database range (db 4 point to the same data block, which has not overflowed
and thus does not need to be split yet. These two directory entries form a region. Regions may
contain any number of directory entries, but are always convex in our grid files. We will refer to
a division between directory entries in a region as a partition of the region. The region in the
example directory contains a single partition.
To locate the portion of the directory that corresponds to the record we are looking for, we
keep one scale per dimension of the grid file. These scales are one-dimensional arrays that indicate
what partitions have taken place in each dimension. For example, the word scale for the grid file
configuration in (3) is (a; m; z), and the corresponding database scale is (db
5.2 Splitting Blocks
The rule that is used to decide how to split a data block is called the splitting policy. The splitting
policy can be used to adjust the overall cost of using a grid file to store our summary information.
Our goal is to find and evaluate splitting policies that are easily parameterized to support an
observed ratio between the frequency of word and database accesses. We describe two extreme
splitting policies that characterize the endpoints of the spectrum of splitting behavior, and then
introduce three additional parameterized policies that can be adjusted to minimize overall cost.
To insert a record into the GlOSS grid file, we first find the block where the record belongs,
using the grid file directory. If the record fits in this block, then we insert it. 2 Otherwise, the block
must be split, either by dividing it between two words or by dividing it between two databases.
Splitting between databases tends to benefit access by database, whereas splitting between words
tends to benefit access by word. This choice of splitting dimension is therefore the basic tool for
controlling relative access costs.
To limit the growth of the grid file directory, however, we always look for ways to split the block
that take advantage of pre-existing partitions in the directory. 3 If more than one entry in the grid
file directory maps to the overflowed block, and if this region of the directory contains at least one
partition (either between words or between databases) such that the regions on either side of the
partition are non-empty, then we can use one such pre-existing partition to split the block without
introducing new entries into the directory. If more than one such partition exists, we favor those
between databases over those between words. If multiple partitions exist in a single dimension, we
choose the one that splits the block most nearly in half. (See Section 5.4 for a variation of this
policy that reduces the amount of unused space in blocks.)
To be precise, Figure 2 shows the basic algorithm for inserting a record into the grid file. Line
1 computes the region and block where the record should be inserted according to the database
and word scales for the grid file directory. Line 2 attempts to insert the record. If there is no
overflow, the insertion succeeds. Otherwise, there is overflow in the block. Line 5 checks the region
in which the record is being inserted for a partition in the database scale. If there is a partition,
the region is divided in half along a partition line, and the records in the block of the region are
redistributed between the old and new block. The new block is assigned to the new region. This
process eliminates a partition of the region by creating a new region. Lines 7-8 do the same for the
word scale. If there are no qualifying partitions (line 10), we need to create one by introducing a
new row (or column) in the directory.

Table

3 describes several policies for choosing a splitting dimension. The DB-always policy
always attempts to split the block between databases, thus favoring access by database over access
by word. Conversely, the Word-always policy always attempts to split between words, thus favoring
access by word over access by database. In between these two extremes lies a spectrum of other
possibilities. The Bounded policy allows the database scale of the grid file directory to be split up
2 We can compress the contents of each block of the grid file by applying methods used for storing sparse matrices
efficiently [30], or by using the methods in [42] for compressing inverted files, for example. Any of these methods will
effectively increase the capacity of the disk blocks in terms of the number of records that they can hold.
3 Several alternative organizations for the grid file directory control its growth and make it proportional to the
data size. These alternative organizations include the region-representation directory and the BR 2 directory [3]. The
2-level directory organization [20] shows how to implement the directory on disk. We have not yet explored how
these techniques would work in our environment.
1. Compute region and block for record
2. If Record fits in block
3. Insert record
4. Else
5. If Usable partitions in database scale
6. Divide region in half on database scale
7. Else If Usable partitions on word scale
8. Divide region in half on word scale
9. Else
10. Split directory
11. Divide region on chosen scale
12. Insert record

Figure

2: Algorithm for inserting a record in a grid file for GlOSS.
Policy Splitting dimension
DB-always Database
Word-always Word
Bounded If DB-splits ! bound then Database else Word
Probabilistic If Random() ! prob-bound then Database else Word
Prepartition Like Word-always, after prepartitioning on Database

Table

3: Different policies for choosing the splitting dimension.
to bound times, and then resorts to splitting between words. Thus, it allows some splits between
databases (which favor access by database), while putting an upper bound on the number of
block reads that might be needed to access all the records for a word. If bound is set to infinity,
then Bounded behaves as DB-always, whereas if bound is set to zero, then Bounded behaves as
Word-always. The Probabilistic policy splits between databases with probability prob-bound.
Unlike the Bounded policy, which favors splitting between databases initially, this policy allows the
choice of splitting dimension to be made independently at each split. The Prepartition policy
works like Word-always, except that the database scale of the directory is prepartitioned into m
regions before any databases are inserted, to see if "seeding" the database scale with evenly-spaced
partitions improves performance. The size of each region is b m
db c, where db is the number of available
databases.
Note that once a scale has been chosen, it may not be possible to split the block on that scale.
For instance, we may choose to split a block on the database scale, but the scale may have only a
single value associated with that block (and consequently, every record in the block has the same
database value). In this case, we automatically split on the other scale.
5.3 Metrics for Evaluation
To evaluate the policies of Table 3, we implemented a simulation of the grid file in C++ on an IBM
RISC/6000 workstation and ran experiments using 200 of the 500 patent databases described in
Section 3 (around 1.3 gigabytes of data). The resulting grid file had 200 columns (one for each of
the 200 databases) and 402,044 rows (one for each distinct word appearing in the patent records).
The file contained 2,999,676 total records. At four bytes per entry, we assumed that each disk
block could hold 512 records.
Our evaluation of the various policies is based on the following metrics:
DB Splits Number of splits that occurred in the database scale.
Word Splits Number of splits that occurred in the word scale.
Total Blocks The total number of blocks in the grid file (excluding the scales and the directory).
Block-fill factor The ratio of used block space to total block space. This measure indicates how
effectively data is packed into blocks.
Directory Size The number of entries in the database scale of the grid file directory times number
of entries in the word scale. This measure indicates the overhead cost of the grid file directory.
About four bytes would be needed for each directory entry in an actual implementation.
Average Word (or Database) Access Cost The number of blocks accessed in reading all the
records for a single word (or database), i.e., an entire row (or column) of the grid file, averaged
over all words (or databases) on the corresponding scale.
Expansion Factor for Words (or Databases) The ratio between the number of blocks accessed
in reading all the records for a single word or database and the minimum number
of blocks that would be required to store that many records, averaged over all words or
databases on the corresponding scale. This metric compares the access cost using the grid
file to the best possible access cost that could be achieved. Note that since we assume that
512 records can be stored in a block, and there are only 200 databases, all the records for a
single word can always fit in one block. Thus the minimum number of blocks required for
each word is one, and the expansion factor for words is always equal to the average word
access cost.
Average Trace Word Access Cost and Expansion Factor for Trace Words Similar to the
word scale metrics, but averaged over the words occurring in a representative set of patent
queries, instead of over all words. For this measurement, we used 1767 queries issued by
real users in November 1994, against a full-text patent database accessible at http://-
town.hall.org/patent/patent.html. These queries contain 2828 words that appear in at
least one of our 200 databases (counting repetitions). This represents less than one percent
of the total vocabulary, but query words from the trace (trace words) occur on average in
99.96 databases compared to the average of 7.46 for all words. Thus trace words occur with
relatively high frequency in the databases.
Weighted (Trace) Average Cost This metric gives the overall cost of using the grid file, given
an observed ratio between word and database accesses. It is calculated by multiplying the
word-to-database access ratio by the average (trace) word access cost, and adding the average
database access cost. For example, if the ratio of word to database accesses is observed to
be 100:1, the weighted average cost is (100 * average word access cost) average database
access cost.
Although the choice of splitting policy is the major factor in determining the behavior of the
grid file, performance is also sensitive to a number of other, more subtle, variations in how the
GlOSS summaries are mapped onto the grid file. We therefore discuss these variants before moving
on to the main body of our results.
5.4 Mapping GlOSS to a Grid File
To insert the GlOSS summary data for a database into a grid file, one must first define a mapping
from each word to an integer that corresponds to a row in the grid file. We explored two alternatives
for this mapping, alpha and freq. In the alpha mapping, all the words in all the databases are
gathered into a single alphabetically ordered list, and then assigned sequential integer identifiers.
In the freq mapping, the same set of words is ordered by frequency, instead of alphabetically,
where the frequency for a word is the sum of the frequencies for that word across all summaries. 4
This difference in mapping has two effects. First, although the vast majority of rows have
exactly one record, the freq map clusters those rows having multiple records in the upper part of
the grid file, and the top rows of the grid file contain a record for every database. In the alpha map,
the rows with multiple records are spread throughout the grid file. (By contrast, the distribution
of records across the columns of the grid file is fairly uniform.)
The second effect is due to the fact that, as an artifact of its construction, the summary for
each database is ordered alphabetically. For the alpha mapping, therefore, (word id, frequency)
pairs are inserted in increasing, but non-sequential, word-identifier order. By contrast, with the
are inserted in essentially random order, since the words
are ordered alphabetically but the identifiers are ordered by frequency.
Similar considerations pertain to the order in which databases are inserted into the grid file.
We considered sequential ordering (seq) and random ordering (random). In the seq case, database
1 is inserted with database identifier 1, database 2 with database identifier 2, etc. In the random
ordering, the mapping is permuted randomly. The seq ordering corresponds to statically loading
the grid file from a collection of summaries. The random ordering corresponds to the dynamic
addition and deletion of summaries as information is updated or exchanged among brokers.
In practice, one could approximate the freq mapping by using a predefined mapping table for relatively common
words, and assigning identifiers in order for the remaining (infrequent) words.
Mapping Splits Average Cost Total Block-Fill Directory
Word Database Policy Word DB Word DB Blocks Factor Size
alpha seq middle 119 117 104.92 109.69 10859 .54 13923
alpha seq right 138 115 83.55 115.89 8584 .68 15870
alpha random middle 204 85 61.03 159.40 9258 .63 17340
alpha random right 187 120 87.34 133.44 10586 .55 22440
freq seq right 118 167 58.41 108.36 8750 .67 19706
random middle 194 127 69.14 128.30 9737 .60 24638
freq random right 167 142 83.29 118.77 10398 .56 23714

Table

4: The DB-always policy for the different mapping and splitting options.
A consequence of the seq ordering is that insertion of data into the grid file is very deterministic.
In particular, we noticed that our default means of choosing a partition in the case of overflow was
a bad one. Since databases are inserted left to right, the left-hand member of a pair of split blocks
is never revisited: subsequent insertions will always insert into the right-hand block. Thus, when
the database scale is split (in line 11 of the algorithm in Figure 2), it would be advantageous to
choose the rightmost value in the block as the value to split on. Furthermore, if given a choice of
pre-existing partitions to use in splitting a block, it would be advantageous to choose the rightmost
partition for splitting (in line 6 of the algorithm). To examine this effect, we parameterized the
algorithm in Figure 2 to choose either the rightmost value or partition (right) or the middlemost
value or partition (middle), as per the original algorithm.
We ran experiments for the eight combinations of mapping and splitting options above for the
DB-always, Word-always, Bounded, and Probabilistic policies. Table 4 shows the results for
the DB-always policy, but the conclusions we draw here apply to the other policies as well. Note
that the combination of options chosen can have a significant effect on performance. The average
word access cost for the worst combination of options is 1.8 times the average word access cost for
the best combination. For average database access cost, this factor is about 1.5. Block-fill factor
varies from a worst case of 0.46 to a best case of 0.68.
The table shows that the combination of frequency ordering for assignment of word identifiers,
sequential insertion of databases, and the right option for block splitting achieves the lowest
access costs, both by word and by database, and has a block-fill factor only slightly poorer than
the best observed. Therefore, we used this combination for our subsequent experiments. The base
parameters for these experiments are summarized in Table 5.
5.5 Comparison of Splitting Policies
We begin our comparison of the splitting policies by examining the basic behavior of each of the five
policies. Tables 6 and 7 provide performance measurements for each policy; for the parameterized
policies (Probabilistic, Prepartition and Bounded) we present data for a single representative
parameter value, and defer discussion of other parameter values to later in this section.
We start with the Word-always policy, since its behavior is very regular. At the start of the
experiment, there is a single empty block. As databases are inserted, the block overflows, and the
word scale is split at a point that balances the resulting blocks. By the time all 200 databases have
been inserted, the word scale has been split 8878 times. In the resulting grid file, each data block
therefore contains complete frequency information for some number of words, i.e., multiple rows of
Parameter Value
Words (rows) 402,044
Records 2,999,676
Records per block 512
Database Insertion seq
Word Insertion freq
Block division right

Table

5: Parameter values for the base set of experiments. See Section 5.4 for a description of the
parameters.
Splits Total Block-Fill Directory
Policy Word DB Blocks Factor Size
Probabilistic (0.5) 202 101 8887 .66 20402
Prepartition
Bounded

Table

Performance measurements for the base experiment for the five policies introduced in
Section 5.2.
the grid file. The number of words in a data block depends on the number of databases in which the
corresponding words appear. As expected, the average word access cost is one block read. Clearly,
this policy is the most favorable one possible for access by word. To access all the records for a
database, however, every block must be read. The average database access cost therefore equals
the total number of blocks in the file. This policy minimizes the size of the grid file directory, since
it reduces the directory to a one-dimensional vector of pointers to the data blocks.
Next, consider the DB-always policy. Our measurements show that the database scale was split
167 times. However, the size of the grid file far exceeds the capacity of 167 blocks, so splitting
must occur between words as well (cf. Section 5.2). Such splits will take advantage of existing
Policy Avg. Word Avg. DB Expansion Factor Avg. Trace
Cost (Dev.) Cost (Dev.) for DB (Dev.) Word Cost (Dev.)
Word-always 1.00 (0.00) 8878.00 (0.00) 710.09 (1152.57) 1.00 (0.00)
Prepartition
Bounded

Table

7: Performance measurements for the base experiment for the five policies introduced in
Section 5.2.
e
Word
Access
Cost
Fraction of Databases
Bounded
Prepartition
Probabilistic

Figure

3: The average word access cost as the bound changes.
partitions of the word scale, if they exist, otherwise the word scale of the directory will be split.
Such splitting of the word scale occurred 118 times during our experiment, leading to an average
database access cost of 108.36 for this policy. At 8.84 times the minimum number of blocks that
must be read, this is the best average database access cost of the policies we measured. However,
58.41 is the worst average word access cost, and for the frequently occurring words of the trace
queries, the cost is even higher.
As a point of comparison for the two extremes of the DB-always and Word-always policies, we
measured the Probabilistic policy, parameterized so that the word and database scales would be
chosen with equal probability. If the distribution of data were uniform between the two scales, this
policy would on average split each scale the same number of times. As the table shows, however,
for our data this policy behaves very much like the DB-always policy. For both of these policies,
the skewed nature of the data (i.e., the vastly larger number of distinct values on the word scale)
makes many attempts to split on the database scale unsuccessful. In effect, the database scale
quickly becomes "saturated" and large numbers of splits must occur in the word scale. For this
parameter value, the Probabilistic policy gives poorer average database access cost and slightly
better average word access cost, when compared to the DB-always policy. The difference is more
pronounced for the average trace word access cost. Block-fill factor varies very little.

Figures

3 and 4 show how the three tunable policies, Bounded, Prepartition and Probabilistic,
behave as the tuning parameter varies. In order to graph these results on a common set of axes,
we express the parameter as a fraction of the total number of databases. Thus, for our study of
200 databases, an X-axis value of .05 in these figures represents parameter values of 10, 10, and
for the Bounded, Prepartition and Probabilistic policies, respectively.

Figure

5 reveals a hidden cost of the Bounded policy: an up-to-tenfold inflation in the size of
the grid-file directory for parameter values midway between the extremes. This occurs because
the Bounded policy forces splits between databases to occur as early as possible in the insertion
process, whereas the other two policies distribute them evenly. Under the Bounded policy, therefore,
e
Database
Access
Cost
Fraction of Databases
Bounded
Prepartition
Probabilistic

Figure

4: The average database access cost as the bound changes.500001500002500003500000 0.2 0.4 0.6 0.8 1
Directory
Size
Fraction of Databases
Bounded
Prepartition
Probabilistic

Figure

5: Directory size as a function of policy parameter.
Weighted
Average
Cost
Fraction of Databases
Bounded 100:1
Prepartition 100:1
Probabilistic 100:1

Figure

Weighted average cost for a word-to-database access ratio of 100:1.
relatively few splits between words occur early in the insertion process (because the regions being
split are typically only one database wide) but, once the bound has been reached, many splits
between words are required to subdivide the remaining portion of the grid file. Each of these
introduces a number of additional directory entries equal to the bound value. With the other
policies, the number of splits between words for each group of databases is fairly constant across
the width of the grid file, and the total number of splits between words (and hence the directory
size) is much smaller.
5.6 Weighted Average Costs

Table

7 presents no clear winner in terms of an overall policy choice, because the performance of
a policy can only be reduced to a single number once the ratio of accesses by word to accesses by
database has been determined. Only then can an appropriately weighted overall access cost be
calculated. For a word-to-database access ratio of 100:1, Figure 6 shows the weighted average cost
for each of the policies, across the entire parameter range. 5 The lowest point on this set of curves
represents the best choice of policy and parameter for this access ratio, and corresponds to the
Probabilistic policy with a parameter of about .025.
The best selections for various ratios are given in Tables 8 and 9, for the weighted average cost
and weighted trace average cost, respectively. When access by word predominates, Word-always
gives the best performance. When access by database is as common as access by word (or more
common), DB-always is the preferred policy. In between, the Probabilistic policy with an
appropriate parameter dominates the other choices.
5 The Word-always and DB-always policies are represented by the points for Probabilistic(0) and
Probabilistic(1), respectively.
Weighted Avg. Cost Block-Fill Factor
1:1 DB-always 167 .67
1000:1 Word-always 9878 .66

Table

8: The policy choices that minimize the weighted average cost, for different word-to-database
access ratios.
Weighted Trace Avg. Cost Block-Fill Factor
1:1 DB-always 213 .67
1000:1 Word-always 9878 .66

Table

9: The policy choices that minimize the weighted trace average cost, for different word-to-
database access ratios.
5.7 Bounded Access Costs
If the databases summarized by GlOSS grow gradually over time, the weighted access costs for
the grid file must grow as well. Using the recommended policies of Tables 8 and 9, this increasing
cost will be distributed between word and database access costs so as to minimize the weighted
average cost. The response time for a given query, however, depends only on the word access costs
for the terms it contains, and will increase without bound as the grid file grows. If such response
time growth is unacceptable, the Bounded and Prepartition policies can be used to put an upper
limit on word access cost, in which case query cost will depend only on the number of terms in the
query.
The upper limit on word access cost for these policies is determined by the parameter value.
With the Prepartition policy, the word access cost is exactly the parameter value: e.g., the cost
any word for Prepartition(10). The Bounded(10) policy gives the same
upper limit, but the average cost is lower (about 7) because for many words, the cost does not
reach the bound. However, Tables 6 and 7 in Section 5.5 show the penalty for the improved average
word access cost: about a fourfold increase in both directory size and database average access cost.
The corresponding tradeoffs for other values of the parameter can be deduced from Figures 3, 4
and 5 in Section 5.5.
5.8 Other Experiments
We did a number of other experiments to complete our evaluation of grid files as a storage method
for GlOSS summaries. In particular, since we must be able to maintain (update) the summaries
efficiently, we tested each of the policies under simulated updates. We also ran our experiments
with a smaller block size to see how that affected our results. Details can be found in [38]. The
results were generally acceptable and did not serve to differentiate the various policies, hence they
are not repeated here.
6 Using Partitioned Hashing for GlOSS
In this section we analyze partitioned (or multiattribute) hashing [22] as an alternative technique
for GlOSS to access its records efficiently both by word and by database. We first describe how
partitioned hashing handles the GlOSS summaries, and then we show experimental results on its
performance using the data of Section 5.
6.1 Partitioned-Hashing Basics
With partitioned hashing, the GlOSS records are stored in a hash table consisting of
buckets. Each bucket is identified by a string of b bits. b w of these b bits are associated with the
word attribute of the records, and the b remaining bits with the database attribute of
the records. Hash functions hw and h db map words and databases into strings of b w and b db bits,
respectively. A record (w; db; f ), with word w and database db, is stored in the bucket with address
hw (w)h db (db), formed by the juxtaposition of the hw (w) and h db (db) bit strings. To access all the
records with word w, we search all the buckets whose address starts with hw (w). To access all the
records with database db, we search all the buckets whose address ends with h db (db) 6 .
The hw hash function maps words into integers between 0 and 2 bw \Gamma 1. Given a word
a n . a 0 , hw does this mapping by first translating word w into integer i
[41], and then taking b(i w A mod 1)2 bw c, where A = 0:6180339887[22]. Similarly, the h db hash function
maps database numbers into integers between 0 and 2 b db \Gamma 1. Given a database number i db , h db
maps it into integer b(i db A mod 1)2 b db c. We initially assign one disk block per hash-table bucket.
If a bucket overflows, we assign more disk blocks to it.
Given a fixed value for b, we vary the values for b w and b db . By letting b w be greater than b db ,
we favor access to the GlOSS records by word, since there will be fewer buckets associated with
each word than with each database. In general we just consider configurations where b w is not
less than b db , since the number of words is much higher than the number of databases, and in our
model the records will be accessed more frequently by word than by database. In the following
section, we analyze experimentally the impact of the b w and b db parameters on the performance of
partitioned hashing for GlOSS.
6.2 Experimental Results
To analyze the performance of partitioned hashing for GlOSS, we ran experiments using the
2,999,676 records for the 200 databases of Section 5. For these experiments, we assumed that 512
records fit in one disk block, that each bucket should span one block on average, and that we want
each bucket to be 70% full on average. Therefore, we should have around
buckets, and we can dedicate approximately bits for the bucket addresses. (Section 7 shows
results for other values of b.)
To access all the records for a word w we must access all of the 2 b db buckets with address prefix
hw (w). Accessing each of these buckets involves accessing one or more disk blocks, depending on
whether the buckets have overflowed or not. Figure 7 shows the average word access cost as a
function of b w As expected, the number of blocks per word decreases as
b w increases, since the number of buckets per word decreases. Conversely, Figure 8 shows that the
average database access cost increases steeply as b w increases. In the extreme case when b
and b db = 0, we need to access every block in every bucket of the hash table, resulting in an
expansion factor for databases of around 773.28. 7 In contrast, when b
6 An improvement over this scheme is to apply the methodology of [12] and use Gray codes to achieve better
performance of partial-match queries.
7 Smarter bucket organizations can help alleviate this situation by sorting the records by database inside each
bucket, for example. However, all buckets of the hash table would still have to be examined to get the records for a
database.
Weighted Avg. Cost Block-Fill Factor

Table

10: The choices for b w and b db that minimize the weighted average cost, for different word-
to-database access ratios.
on average, around 11.24 times as many blocks for a database as we would need if the records were
clustered by database.
Partitioned hashing does not distribute records uniformly across the different buckets. For
example, all the records corresponding to database db belong in buckets with address suffix h db (db).
Surprisingly, this characteristic of partitioned hashing does not lead to a poor block-fill factor: the
average block-fill factor for and the different values of b w and b db is mostly higher than 0.6,
meaning that on average blocks were at least 60% full. These high values of block-fill factor are
partly due to the fact that only the last block of each bucket can be partially empty: all of the
other blocks of a bucket are completely full.
To measure the performance of partitioned hashing for access by word, we have so far computed
the average value of various parameters over all the words in the combined vocabulary of the 200
databases. Figure 7 also shows a curve using the words in the query trace of Section 5. The average
trace word access cost is very similar to the average word access cost. Two aspects of partitioned
hashing and our experiments explain this behavior. Firstly, the number of blocks read for a word
w does not depend on the number of records associated with w: we access all the 2 b db buckets with
prefix hw (w). Consequently, we access a similar number of blocks for each word. (For example,
when b the number of blocks we access per word ranges between 66 and 82.)
Secondly, there are only 2 bw possible different word access costs, because the hash function hw
maps the words into 2 bw different values. Each trace word w will contribute a "random sample"
of this set of 2 bw possible costs. Furthermore, the number of words in the query trace
(2828 word occurrences from a set of 1304 different words) is significant with respect to the number
of different access costs, for the values of b that we used in our experiments.
To determine the best values for b w and b db for an observed word-to-database access ratio, we
computed the weighted average cost for different access ratios, as in Section 5.6. Figure 9 shows
the results for a 100:1 word-to-database access ratio (i.e., when accesses by word are 100 times as
frequent as accesses by database). For this ratio, the best choice is b
weighted average cost of around 1844.51. Table 10 summarizes the results for the different access
ratios. Table 11 shows the corresponding results for the trace words. 8
7 Comparing Grid Files to Partitioned Hashing for Storing Sum-
maries
A comparison of Tables 8 and 9 with Tables 10 and 11 shows that with an ideal choice of parameters
for either structure, partitioned hashing and the grid file are competitive data structures for storing
GlOSS summaries. The grid file outperforms partitioned hashing only when word and database
are equally frequent. However, for a number of practical reasons, we believe that the grid
8 [1] and [23] study how to analytically derive the values of bw and bdb that would minimize the number of buckets
accessed for a given query distribution.
Average Word Access Cost 333
Average Trace Word Access Cost 222

Figure

7: Average word access costs as a function of b w
Average Database Access Cost 3

Figure

8: Average database access cost as a function of b w .
Weighted Trace Avg. Cost Block-Fill Factor

Table

11: The choices for b w and b db that minimize the weighted trace average cost, for different
word-to-database access ratios.
Weighted Average Cost (100:1) 333
Weighted Trace Average Cost

Figure

9: Weighted average cost for a word-to-database access ratio of 100:1, as a function of b w .
file is better suited to this application.
Firstly, to get optimum performance from partitioned hashing, it is critical to choose the total
number of buckets correctly. For instance, suppose that we overestimate the number of records of
the GlOSS summaries and set the number of bits that identify each bucket to instead of to
for the experiments of Section 6. Table 12 shows that, as expected, the average block-fill
factor drops to about half the values for (see Table 10), because there are twice as many
buckets now for the same number of records. The best average access costs also deteriorate: for
example, the weighted average cost for the 100:1 word-to-database access ratio grows to 2624 (from
for the Alternatively, if we underestimate the number of records of the GlOSS
summaries and set we obtain the results in Table 13. In this case, the average block-fill
factor is higher than in the case. However, all of the average access costs are significantly
higher. For example, for the 100:1 word-to-database access ratio, the weighted average cost for
These experiments show that it is crucial for the
performance of partitioned hashing to choose the right number of buckets in the hash table. Since
we expect databases to grow over time, even an initially optimal choice will degrade as database size
increases. By contrast, the grid file grows gracefully. Dynamic versions of multiattribute hashing
like the ones in [24] solve this problem at the expense of more complicated algorithms, resulting in
techniques that are closely related to the grid files.
Secondly, with partitioned hashing, the tradeoff between word and database access cost is fixed
for all time once a division of hash-value bits has been made. The only way to correct for an error
is to rebuild the hash table. By contrast, the value of the probabilistic splitting parameter for the
grid file can be dynamically tuned. Although changing the parameter may not be able to correct
for unfortunate splits in the existing grid file, at least future splitting decisions will be improved.
Finally, partitioned hashing treats all words the same, regardless of how many or how few
databases they occur in, and likewise treats all databases the same, regardless of the number of
words they contain. By contrast, the cost of reading a row or column of the grid file tends to be
proportional to the number of records it contains.
Weighted Avg. Cost Block-Fill Factor

Table

12: The choices for b w and b db that minimize the weighted average cost, for different word-
to-database access ratios and for
Weighted Avg. Cost Block-Fill Factor
100:1 9 3 2623.05 0.72

Table

13: The choices for b w and b db that minimize the weighted average cost, for different word-
to-database access ratios and for
8 Related Work
Many approaches to solving the text database discovery problem have been proposed [27, 33].
These fall into two groups, distributed browsing systems (e.g., [4], [25]) and query systems (e.g.,
[21], [14], [10]). In distributed browsing systems, users follow pre-defined links between data items.
While a wealth of information is accessible this way, links must be maintained by hand, and are
therefore frequently out of date (or non-existent). Finding information can be frustrating to say
the least.
To address this problem, an increasing number of systems allow users to query a collection of
"meta-information" about available databases (e.g., [36], [2], and [28], or the Content Router [35,
11]). The meta-information typically provides some sort of summary of the contents of each
database; thus, these systems fit our generic concept of a broker. Of course, different systems use
different representations of this summary information and their implementations vary substantially.
To scale with the growing number of available databases, some systems index only document
titles or, more generally, just a small fraction of each document (e.g., the World-Wide Web Worm 9 ,
Veronica [14]). This approach sacrifices important information about the contents of each database.
Other systems keep succinct, sometimes human-generated, summaries of the contents of each
database (e.g., the ALIWEB system 10 , or WAIS [21]). Human-generated summaries are often out
of date, since as the database changes, the summaries generally do not. English text summaries
as in WAIS may not capture the information the user wants. GlOSS attacks both these problems
by using all words in the database as a summary and by automatically updating the summary as
the database changes. A GlOSS-based meta-information query facility has been implemented for
servers. 11
System architectures range from centralized servers such as Lycos 12 and Yahoo 13 , to collections
of brokers or mediators. In Indie (shorthand for "Distributed Indexing") [10, 9] and Harvest [5],
brokers each know about some subset of the data sources, with a special broker that keeps informa-
9 The World-Wide Web Worm is accessible at http://www.cs.colorado.edu/home/mcbryan/WWWW.html.
is accessible at http://web.nexor.co.uk/aliweb/doc/aliweb.html.
11 GlOSS is accessible at http://gloss.stanford.edu.
12 Lycos is accessible at http://lycos.cs.cmu.edu.
13 Yahoo is accessible at http://yahoo.stanford.edu.
tion about all other brokers. [32] and WHOIS++ [40] allow brokers (index-servers in WHOIS++)
to exchange information about sources they index, and to forward queries they receive to other
knowledgeable brokers. [13] similarly allows sites to forward queries to likely sources (based, in
this case, on what information has been received from that source in the past). Recently, [7] has
applied inference networks (from traditional information retrieval) to the text database discovery
problem. Their approach summarizes databases using document frequency information for each
term (the same type of information that GlOSS keeps about the databases), together with the "in-
verse collection frequency" of the different terms. An inference network then uses this information
to rank the databases for a given query.
While there have been many proposals for how to summarize database contents and how to
use the summaries to answer queries, there have been very few performance studies in this area.
[32] includes a simulation study of the effectiveness of having brokers exchange content summaries,
but is not concerned with what these content summaries are, nor with the costs of storing and
exchanging them. [7] studies the inference network approach experimentally. Likewise, [17, 18]
examine the effectiveness and storage efficiency of GlOSS without worrying about costs of access
and update.
The representation of summary information for distributed text databases is clearly important
for a broad range of query systems. Our paper goes beyond existing works in addressing the storage
of this information, and in studying the performance of accesses and updates to this information.
9 Conclusion
The investigation reported in this paper represents an important step toward making GlOSS a
useful tool for large scale information discovery. We showed that GlOSS can, in fact, effectively
distinguish among text databases in a large system with hundreds of databases. We further identified
partitioned hashing and grid files as useful data structures for storing the summary information
that GlOSS requires. We showed that partitioned hashing offers the best average case performance
for a wide range of workloads, but that performance can degrade dramatically as the amount of
data stored grows beyond initial estimates. The grid file can be tuned to perform well, and does
not require any initial assumption about the ultimate size of the summary information.
We examined how the characteristics of the GlOSS summaries make the policy for splitting
blocks of the grid file a critical factor in determining the ultimate row and column access costs,
and evaluated several specific policies using databases containing U.S. Patent Office data. Our
investigation showed that if the expected ratio of row accesses to column accesses is very high
(greater than about 1000:1 in our experiment), the best policy is to always split between words.
Some existing distributed information retrieval services exceed this high ratio. If the ratio is very
low or if updates exceed queries, the best policy is to split between databases whenever possible.
Between these extremes, a policy of splitting between databases with a given probability can be used
to achieve the desired balance between row and column access costs. For a given probability (and
expected number of database splits, ds), this policy performs better than policies that prepartition
the database scale ds times, or that always divide on the database scale up to ds times. If it is
important to have a firm bound on query costs, policies that prepartition or divide the database
scale a fixed number of times can be used.
More work is needed to explore the utility of the GlOSS summaries as a representation of summary
information for brokers. Their effectiveness should be studied in a more realistic environment
with real databases and matching queries, where the queries involve disjunction as well as conjunc-
tion. There is more work to be done on the storage of these summaries as well. An unfortunate
aspect of the grid files is their need for a relatively large directory. Techniques have been reported
for controlling directory size [3]; we must examine whether those techniques are applicable to the
highly-skewed grid files generated by the GlOSS summaries. Compression techniques [42] would
have a significant impact on the performance figures reported here. Finally, building an operational
GlOSS server for a large number of real databases is the only way to truly determine the right
ratio between word and database access costs.
On a broader front, many other issues remain to be studied. The vastly expanding number
and scope of online information sources make it clear that a centralized solution to the database
discovery problem will never be satisfactory, showing the need to further explore architectures
based on hierarchies [16] or networks of brokers.



--R

optimal partial-match retrieval when fields are independently specified
Information Brokers: Sharing knowledge in a heterogeneous distributed system.
A new algorithm for computing joins with grid files.

Harvest: A scalable
Fast incremental indexing for full-text information retrieval
Searching distributed collections with inference networks.
Optimizations for dynamic inverted index maintenance.
Distributed indexing: a scalable mechanism for distributed information retrieval.
Distributed indexing of autonomous Internet services.
Content routing in a network of WAIS servers.
Multiattribute hashing using Gray codes.
An information retrieval system for network resources.
About the Veronica service
A general solution of the n-dimensional b-tree problem
Generalizing GlOSS to vector-space databases and broker hierarchies
The effectiveness of GlOSS for the text-database discovery problem
Precision and recall of GlOSS estimators for database discovery.
A dynamic index structure for spatial searching.
Implementation of the grid file: design concepts and experience.
An information system for corporate users: Wide Area Information Servers.
The art of computer programming: Volume
optimal partial-match retrieval

The Prospero File System: A global file system based on the Virtual System model.
The grid file: An adaptable
Internet resource discovery services.
Distributed active catalogs and meta-data caching in descriptive name services
A class of data structures for associative searching.
Sparse matrix technology.
Introduction to modern information retrieval.
A scalable
A comparison of Internet resource discovery approaches.

A content routing system for distributed information servers.
Querying a network of autonomous databases.
Incremental updates of inverted lists for text document retrieval.
Data structures for efficient broker implementation.
Principles of database and knowledge-base systems
Architecture of the WHOIS
File organization for database design.
An efficient indexing technique for full-text database systems
--TR
Implementation of the grid file: design concepts and experience
Multiattribute hashing using Gray codes
Principles of database and knowledge-base systems, Vol. I
File organization for database design
Optimization for dynamic inverted index maintenance
Distributed indexing
Content routing for distributed information servers
The effectiveness of GIOSS for the text database discovery problem
Incremental updates of inverted lists for text document retrieval
Searching distributed collections with inference networks
A general solution of the n-dimensional B-tree problem
Performance issues in distributed shared-nothing information-retrieval systems
The art of computer programming, volume 2 (3rd ed.)
The Grid File
Optimal partial-match retrieval when fields are independently specified
Precision and recall of <italic>GIOSS</italic> estimators for database discovery
Introduction to Modern Information Retrieval
A class of data structures for associative searching
R-trees
Internet Resource Discovery Services
A New Algorithm for Computing Joins with Grid Files
The R+-Tree
An Efficient Indexing Technique for Full Text Databases
Fast Incremental Indexing for Full-Text Information Retrieval
Generalizing GlOSS to Vector-Space Databases and Broker Hierarchies

--CTR
Ray R. Larson, Distributed resource discovery: using z39.50 to build cross-domain information servers, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.52-53, January 2001, Roanoke, Virginia, United States
Athman Bouguettaya , Boualem Benatallah , Mourad Ouzzani , Lily Hendra, WebFindIt: An Architecture and System for Querying Web Databases, IEEE Internet Computing, v.3 n.4, p.30-41, July 1999
Jian Xu , Yinyan Cao , Ee-Peng Lim , Wee-Keong Ng, Database selection techniques for routing bibliographic queries, Proceedings of the third ACM conference on Digital libraries, p.264-274, June 23-26, 1998, Pittsburgh, Pennsylvania, United States
M. S. Hosain , M. A. H. Newton , M. M. Rahman, Dynamic adaptation of multi-key index for distributed database system, Proceedings of the 9th WSEAS International Conference on Computers, p.1-6, July 14-16, 2005, Athens, Greece
Luis Gravano , Hector Garcia-Molina, Generalizing GlOSS to Vector-Space Databases and Broker Hierarchies, Proceedings of the 21th International Conference on Very Large Data Bases, p.78-89, September 11-15, 1995
James C. French , Allison L. Powell, Metrics for evaluating database selection techniques, World Wide Web, v.3 n.3, p.153-163, 2000
Athman Bouguettaya , Boualem Benatallah , Brahim Medjahed , Mourad Ouzzani , Lily Hendra, Adaptive web-based database communities, Information modeling for internet applications, Idea Group Publishing, Hershey, PA,
M. Ouzzani , B. Benatallah , A. Bouguettaya, Ontological Approach for Information Discovery in Internet Databases, Distributed and Parallel Databases, v.8 n.3, p.367-392, July 2000
Luis Gravano , Hctor Garca-Molina , Anthony Tomasic,
GlOSS
Athman Bouguettaya , Boualem Benatallah , Lily Hendra , Mourad Ouzzani , James Beard, Supporting Dynamic Interactions among Web-Based Information Sources, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.779-801, September 2000
Diego Puppin , Fabrizio Silvestri , Domenico Laforenza, Query-driven document partitioning and collection selection, Proceedings of the 1st international conference on Scalable information systems, p.34-es, May 30-June 01, 2006, Hong Kong
Allison L. Powell , James C. French, Comparing the performance of collection selection algorithms, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.412-456, October
broker architecture;distributed information;GlOSS;partitioned hashing;grid files;broker performance