Evaluating different methods of estimating retrieval quality for resource selection

ABSTRACT

In a federated digital library system, it is too expensive to query every accessible library. Resource selection is the task to decide to which libraries a query should be routed. Most existing resource selection algorithms compute a library ranking in a heuristic way. In contrast, the decision-theoretic framework (DTF) follows a different approach on a better theoretic foundation: It computes a selection which minimises the overall costs (e.g. retrieval quality, time, money) of the distributed retrieval. For estimating retrieval quality the recall-precision function is proposed. In this paper, we introduce two new methods: The first one computes the empirical distribution of the probabilities of relevance from a small library sample, and assumes it to be representative for the whole library. The second method assumes that the indexing weights follow a normal distribution, leading to a normal distribution for the document scores. Furthermore, we present the first evaluation of DTF by comparing this theoretical approach with the heuristical state-of-the-art system CORI; here we find that DTF outperforms CORI in most cases.

REFERENCES

• 1: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 2: J. Callan, W. Croft, and S. Harding. The INQUERY retrieval system. In Proceedings of DEXA-92, 3rd International Conference on Database and Expert Systems Applications, pages 78--83, Berlin et al., 1992. Springer.
• 3: 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]
• 4: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 5: 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]
• 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: 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
• 8: D. K. Harman, Second Text Retrieval Conference (TRE C-2) Proceedings, DIANE Publishing Company, 1995
• 9: R. Manmatha , T. Rath , F. Feng, Modeling score distributions for combining the outputs of search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-275, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384005]
• 10: H. Nottelmann and N. Fuhr. From uncertain inference to probability of relevance for advanced IR applications. In F. Sebastiani, editor, 25th European Conferenve on Information Retrieval Research (ECIR 2003), pages 235--250. Springer, 2003.
• 11: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, editors. Nested Relations and Complex Objects in Databases. Cambridge University Press, 1992.
• 12: S. E. Robertson, S. Walker, M. Hancock-Beaulieu, A. Gull, and M. Lau. Okapi at TREC. In Text REtrieval Conference, pages 21--30, 1992.
• 13: Luo Si , Jamie Callan, Relevant document distribution estimation method for resource selection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860490]
• 14: L. Si, R. Jin, J. Callan, and P. Ogilvie. Proceedings of the 11th international conference on information and knowledge management. In D. Grossman, editor, Proceedings of the 11th International Conference on Information and Knowledge Management, New York, 2002. ACM.
• 15: C. J. van Rijsbergen. A non-classical logic for information retrieval. The Computer Journal, 29(6):481--485, 1986.
• 16: 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]
• 17: S. Wu and F. Crestani. Multi-objective resource selection in distributed information retrieval. In Proceedings of The 9th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU), 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Retrieval models

General Terms:
Experimentation, Theory

Keywords:
decision-theoretic framework, evaluation, formal models, normal distribution, resource selection