Stanford InfoLab Publication Server

Data Structures for Efficient Broker Implementation

Tomasic, A. and Gravano, L. and Lue, C. and Schwarz, P. and Haas, L. (1996) Data Structures for Efficient Broker Implementation. Technical Report. Stanford InfoLab. (Publication Note: Technical report, IBM Almaden Research Center, June 1995; also in TOIS'96.)




With the profusion of text databases on the Internet, it is becoming increasingly hard to find the 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 effcient access. We offer evidence that one broker, GlOSS, can be effective at locating databases of interest even in a system of hundreds of databases, and examine the performance of accessing the GlOSS summaries 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 wand 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; in particular, 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.

Item Type:Techreport (Technical Report)
Subjects:Computer Science
Related URLs:Project Homepage
ID Code:141
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:09 Dec 2008 09:41

Download statistics

Repository Staff Only: item control page