Robust result merging using sample-based score estimates

ABSTRACT

In federated information retrieval, a query is routed to multiple collections and a single answer list is constructed by combining the results. Such metasearch provides a mechanism for locating documents on the hidden Web and, by use of sampling, can proceed even when the collections are uncooperative. However, the similarity scores for documents returned from different collections are not comparable, and, in uncooperative environments, document scores are unlikely to be reported. We introduce a new merging method for uncooperative environments, in which similarity scores for the sampled documents held for each collection are used to estimate global scores for the documents returned per query. This method requires no assumptions about properties such as the retrieval models used. Using experiments on a wide range of collections, we show that in many cases our merging methods are significantly more effective than previous techniques.

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: Javed A. Aslam , Virgiliu Pavlu , Robert Savell, A unified model for metasearch, pooling, and system evaluation, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956953]
• 3: 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]
• 4: 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]
• 5: Leif Azzopardi , Mark Baillie , Fabio Crestani, Adaptive query-based sampling for distributed IR, 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.1148277]
• 6: Baillie, M., Azzopardi, L., and Crestani, F. 2006. Adaptive query-based sampling of distributed collections. In SPIRE String Processing and Information Retrieval Symposium. Springer, Glasgow, U.K. 316--328.
• 7: Ziv Bar-Yossef , Maxim Gurevich, Random sampling from a search engine's index, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135833]
• 8: Bernstein, Y., Shokouhi, M., and Zobel, J. 2006. Compact features for detection of near-duplicates in distributed retrieval. In SPIRE String Processing and Information Retrieval Symposium. Springer, Glasgow, U.K. 110--121.
• 9: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Computer Networks and ISDN Systems, v.30 n.1-7, p.379-388, April 1, 1998
• 10: Callan, J. 2000. Distributed information retrieval. Advances in Information Retrieval. Kluwer, Norwell, MA, Chapter 5, 127--150.
• 11: 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]
• 12: 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
• 13: James P. Callan , W. Bruce Croft , John Broglio, TREC and TIPSTER experiments with INQUERY, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 14: 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]
• 15: James Caverlee , Ling Liu , Joonsoo Bae, Distributed query sampling: a quality-conscious approach, 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.1148230]
• 16: Nick Craswell , Peter Bailey , David Hawking, Server selection on the World Wide Web, Proceedings of the fifth ACM conference on Digital libraries, p.37-46, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336628]
• 17: Craswell, N., Hawking, D., and Thistlewaite, P. 1999. Merging results from isolated search engines. In Proceedings of the 10th Australasian Database Conference. Springer-Verlag, Auckland, New Zealand, 189--200.
• 18: Croft, B. 2000. Combining approaches to information retrieval. Advances in Information Retrieval. Kluwer, Norwell, MA, Chapter 1, 1--36.
• 19: Daniel Dreilinger , Adele E. Howe, Experiences with selecting search engines using metasearch, ACM Transactions on Information Systems (TOIS), v.15 n.3, p.195-222, July 1997 [doi>10.1145/256163.256164]
• 20: D'Souza, D. and Thom, J. 1999. Collection selection using n-term indexing. In Proceedings of the Second International Symposium on Cooperative Database Systems for Advanced Applications (CODAS'99). Springer, Wollongong, Australia, 52--63.
• 21: Daryl D'Souza , James A. Thom , Justin Zobel, Collection selection for managed distributed document databases, Information Processing and Management: an International Journal, v.40 n.3, p.527-546, January 2004 [doi>10.1016/S0306-4573(03)00008-6]
• 22: Fox, E. and Shaw, J. 1993. Combination of multiple searches. In Proceedings of the Second Text REtrieval Conference. NIST Special Publication. National Institute of Science and Technology, Gaithersburg, MD, 243--252.
• 23: 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]
• 24: 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]
• 25: Steven Garcia , Hugh E. Williams , Adam Cannane, Access-ordered indexes, Proceedings of the 27th Australasian conference on Computer science, p.7-14, January 01, 2004, Dunedin, New Zealand
• 26: Eric J. Glover , Steve Lawrence , William P. Birmingham , C. Lee Giles, Architecture of a metasearch engine that supports user information needs, Proceedings of the eighth international conference on Information and knowledge management, p.210-216, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319980]
• 27: Luis Gravano , Chen-Chuan K. Chang , Héctor García-Molina , Andreas Paepcke, STARTS: Stanford proposal for Internet meta-searching, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.207-218, May 11-15, 1997, Tucson, Arizona, United States
• 28: 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
• 29: Luis Gravano , Héctor García-Molina , Anthony Tomasic, The effectiveness of GIOSS for the text database discovery problem, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.126-137, May 24-27, 1994, Minneapolis, Minnesota, United States
• 30: Luis Gravano , Hector Garcia-Molina , Anthony Tomasic, Precision and Recall of GlOSS Estimators for Database Discovery, Proceedings of the Third International Conference on Parallel and Distributed Information Systems, p.103-106, September 28-30, 1994
• 31: 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]
• 32: Luis Gravano , Panagiotis G. Ipeirotis , Mehran Sahami, QProber: A system for automatic classification of hidden-Web databases, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.1-41, January 2003 [doi>10.1145/635484.635485]
• 33: Gross, J. 2003. Linear Regression. Springer, Berlin, Germany.
• 34: Y. L. Hedley , M. Younas , A. James , M. Sanderson, A two-phase sampling technique for information extraction from hidden web databases, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031456]
• 35: Hedley, Y., Younas, M., James, A., and Sanderson, M. 2004b. A two-phase sampling technique to improve the accuracy of text similarities in the categorisation of hidden Web databases. In Proceedings of the International Conference on Web Informations Systems. Springer, Brisbane, Australia, 516--527.
• 36: Panagiotis G. Ipeirotis , Luis Gravano, When one sample is not enough: improving text database selection using shrinkage, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007655]
• 37: 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]
• 38: Kirsch, T. 2003. Document retrieval over networks wherein ranking and relevance scores are computed at the client for multiple database documents. U.S. Patent 5,659,732.
• 39: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 40: Leah S. Larkey , Margaret E. Connell , Jamie Callan, Collection selection and results merging with topically organized U.S. patents and TREC data, Proceedings of the ninth international conference on Information and knowledge management, p.282-289, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354830]
• 41: Steve Lawrence , C. Lee Giles, Inquirus, the NECI meta search engine, Proceedings of the seventh international conference on World Wide Web 7, p.95-105, April 1998, Brisbane, Australia
• 42: Joon Ho Lee, Analyses of multiple evidence combination, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-276, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 43: David Lillis , Fergus Toolan , Rem Collier , John Dunnion, ProbFuse: a probabilistic approach to data fusion, 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.1148197]
• 44: Jie Lu , Jamie Callan, Pruning long documents for distributed information retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584847]
• 45: 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]
• 46: Ng, K. 1998. An investigation of the conditions for effective data fusion in information retrieval. Ph.D. dissertation. Rutgers University, New Brunswick, NJ.
• 47: 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]
• 48: Paul Ogilvie , Jamie Callan, The effectiveness of query expansion for distributed information retrieval, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502617]
• 49: B. Uygar Oztekin , George Karypis , Vipin Kumar, Expert agreement and content based reranking in a meta search environment using Mearf, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511490]
• 50: Paltoglou, G., Salampasis, M., and Satratzemi, M. 2007. Results merging algorithm using multiple regression models. In Proceedings of the Euorpean Conference on Information Retrieval. Springer, Rome, Italy, 173--184.
• 51: M. F. Porter, An algorithm for suffix stripping, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 52: 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]
• 53: Yves Rasolofo , Faïza Abbaci , Jacques Savoy, Approaches to collection selection and results merging for distributed information retrieval, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502618]
• 54: Yves Rasolofo , David Hawking , Jacques Savoy, Result merging strategies for a current news metasearcher, Information Processing and Management: an International Journal, v.39 n.4, p.581-609, July 2003 [doi>10.1016/S0306-4573(02)00122-X]
• 55: Selberg, E. and Etzioni, O. 1995. Multi-service search and comparison using the metacrawler. In Proceedings of the 4th International Conference on the World Wide Web. Oreilly, Boston, MA.
• 56: Selberg, E. and Etzioni, O. 1997. The MetaCrawler architecture for resource aggregation on the web. IEEE Expert 12, 1, 8--14.
• 57: Shokouhi, M. 2007. Central-rank-based collection selection in uncooperative distributed information retrieval. In Proceedings of the Euorpean Conference on Information Retrieval. Springer, Rome, Italy, 160--172.
• 58: Shokouhi, M., Scholer, F., and Zobel, J. 2006a. Sample sizes for query probing in uncooperative distributed information retrieval. In Proceedings of the 8th Asia Pacific Web Conference. Springer (Harbin, China). 63--75.
• 59: Milad Shokouhi , Justin Zobel, Federated text retrieval from uncooperative overlapped 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.1277827]
• 60: Milad Shokouhi , Justin Zobel , Yaniv Bernstein, Distributed text retrieval from overlapping collections, Proceedings of the eighteenth conference on Australasian database, p.141-150, January 30-February 02, 2007, Ballarat, Victoria, Australia
• 61: 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]
• 62: 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]
• 63: Si, L. and Callan, J. 2003a. The effect of database size distribution on resource selection algorithms. In Proeedings of the SIGIR 2003 Workshop on Distributed Information Retrieval (Toronto, Ont., Canada). 31--42.
• 64: 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]
• 65: 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]
• 66: 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]
• 67: 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]
• 68: Luo Si , Rong Jin , Jamie Callan , Paul Ogilvie, A language modeling framework for resource selection and results merging, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584856]
• 69: 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]
• 70: Christopher Charles Vogt , Garrison W. Cottrell, Adaptive combination of evidence for information retrieval, University of California, San Diego, 1999
• 71: Christopher C. Vogt , Garrison W. Cottrell, Fusion Via a Linear Combination of Scores, Information Retrieval, v.1 n.3, p.151-173, October 1999 [doi>10.1023/A:1009980820262]
• 72: Yuan Wang , David J. DeWitt, Computing pagerank in a distributed internet search system, Proceedings of the Thirtieth international conference on Very large data bases, p.420-431, August 31-September 03, 2004, Toronto, Canada
• 73: Shengli Wu , Sally McClean, Performance prediction of data fusion for information retrieval, Information Processing and Management: an International Journal, v.42 n.4, p.899-915, July 2006 [doi>10.1016/j.ipm.2005.08.004]
• 74: Shengli Wu , Sally McClean, Result merging methods in distributed information retrieval with overlapping databases, Information Retrieval, v.10 n.3, p.297-319, June 2007 [doi>10.1007/s10791-007-9023-y]
• 75: 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]
• 76: 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]
• 77: Jingfang Xu , Sheng Wu , Xing Li, Estimating collection size with logistic regression, 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.1277910]
• 78: Zhai, C. 2001. Notes on the lemur TFIDF model. School of Computer Science. Carnegie Mellon University, Pittsburgh, PA. unpublished report. www.cs.cmu.edu/~lemur/1.1/tfidf.ps.
• 79: Zobel, J. 1997. Collection selection via lexicon inspection. In Proceedings of the Australian Document Computing Symposium (Melbourne, Australia). 74--80.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
Result merging, distributed information retrieval, result fusion, uncooperative collections