SUSHI: scoring scaled samples for server selection

ABSTRACT

Modern techniques for distributed information retrieval use a set of documents sampled from each server, but these samples have been underutilised in server selection. We describe a new server selection algorithm, SUSHI, which unlike earlier algorithms can make full use of the text of each sampled document and which does not need training data. SUSHI can directly optimise for many common cases, including high precision retrieval, and by including a simple stopping condition can do so while reducing network traffic.

Our experiments compare SUSHI with alternatives and show it achieves the same effectiveness as the best current methods while being substantially more efficient, selecting as few as 20% as many servers.

REFERENCES

• 1: A Methodology for Collection Selection in Heterogeneous Contexts, Proceedings of the International Conference on Information Technology: Coding and Computing, p.529, April 08-10, 2002
• 2: Thi Truong Avrahami , Lawrence Yau , Luo Si , Jamie Callan, The FedLemur project: Federated search in the real world, Journal of the American Society for Information Science and Technology, v.57 n.3, p.347-358, February 2006 [doi>10.1002/asi.v57:3]
• 3: 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]
• 4: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 5: Jamie Callan , Margaret Connell , Aiqun Du, Automatic discovery of language models for text databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.479-490, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: 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]
• 7: N. Craswell, D. Hawking, and P. Thistlewaite. Merging results from isolated search engines. In Proc. Australasian Database Conference, 1999.
• 8: D. D'Souza, J. Zobel, and J.A. Thom. Is CORI effective for collection selection? An exploration of parameters, queries, and data. In Proc. Australasian Document Computing Symposium, 2004.
• 9: 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]
• 10: 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
• 11: D.K. Harman. The TREC test collections. In E.M. Voorhees and D.K. Harman, editors, TREC: Experiment and Evaluation in Information Retrieval. MIT Press, 2005.
• 12: David Hawking , Stephen Robertson, On Collection Size and Retrieval Effectiveness, Information Retrieval, v.6 n.1, p.99-105, January 2003 [doi>10.1023/A:1022904715765]
• 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: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, 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.1076063]
• 15: King-Lup Liu , Adrain Santoso , Clement Yu , Weiyi Meng, Discovering the representative of a search engine, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502696]
• 16: R. Manmatha , H. Sever, A formal approach to score normalization for meta-search, Proceedings of the second international conference on Human Language Technology Research, March 24-27, 2002, San Diego, California
• 17: W. Meng, W. Wang, H. Sun, and C. Yu. Concept hierarchy based text database categorization. Knowledge and Information Systems, 4(2), 2002.
• 18: H. Nottelmann and N. Fuhr. Combining CORI and the decision-theoretic approach for advanced resource selection. In Proc. ECIR, 2004.
• 19: M. Shokouhi. Central-rank-based collection selection in uncooperative distributed information retrieval. In Proc. ECIR, 2007.
• 20: Milad Shokouhi , Justin Zobel, Robust result merging using sample-based score estimates, ACM Transactions on Information Systems (TOIS), v.27 n.3, p.1-29, May 2009 [doi>10.1145/1508850.1508852]
• 21: 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]
• 22: L. Si and J. Callan. The eect of database size distribution on resource selection algorithms. In Proc. ACM SIGIR, 2003.
• 23: 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]
• 24: 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]
• 25: 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]
• 26: 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]
• 27: P. Thomas. Server Characterisation and Selection for Personal Metasearch. PhD thesis, Australian National University, 2008.
• 28: 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]

INDEX TERMS

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

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

General Terms:
Experimentation, Measurement

Keywords:
document samples