Repeatable evaluation of search services in dynamic environments

ABSTRACT

In dynamic environments, such as the World Wide Web, a changing document collection, query population, and set of search services demands frequent repetition of search effectiveness (relevance) evaluations. Reconstructing static test collections, such as in TREC, requires considerable human effort, as large collection sizes demand judgments deep into retrieved pools. In practice it is common to perform shallow evaluations over small numbers of live engines (often pairwise, engine A vs. engine B) without system pooling. Although these evaluations are not intended to construct reusable test collections, their utility depends on conclusions generalizing to the query population as a whole. We leverage the bootstrap estimate of the reproducibility probability of hypothesis tests in determining the query sample sizes required to ensure this, finding they are much larger than those required for static collections. We propose a semiautomatic evaluation framework to reduce this effort. We validate this framework against a manual evaluation of the top ten results of ten Web search engines across 896 queries in navigational and informational tasks. Augmenting manual judgments with pseudo-relevance judgments mined from Web taxonomies reduces both the chances of missing a correct pairwise conclusion, and those of finding an errant conclusion, by approximately 50%.

REFERENCES

• 1: Javed A. Aslam , Virgil Pavlu , Emine Yilmaz, A statistical method for system evaluation using incomplete judgments, 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.1148263]
• 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: Bacchetti, P. 2002. Peer review of statistics in medical research: The other problem. Brit. Med. J. 324, 1271--1273.
• 4: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman, Using titles and category names from editor-driven taxonomies for automatic evaluation, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956868]
• 5: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Using manually-built web directories for automatic evaluation of known-item retrieval, 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.860507]
• 6: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Evaluation of filtering current news search results, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009087]
• 7: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Hourly analysis of a very large topically categorized web query log, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009048]
• 8: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , Ophir Frieder , David Grossman, Temporal analysis of a very large topically categorized Web query log, Journal of the American Society for Information Science and Technology, v.58 n.2, p.166-178, January 2007 [doi>10.1002/asi.v58:2]
• 9: Blustein, J. and Tague-Sutcliffe, J. 1995. IR-stat-pak. In Presented at the ACM Conference on Research and Development in Information Retrieval.
• 10: Pia Borlund, The concept of relevance in IR, Journal of the American Society for Information Science and Technology, v.54 n.10, p.913-925, August 2003 [doi>10.1002/asi.10286]
• 11: Boyan, J., Freitag, D., and Joachims, T. 1996. A machine learning architecture for optimizing Web search engines. In Proceedings of the AAAI Workshop on Internet Based Information Systems.
• 12: Chris Buckley , Ellen M. Voorhees, Evaluating evaluation measure stability, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.33-40, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345543]
• 13: Ben Carterette , James Allan , Ramesh Sitaraman, Minimal test collections for retrieval evaluation, 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.1148219]
• 14: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Proceedings of the seventh international conference on World Wide Web 7, p.161-172, April 1998, Brisbane, Australia
• 15: Abdur Chowdhury , Ian Soboroff, Automatic evaluation of world wide web search services, 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.564474]
• 16: Chowdhury, A. 2005. Automatic evaluation of Web search services. In Zelkowitz, M., Ed. Advances in Computers, Elsevier Academic Press.
• 17: Clarke, C., Scholer, F., and Soboroff, I. 2005. The TREC 2005 terabyte track. In Proceedings of the The Text Retrieval Conference, NIST.
• 18: Collings, B. J. and Hamilton, M. A. 1988. Estimating the power of the two sample Wilcoxon test for location shift. Biometrics 44, 847--860.
• 19: Gordon V. Cormack , Christopher R. Palmer , Charles L. A. Clarke, Efficient construction of large test collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.282-289, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291009]
• 20: Gordon V. Cormack , Thomas R. Lynam, Statistical precision of information retrieval evaluation, 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.1148262]
• 21: Davidson, R. and MacKinnon, J. G. 2000. Bootstrap tests: How many bootstraps? Econometric Rev. 19, 55--68.
• 22: Davidson, R. and MacKinnon, J. G. 2006. The power of bootstrap and asymptotic tests. J. Econometrics 133, 421--441.
• 23: De Martini, D. and Rapallo, F. 2003. Calculating the power of permutation tests: A comparison between nonparametric estimators. J. Appl. Stat. Sci. 11, 109--120.
• 24: De Martini, D. 2006. On the stability of statistical tests. In Proceedings of the ASA Joint Statistical Meeting.
• 25: Ding, W. and Marchionini, G. 1996. Comparative study of Web search service performance. In Proceedings of the ASIS 1996 Annual Conference.
• 26: Efron, B. and Tibshirani, R. J. 1993. An Introduction to the Bootstrap. Chapman & Hall/CRC, 379--381.
• 27: Goldstein, J., Lavie, A., Lin, C.-Y., and Voss, C. 2005. Workshop: Intrinsic and extrinsic evaluation measures for MT and/or summarization. In Proceedings of the Annual Meeting of the Association of Computational Linguistics.
• 28: Goodman, S. N. 1992. A comment on replication, p-values and evidence. Stat. Med. 11, 875--879.
• 29: Hall, P. and Martin, M. A. 1988. On bootstrap resampling and iteration. Biometrika 75(4), 661--671.
• 30: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 31: David Hawking , Nick Craswell , Paul Thistlewaite , Donna Harman, Results and challenges in Web search evaluation, Proceedings of the eighth international conference on World Wide Web, p.1321-1330, May 1999, Toronto, Canada
• 32: Hoenig, J. M. and Heisey, D. M. 2001. The abuse of power: The pervasive fallacy of power calculations for data analysis. Amer. Statist. 55(1), 19--24.
• 33: Hollander, M. and Wolfe, D. 1973. Nonparametric Statistical Methods. John Wiley and Sons.
• 34: Bernard J. Jansen , Amanda Spink, How are we searching the world wide web?: a comparison of nine search engine transaction logs, Information Processing and Management: an International Journal, v.42 n.1, p.248-263, January 2006 [doi>10.1016/j.ipm.2004.10.007]
• 35: Bernard J. Jansen , Amanda Spink , Jan Pedersen, A temporal comparison of AltaVista Web searching: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.6, p.559-570, April 2005 [doi>10.1002/asi.v56:6]
• 36: Eric C. Jensen , Steven M. Beitzel , Ophir Frieder , Abdur Chowdhury, A framework for determining necessary query set sizes to evaluate web search effectiveness, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062926]
• 37: Eric C. Jensen , Ophir Frieder, Repeatable evaluation of information retrieval effectiveness in dynamic environments, Illinois Institute of Technology, Chicago, IL, 2006
• 38: 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]
• 39: Lehmann, E. 1986. Testing Statistical Hypotheses. Wiley, 150.
• 40: Wei-Hao Lin , Alexander Hauptmann, Revisiting the effect of topic set size on retrieval error, 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.1076166]
• 41: R. Manmatha , Ao Feng , James Allan, A critical examination of TDT's cost function, 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.564465]
• 42: Miller, R. G., Jr. 1981. Simultaneous Statistical Inference. Springer, New York.
• 43: Munzel, U. 2001. A unified approach to simultaneous rank test procedures in the unbalanced one-way layout. Biomet. J. 43(5), 553--569.
• 44: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 45: Rabia Nuray , Fazli Can, Automatic ranking of information retrieval systems using data fusion, Information Processing and Management: an International Journal, v.42 n.3, p.595-614, May 2006 [doi>10.1016/j.ipm.2005.03.023]
• 46: Greg Pass , Abdur Chowdhury , Cayley Torgeson, A picture of search, Proceedings of the 1st international conference on Scalable information systems, p.1-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146848]
• 47: Tetsuya Sakai, Evaluating evaluation metrics based on the bootstrap, 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.1148261]
• 48: Mark Sanderson , Hideo Joho, Forming test collections with no system pooling, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009001]
• 49: Mark Sanderson , Justin Zobel, Information retrieval system evaluation: effort, sensitivity, and reliability, 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.1076064]
• 50: Jacques Savoy, Statistical inference in retrieval effectiveness evaluation, Information Processing and Management: an International Journal, v.33 n.4, p.495-512, July 1997 [doi>10.1016/S0306-4573(97)00027-7]
• 51: Jacques Savoy , Justin Picard, Retrieval effectiveness on the web, Information Processing and Management: an International Journal, v.37 n.4, p.543-569, July 2001 [doi>10.1016/S0306-4573(00)00039-X]
• 52: Yi Shang , Longzhuang Li, Precision Evaluation of Search Engines, World Wide Web, v.5 n.2, p.159-173, 2002 [doi>10.1023/A:1019679624079]
• 53: Shao, J. and Chow, S.-C. 2002. Reproducibility probability in clinical trials. Statistics in Medicine 21(12), 1727--1742.
• 54: Ian Soboroff , Charles Nicholas , Patrick Cahan, Ranking retrieval systems without relevance judgments, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.66-73, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383961]
• 55: Ian Soboroff, Dynamic test collections: measuring search effectiveness on the live web, 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.1148220]
• 56: Spiegelhalter, D. J. and Freedman, L. S. 1986. A predictive approach to selecting the size of a clinical trial, based on subjective clinical opinion. Statistics in Medicine 5, 1--13.
• 57: P. Srinivasan , F. Menczer , G. Pant, A General Evaluation Framework for Topical Crawlers, Information Retrieval, v.8 n.3, p.417-447, May 2005 [doi>10.1007/s10791-005-6993-5]
• 58: Jean M. Tague-Sutcliffe, Some perspectives on the evaluation of information retrieval systems, Journal of the American Society for Information Science, v.47 n.1, p.1-3, Jan. 1996 [doi>10.1002/(SICI)1097-4571(199601)47:1<1::AID-ASI1>3.3.CO;2-H]
• 59: Troendle, J. F. 1999. Approximating the power of wilcoxon's rank-sum test against shift alternatives. Stat. Med. 18(20) (Oct.), 2763--2773.
• 60: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 61: Ellen M. Voorhees, Variations in relevance judgments and the measurement of retrieval effectiveness, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.315-323, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291017]
• 62: Ellen M. Voorhees , Chris Buckley, The effect of topic set size on retrieval experiment error, 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.564432]
• 63: Shengli Wu , Fabio Crestani, Methods for ranking information retrieval systems without relevance judgments, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952693]
• 64: Justin Zobel, How reliable are the results of large-scale information retrieval experiments?, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.307-314, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291014]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation

Keywords:
Evaluation, Web search