A utility theoretic approach to determining optimal wait times in distributed information retrieval

ABSTRACT

Distributed IR systems query a large number of IR servers, merge the retrieved results and display them to users. Since different servers handle collections of different sizes, have different processing and bandwidth capacities, there can be considerable heterogeneity in their response times. The broker in the distributed IR system thus has to make decisions regarding terminating searches based on perceived value of waiting -- retrieving more documents -- and the costs imposed on users by waiting for more responses. In this paper, we apply utility theory to formulate the broker's decision problem. The problem is a stochastic nonlinear program. We use Monte Carlo simulations to demonstrate how the optimal wait time may be determined in the context of a comparison shopping engine that queries multiple store websites for price and product information. We use data gathered from 30 stores for a set of 60 books. Our research demonstrates how a broker can leverage information about past retrievals regarding distributions of server response time and relevance scores to optimize its performance. Our main contribution is the formulation of the decision model for optimal wait time and proposal of a solution method. Our results suggest that the optimal wait time is highly sensitive to the manner in which users value from a set of retrieved results differs from the sum of user value from each result evaluated independently. We also find that the optimal wait time increases with the size of the distributed collections, but only if user utility from a set of results is nearly equal to the sum of utilities from each result.

REFERENCES

• 1: Jay April , Fred Glover , James Kelly , Manuel Laguna, Optimization and system selection: simulation/optimization using "real-world" applications, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 2: Javed A. Aslam , Mark Montague, Models for metasearch, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.276-284, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384007]
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 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: Robert B. Doorenbos , Oren Etzioni , Daniel S. Weld, A scalable comparison-shopping agent for the World-Wide Web, Proceedings of the first international conference on Autonomous agents, p.39-48, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267666]
• 6: 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]
• 7: Fred Glover , James P. Kelly , Manuel Laguna, New advances for wedding optimization and simulation, Proceedings of the 31st conference on Winter simulation: Simulation---a bridge to the future, p.255-260, December 05-08, 1999, Phoenix, Arizona, United States [doi>10.1145/324138.324223]
• 8: 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
• 9: Johnson, Eric J. and J. W. Payne (1985), "Effort and accuracy in choice", Management Science, 31, pp. 394--414.
• 10: Kehoe, Colleen, J. Pitkow, K. Sutton, G. Agarwal and J. D. Rogers (1999), "Results of the Graphics, Visualization and Usability Tenth World Wide Web User Survey," Working Paper.
• 11: Larcker, D. F. and V. P. Lessig, "Perceived Usefulness of Information: A Psychometric Examination," Decision Sciences, 11, 1, 1980.
• 12: Hugo Liu , Henry Lieberman , Ted Selker, GOOSE: A Goal-Oriented Search Engine with Commonsense, Proceedings of the Second International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems, p.253-263, May 29-31, 2002
• 13: McFadden, D. (1980), "Econometric Models of Probabilistic Choice Among Products", Journal of Business.
• 14: Rudy K. Moenaert , William E. Souder, Context and antecedents of information utility at the R&D/marketing interface, Management Science, v.42 n.11, p.1592-1610, Nov. 1996 [doi>10.1287/mnsc.42.11.1592]
• 15: Moffat and J. Zobel. Information retrieval systems for large document collections. In D. K. Harman, editor, The Third Text REtrieval Conference (TREC3) , Gaithersburg, MD, 1995.
• 16: Alan L. Montgomery , Kartik Hosanagar , Ramayya Krishnan , Karen B. Clay, Designing a Better Shopbot, Management Science, v.50 n.2, p.189-206, February 2004 [doi>10.1287/mnsc.1030.0151]
• 17: B. J. Rhodes , P. Maes, Just-in-time information retrieval agents, IBM Systems Journal, v.39 n.3-4, p.685-704, July 2000
• 18: Shugan, Steven M. (1980), "The Cost of Thinking", Journal of Consumer Research, Vol. 7, September, pp. 99--111.
• 19: Smith, Michael D., and Erik Brynjolfsson. "Customer Decision Making at an Internet Shopbot: Brand Still Matters," The Journal of Industrial Economics, 49(4) 541--558, 2001.
• 20: Luo Si , Jamie Callan, Using sampled data and regression to merge search engine results, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564382]
• 21: 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]
• 22: O. Madani, Efficient information gathering on the Internet, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.234, October 14-16, 1996

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.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design, Economics, Human Factors

Keywords:
distributed IR, optimal wait time, query termination, utility theory