The impact of database selection on distributed searching

ABSTRACT

The proliferation of online information resources increases the importance of effective and efficient distributed searching. Distributed searching is cast in three parts — database selection, query processing, and results merging. In this paper we examine the effect of database selection on retrieval performance. We look at retrieval performance in three different distributed retrieval testbeds and distill some general results. First we find that good database selection can result in better retrieval effectiveness than can be achieved in a centralized database. Second we find that good performance can be achieved when only a few sites are selected and that the performance generally increases as more sites are selected. Finally we find that when database selection is employed, it is not necessary to maintain collection wide information (CWI), e.g. global idf. Local information can be used to achieve superior performance. This means that distributed systems can be engineered with more autonomy and less cooperation. This work suggests that improvements in database selection can lead to broader improvements in retrieval performance, even in centralized (i.e. single database) systems. Given a centralized database and a good selection mechanism, retrieval performance can be improved by decomposing that database conceptually and employing a selection step.

REFERENCES

• 1: J. Allan, J. P. Callan, W. B. Croft, L. Ballesteros, D. Byrd, R. Swan, and J. Xu. INQUERY does battle with TREC-6. In The Sixth Text REtrieval Conference (TREC-6).
• 2: N. J. Belkin , P. Kantor , E. A. Fox , J. A. Shaw, Combining the evidence of multiple query representations for information retrieval, Information Processing and Management: an International Journal, v.31 n.3, p.431-448, May-June 1995
• 3: J. Callan, A. L. Powell, J. C. French, and M. Connell. The Effects of Query-Based Sampling on Automatic Database Selection Algorithms. Technical Report CMU-LTI-00- 162, Language Technologies Institute, School of Computer Science, Carnegie Mellon University, 2000.
• 4: 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]
• 5: N. Craswell, D. Hawking, and P. Thistlewaite. Merging Results from Isolated Search Engines. In Proc. of the Tenth Australasian Database Conf., pages 189-200, 1999.
• 6: E. A. Fox, M. P. Koushik, J. Shaw, R. Modlin, and D. Rat. Combining Evidence from Multiple Searches. In The First Text Retrieval Conference (TREC-1), pages 319-328, November 1992.
• 7: James C. French , Allison L. Powell , Jamie Callan , Charles L. Viles , Travis Emmitt , Kevin J. Prey , Yun Mou, Comparing the performance of database selection algorithms, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.238-245, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312684]
• 8: James C. French , Allison L. Powell , Charles L. Viles , Travis Emmitt , Kevin J. Prey, Evaluating database selection techniques: a testbed and experiment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.121-129, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290976]
• 9: J. C. French and C. L. Viles. Ensuring Retrieval Effectiveness in Distributed Digital Libraries. Journal of Visual Communication and Image Representation, 7(1):61 - 73, 1996.
• 10: Norbert Fuhr, A decision-theoretic approach to database selection in networked IR, ACM Transactions on Information Systems (TOIS), v.17 n.3, p.229-249, July 1999 [doi>10.1145/314516.314517]
• 11: 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
• 12: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 13: 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
• 14: D. Harman. Overview of the Fourth Text Retrieval Conference (TREC-4). In Proceedings of the Fourth Text Retrieval Conference (TREC-4), 1996.
• 15: David Hawking , Paul Thistlewaite, Methods for information server selection, ACM Transactions on Information Systems (TOIS), v.17 n.1, p.40-76, Jan. 1999 [doi>10.1145/297117.297123]
• 16: David Hull, Using statistical testing in the evaluation of retrieval experiments, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.329-338, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160758]
• 17: A. Moffat and J. Zobel. Information Retrieval Systems for Large Document Collections. In Proceedings of the Third Text Retrieval Conference (TREC-3), pages 85-94, 1995.
• 18: R. L. Ott. An Introduction to Statistical Methods and Data Analysis. Duxbury Press, 4th. edition, 1993.
• 19: Charles L. Viles , James C. French, Dissemination of collection wide information in a distributed information retrieval system, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.12-20, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215327]
• 20: Ellen M. Voorhees , Narendra K. Gupta , Ben Johnson-Laird, Learning collection fusion strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-179, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215357]
• 21: E. Voorhees, N. K. Gupta, and B. Johnson-Laird. The Collection Fusion Problem. In Proceedings of the Third Text Retrieval Conference (TREC-3), pages 95-104, 1995.
• 22: Jinxi Xu , Jamie Callan, Effective retrieval with distributed collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.112-120, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290974]
• 23: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 24: Ronald R. Yager , Alexander Rybalov, On the fusion of documents from multiple collection information retrieval systems, Journal of the American Society for Information Science, v.49 n.13, p.1177-1184, Nov. 1998 [doi>10.1002/(SICI)1097-4571(1998)49:13<1177::AID-ASI5>3.0.CO;2-E]
• 25: Budi Yuwono , Dik Lun Lee, Server Ranking for Distributed Text Retrieval Systems on the Internet, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.41-50, April 01-04, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Experimentation, Performance, Theory