Data structures for efficient broker implementation

ABSTRACT

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.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Optimal partial-match retrieval when fields are independently specified, ACM Transactions on Database Systems (TODS), v.4 n.2, p.168-179, June 1979 [doi>10.1145/320071.320074]
• 2: BARBARA, D. AND CLIFTON, C. 1992. Information brokers: Sharing knowledge in a heterogeneous distributed system. Tech. Rep. MITL-TR-31-92, Matsushita Information Technology Laboratory, Princeton, N.J. October.
• 3: Ludger Becker , Klaus Hinrichs , Ulrich Finke, A New Algorithm for Computing Joins with Grid Files, Proceedings of the Ninth International Conference on Data Engineering, p.190-197, April 19-23, 1993
• 4: BERNERS-LEE, T., CAILLIAU, R., GROFF, J.-F., AND POLLERMANN, B. 1992. World-Wide Web: The information universe. Elect. Network. Res. Appl. Policy 1, 2.
• 5: BOWMAN, C. M., DANZIG, P. B., HARDY, D. R., MANBER, U., AND SCHWARTZ, M.F. 1994. Harvest: A scalable, customizable discovery and access system. Tech. Rep. CU-CS-732-94, Dept. of Computer Science, Univ. of Colorado, Boulder, Colo.
• 6: Eric W. Brown , James P. Callan , W. Bruce Croft, Fast Incremental Indexing for Full-Text Information Retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, p.192-202, September 12-15, 1994
• 7: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 8: D. Cutting , J. Pedersen, Optimization for dynamic inverted index maintenance, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.405-411, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98245]
• 9: Peter B. Danzig , Jongsuk Ahn , John Noll , Katia Obraczka, Distributed indexing: a scalable mechanism for distributed information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.220-229, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122883]
• 10: DANZIG, P.B., LI, S.-H., AND OBRACZKA, K. 1992. Distributed indexing of autonomous Internet services. Comput. Sys. 5, 4.
• 11: DUDA, A. AND SHELDON, M.A. 1994. Content routing in a network of WAIS servers. In the 14th IEEE International Conference on Distributed Computing Systems. IEEE, New York.
• 12: Christos Faloutsos, Multiattribute hashing using Gray codes, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.227-238, May 28-30, 1986, Washington, D.C., United States
• 13: FLATER, D. W. AND YESHA, Y. 1993. An information retrieval system for network resources. In Proceedings of the International Workshop on Next Generation Information Technologies and Systems.
• 14: Michael Freeston, A general solution of the n-dimensional B-tree problem, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.80-91, May 22-25, 1995, San Jose, California, United States
• 15: 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
• 16: Luis Gravano , Héctor García-Molina , Anthony Tomasic, The effectiveness of GIOSS for the text database discovery problem, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.126-137, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: Luis Gravano , Héctor García-Molina , Anthony Tomasic, Precision and recall of GIOSS estimators for database discovery, Proceedings of the third international conference on on Parallel and distributed information systems, p.103-107, October 1994, Autin, Texas, United States
• 18: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 19: HARMAN, D. K., Ed. 1995a. Overview of the 3rd Text Retrieval Conference (TREC-3). NIST Special Pub. 500-225, Coden: NSPUE2. U.S. Dept. of Commerce, Technology Administration, National Institute of Standards and Technology (NIST), Gaithersburg, Md.
• 20: HARMAN, D., Ed. 1995b. Proceedings of the 3rd Text Retrieval Conference (TREC-3). National Institute of Standards and Technology, Gaithersburg, Md. Available as Special Pub. 500 -225.
• 21: HARMAN, D., E. 1996. Proceedings of the 4th Text Retrieval Conference (TREC-4). National Institute of Standards and Technology, Gaithersburg, Md.
• 22: Klaus Hinrichs, Implementation of the grid file: design concepts and experience, BIT, v.25 n.4, p.569-592, 1985 [doi>10.1007/BF01936137]
• 23: KAHLE, B. AND MEDLAR, A. 1991. An information system for corporate users: Wide Area Information Servers. Tech. Rep. TMC199, Thinking Machines Corp., Boston, Mass.
• 24: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 25: LLOYD, g.W. 1980. Optimal partial-match retrieval. BIT 20, 406-413.
• 26: LLOYD, J. W. AND RAMAMOHANARAO, K. 1982. Partial-match retrieval for dynamic files. BIT 22, 150-168.
• 27: NEUMAN, B.C. 1992. The Prospero file system: A global file system based on the Virtual System model. Comput. Syst. 5, 4.
• 28: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 29: Katia Obraczka , Peter B. Danzig , Shih-Hao Li, Internet Resource Discovery Services, Computer, v.26 n.9, p.8-22, September 1993 [doi>10.1109/2.231277]
• 30: ORDILLE, J. J. AND MILLER, B.P. 1992. Distributed active catalogs and meta-data caching in descriptive name services. Tech. Rep. 1118, Univ. of Wisconsin, Madison, Wisc.
• 31: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 32: PISSANETZKY, S. 1984. Sparse Matrix Technology. Academic Press, New York.
• 33: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 34: SCHWARTZ, M.F. 1990. A scalable, non-hierarchical resource discovery mechanism based on probabilistic protocols. Tech. Rep. Cu-CS-474-90, Dept. of Computer Science, Univ. of Colorado, Boulder, Colo.
• 35: SCHWARTZ, M. F., EMTAGE, A., KAHLE, B., AND NEUMAN, C.B. 1992. A comparison of Internet resource discovery approaches. Comput. Syst. 5, 4.
• 36: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 37: Mark A. Sheldon , Andrzej Duda , Ron Weiss , James W. O'Toole, Jr. , David K. Gifford, Content routing for distributed information servers, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.109-122, May 1994, Cambridge, United Kingdom
• 38: SIMPSON, P. AND ALONSO, R. 1989. Querying a network of autonomous databases. Tech. Rep. CS-TR-202-89, Dept. of Computer Science, Princeton Univ., Princeton, N.J.
• 39: Anthony Tomasic , Hector Garcia-Molina, Performance issues in distributed shared-nothing information-retrieval systems, Information Processing and Management: an International Journal, v.32 n.6, p.647-665, Nov. 1996 [doi>10.1016/S0306-4573(96)00019-2]
• 40: Anthony Tomasic , Héctor García-Molina , Kurt Shoens, Incremental updates of inverted lists for text document retrieval, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States
• 41: TOMASIC, A., GRAVANO, L., LUE, C., SCHWARZ, P., AND HAAS, L. 1995. Data structures for efficient broker implementation. Tech. Rep., IBM Almaden Research Center, San Jose, Calif. Also available as ftp://db.stanford.edu/pub/gravano/1995/ibm_rj.ps.
• 42: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 43: VOORHEES, E.M. 1996. Siemens TREC-4 report: Further experiments with database merging. In Proceedings of the 4th Text Retrieval Conference (TREC-4). NIST, Gaithersburg, Md.
• 44: VOORHEES, E. M., GUPTA, N. K., AND JOHNSON-LAIRD, B. 1995. The collection fusion problem. In Proceedings of the 3rd Text Retrieval Conference (TREC-3). NIST, Gaithersburg, Md.
• 45: WEIDER, C. AND FALTSTROM, P. 1994. The WHOIS++ directory service. ConneXions 8, 12 (Dec.).
• 46: G. Weiderhold, File organization for database design, McGraw-Hill, Inc., New York, NY, 1987
• 47: Justin Zobel , Alistair Moffat , Ron Sacks-Davis, An Efficient Indexing Technique for Full Text Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.352-362, August 23-27, 1992

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.4 Systems and Software
          Subjects: Information networks

General Terms:
Algorithms, Measurement, Performance

Keywords:
GlOSS, broker architecture, broker performance, distributed information, grid files, partitioned hashing