A decision-theoretic approach to database selection in networked IR

ABSTRACT

In networked IR, a client submits a query to a broker, which is in contact with a large number of databases. In order to yield a maximum number of documents at minimum cost, the broker has to make estimates about the retrieval cost of each database, and then decide for each database whether or not to use it for the current query, and if, how many documents to retrieve from it. For this purpose, we develop a general decision-theoretic model and discuss different cost structures. Besides cost for retrieving relevant versus nonrelevant documents, we consider the following parameters for each database: expected retrieval quality, expected number of relevant documents in the database and cost factors for query processing and document delivery. For computing the overall optimum, a divide-and-conquer algorithm is given. If there are several brokers knowing different databases, a preselection of brokers can only be performed heuristically, but the computation of the optimum can be done similarily to the single-broker case. In addition, we derive a formula which estimates the number of relevant documents in a database based on dictionary information.

REFERENCES

• 1: Daniel E. Atkins , William P. Birmingham , Edmund H. Durfee , Eric J. Glover , Tracy Mullen , Elke A. Rundensteiner , Elliot Soloway , José M. Vidal , Raven Wallace , Michael P. Wellman*Authors are listed alphabeticall, Toward Inquiry-Based Education Through Interacting Software Agents, Computer, v.29 n.5, p.69-76, May 1996 [doi>10.1109/2.494084]
• 2: Christoph Baumgarten, A probabilistic model for distributed information retrieval, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.258-266, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 3: BOOKSTEIN, A. 1983. Outline of a general probabilistic retrieval model. J. Doc. 39, 2, 63-72.
• 4: C. Mic Bowman , Peter B. Danzig , Darren R. Hardy , Udi Manber , Michael F. Schwartz, The Harvest information discovery and access system, Computer Networks and ISDN Systems, v.28 n.1-2, p.119-125, Dec. 1995 [doi>10.1016/0169-7552(95)00098-5]
• 5: 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]
• 6: DANZIG, P., LI, S. -H., AND OBRACZKA, K. 1992. Distributed indexing of autonomous internet services. Comput. Syst. 5, 4, 433-459.
• 7: Markus Dreger , Norbert Fuhr , Kai Großjohann , Stefan Lohrum, Provider Selection - Design and Implementation of the Medoc Broker, Digital Libraries in Computer Science: The MeDoc Approach, p.67-78, January 1998
• 8: Albert Endres , Norbert Fuhr, Students access books and journals through MeDoc, Communications of the ACM, v.41 n.4, p.76-77, April 1998 [doi>10.1145/273035.273058]
• 9: 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]
• 10: Norbert Fuhr, Optimum polynomial retrieval functions based on the probability ranking principle, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.183-204, July 1989 [doi>10.1145/65943.65944]
• 11: Norbert Fuhr, Object-oriented and database concepts for the design of networked information retrieval systems, Proceedings of the fifth international conference on Information and knowledge management, p.164-172, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238480]
• 12: G VERT, N. 1997. Database selection in networked information retrieval systems. Diploma thesis. Department of Computer Science, University of Dortmund, Dortmund, Germany.
• 13: 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
• 14: Luis Gravano , Héctor García-Molina , Anthony Tomasic, The effectiveness of GIOSS for the text database discovery problem, ACM SIGMOD Record, v.23 n.2, p.126-137, June 1994
• 15: Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
• 16: Brewster Kahle , Harry Morris , Jonathan Goldman , Thomas Erickson , John Curran, Interfaces for distributed systems of information servers, Journal of the American Society for Information Science, v.44 n.8, p.453-467, Sept. 1993 [doi>10.1002/(SICI)1097-4571(199309)44:8<453::AID-ASI4>3.0.CO;2-E]
• 17: ROBERTSON, S. E. 1977. The probability ranking principle in IR. J. Doc. 33, 4, 294-304.
• 18: Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
• 19: VAN RIJSBERGEN, C.J. 1986. A non-classical logic for information retrieval. Comput. J. 29, 6, 481-485.
• 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: S. K. M. Wong , Y. Y. Yao, On modeling information retrieval with probabilistic inference, ACM Transactions on Information Systems (TOIS), v.13 n.1, p.38-68, Jan. 1995 [doi>10.1145/195705.195713]
• 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]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

General Terms:
Theory

Keywords:
networked retrieval, probabilistic retrieval, probability ranking principle, resource discovery