Integral based source selection for uncooperative distributed information retrieval environments

ABSTRACT

In this paper, a new source selection algorithm for uncooperative distributed information retrieval environments is presented. The algorithm functions by modeling each information source as an integral, using the relevance score and the intra-collection position of its sampled documents in reference to a centralized sample index and selects the collections that cover the largest area in the rank-relevance space. Based on the above novel metric, the algorithm explicitly focuses on addressing the two goals of source selection; high recall which is important for source recommendation applications and high precision aiming to produce a high precision final merged list. For the latter goal in particular, the new approach steps away from the usual practice of DIR systems of explicitly declaring the number of collections that must be queried and instead receives as input only the number of retrieved documents in the final merged list, dynamically calculating the number of collections that are selected and the number of documents requested from each. The algorithm is tested in a wide range of testbeds in both recall and precision oriented settings and its effectiveness is found to be equal or better than other state-of-the-art algorithms.

REFERENCES

• 1: 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]
• 2: Peter Bailey , Nick Craswell , David Hawking, Engineering a multi-purpose test collection for web retrieval experiments, Information Processing and Management: an International Journal, v.39 n.6, p.853-871, November 2003 [doi>10.1016/S0306-4573(02)00084-5]
• 3: M. Bergman. The deep web: Surfacing hidden value.
• 4: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 5: J. Callan. Advances in information retrieval chapter 5, pages 127--150. Kluwer Academic Publishers, 2000.
• 6: 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]
• 7: J. Callan, W. Croft, and S. Harding. Inquery retrieval system. In DEXA-92 pages 78--83, 1992.
• 8: 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]
• 9: N. Craswell. Methods for Distributed Information Retrieval PhD thesis, ANU, 2000.
• 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: L. Gravano, K. Chang, H. Garcia-Molina, and A. Paepcke. Starts. Stanford University, 1997.
• 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: David Hawking , Paul Thomas, Server selection methods in hybrid portal search, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076050]
• 14: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 15: Art Lew , Holger Mauch, Dynamic Programming: A Computational Tool (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 16: P. Lyman and H. R. Varian. How much information? 2003. 2003.
• 17: Craig Macdonald , Iadh Ounis, Voting for candidates: adapting data fusion techniques for an expert search task, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183671]
• 18: Henrik Nottelmann , Norbert Fuhr, Evaluating different methods of estimating retrieval quality 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.860489]
• 19: Paul Ogilvie , Jamie Callan, Combining document representations for known-item search, 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.860463]
• 20: P. Ogilvie and J. P. Callan. Experiments using the lemur toolkit. In TREC 2001.
• 21: Georgios Paltoglou , Michail Salampasis , Maria Satratzemi, Hybrid results merging, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321487]
• 22: Allison L. Powell , James C. French, Comparing the performance of collection selection algorithms, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.412-456, October 2003 [doi>10.1145/944012.944016]
• 23: S. Robertson, S. Walker, H.-B. M., and G. M. Okapi at trec-3. In TREC-3 1994.
• 24: C. Sherman. Search for the invisible web. Guardian Unlimited, 2001.
• 25: M. Shokouhi. Central-rank-based collection selection in uncooperative distributed information retrieval. In ECIR pages 160--172, 2007.
• 26: Milad Shokouhi , Justin Zobel , Falk Scholer , S. M. M. Tahaghoghi, Capturing collection size for distributed non-cooperative retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148227]
• 27: 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]
• 28: Luo Si , Jamie Callan, A semisupervised learning method to merge search engine results, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.457-491, October 2003 [doi>10.1145/944012.944017]
• 29: Luo Si , Jamie Callan, Unified utility maximization framework for resource selection, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031180]
• 30: Luo Si , Jamie Callan, Modeling search engine effectiveness for federated search, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076051]
• 31: Paul Thomas , David Hawking, Evaluating sampling methods for uncooperative collections, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277828]
• 32: 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.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation

Keywords:
distributed information retrieval, federated search, source selection