Efficiency trade-offs in two-tier web search systems

ABSTRACT

Search engines rely on searching multiple partitioned corpora to return results to users in a reasonable amount of time. In this paper we analyze the standard two-tier architecture for Web search with the difference that the corpus to be searched for a given query is predicted in advance. We show that any predictor better than random yields time savings, but this decrease in the processing time yields an increase in the infrastructure cost. We provide an analysis and investigate this trade-off in the context of two different scenarios on real-world data. We demonstrate that in general the decrease in answer time is justified by a small increase in infrastructure cost.

REFERENCES

• 1: Ricardo Baeza-Yates , Aristides Gionis , Flavio Junqueira , Vanessa Murdock , Vassilis Plachouras , Fabrizio Silvestri, The impact of caching on search engines, 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.1277775]
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: J. Callan, W. B. Croft, and S. M. Harding. The INQUERY retrieval system. In Proceedings of the 3rd International Conference on Database and Expert Systems Applications, pages 78--83, 1992.
• 4: 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]
• 5: 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]
• 6: Nick Craswell , Francis Crimmins , David Hawking , Alistair Moffat, Performance and cost tradeoffs in Web search, Proceedings of the 15th Australasian database conference, p.161-169, January 01, 2004, Dunedin, New Zealand
• 7: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Predicting query performance, 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.564429]
• 8: 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]
• 9: 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
• 10: Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
• 11: Claudia Hauff , Leif Azzopardi , Djoerd Hiemstra, The Combination and Evaluation of Query Performance Prediction Methods, Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval, April 06-09, 2009, Toulouse, France [doi>10.1007/978-3-642-00958-7_28]
• 12: B. He and I. Ounis. Inferring query performance using pre-retrieval predictors. In Proceedings of SPIRE, 2004.
• 13: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 14: Robert Krovetz, Viewing morphology as an inference process, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.191-202, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160718]
• 15: Yiqun Liu , Min Zhang , Rongwei Cen , Liyun Ru , Shaoping Ma, Data cleansing for Web information retrieval using query independent features, Journal of the American Society for Information Science and Technology, v.58 n.12, p.1884-1898, October 2007 [doi>10.1002/asi.v58:12]
• 16: Alexandros Ntoulas , Junghoo Cho, Pruning policies for two-tiered inverted index with correctness guarantee, 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.1277776]
• 17: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 18: K. M. Risvik. Scaling Internet Search Engines: Methods and Analysis. PhD thesis, NTNU, 2004.
• 19: Knut Magne Risvik , Yngve Aasheim , Mathias Lidal, Multi-Tier Architecture for Web Search Engines, Proceedings of the First Conference on Latin American Web Congress, p.132, November 10-12, 2003
• 20: 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]
• 21: Gleb Skobeltsyn , Flavio Junqueira , Vassilis Plachouras , Ricardo Baeza-Yates, ResIn: a combination of results caching and index pruning for high-performance web search engines, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390359]
• 22: Ian Soboroff, Does WT10g look like the web?, 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.564475]
• 23: A. Spink, J. Bateman, and B. J. Jansen. Searching heterogeneous collections on the web: Behavior of excite users. Information Research, 4(2), 1998. Available at http://informationr.net/ir/4-2/paper53.html.
• 24: E. Yom-Tov, D. Carmel, A. Darlow, D. Pelleg, S. Errera-Yaakov, and S. Fine. Juru at TREC 2005: Query prediction in the teraybyte and the robust tracks. In TREC 2005, 2005.
• 25: Elad Yom-Tov , Shai Fine , David Carmel , Adam Darlow, Learning to estimate query difficulty: including applications to missing content detection and distributed information retrieval, 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.1076121]
• 26: 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
• 27: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]
• 28: J. Zobel. Collection selection via lexicon inspection. In Proceedings of the Second Australian Document Computing Symposium, 1997.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
distributed systems, pre-retrieval prediction, tiered indexing