Quantifying performance and quality gains in distributed web search engines

ABSTRACT

Distributed search engines based on geographical partitioning of a central Web index emerge as a feasible solution to the immense growth of the Web, user bases, and query traffic. However, there is still lack of research in quantifying the performance and quality gains that can be achieved by such architectures. In this paper, we develop various cost models to evaluate the performance benefits of a geographically distributed search engine architecture based on partial index replication and query forwarding. Specifically, we focus on possible performance gains due to the distributed nature of query processing and Web crawling processes. We show that any response time gain achieved by distributed query processing can be utilized to improve search relevance as the use of complex but more accurate algorithms can now be enabled for document ranking. We also show that distributed Web crawling leads to better Web coverage and try to see if this improves the search quality. We verify the validity of our claims over large, real-life datasets via simulations.

REFERENCES

• 1: R. Baeza-Yates, C. Castillo, F. Junqueira, V. Plachouras, and F. Silvestri. Challenges in distributed information retrieval. In Proc. 23rd Int'l Conf. on Data Engineering, pages 6--20, 2007.
• 2: Ricardo Baeza-Yates , Carlos Castillo , Mauricio Marin , Andrea Rodriguez, Crawling a country: better strategies than breadth-first for web page ordering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062768]
• 3: R. Baeza-Yates, A. Gionis, F. Junqueira, V. Plachouras, and L. Telloli. On the feasibility of multi-site web search engines. Unpublished manuscript, 2009.
• 4: Mayank Bawa , Gurmeet Singh Manku , Prabhakar Raghavan, SETS: search enhanced by topic segmentation, 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.860491]
• 5: J. Callan. Distributed information retrieval. In Advances in Information Retrieval. Recent Research from the Center for Intelligent Information Retrieval, volume 7 of The Kluwer Int'l Series on Information Retrieval, chapter 5, pages 127--150, 2000.
• 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: B. Barla Cambazoglu , Vassilis Plachouras , Flavio Junqueira , Luca Telloli, On the feasibility of geographically distributed web crawling, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy
• 8: Junghoo Cho , Hector Garcia-Molina, Parallel crawlers, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511464]
• 9: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Computer Networks and ISDN Systems, v.30 n.1-7, p.161-172, April 1, 1998
• 10: D. Harman and G. Candela. Retrieving records from a gigabyte of text on a multicomputer using statistical ranking. Journal of the American Society for Information Science, 41(8):581--589, 1990.
• 11: B. Huffaker, M. Fomenkov, D. J. Plummer, D. Moore, and K. Claffy. Distance metrics in the internet. In Proc. Int'l Telecommunications Symposium, 2002.
• 12: Marc Najork , Janet L. Wiener, Breadth-first crawling yields high-quality pages, Proceedings of the 10th international conference on World Wide Web, p.114-118, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371965]
• 13: Diego Puppin , Fabrizio Silvestri , Domenico Laforenza, Query-driven document partitioning and collection selection, Proceedings of the 1st international conference on Scalable information systems, p.34-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146881]
• 14: Charalampos Sarigiannis , Vassilis Plachouras , Ricardo Baeza-Yates, A Study of the Impact of Index Updates on Distributed Query Processing for Web Search, 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_55]
• 15: C. Tang, Z. Xu, and M. Mahalingam. Peersearch: Efficient information retrieval in peer-to-peer networks. In HotNets-I, 2002.
• 16: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

INDEX TERMS

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

General Terms:
Experimentation, Performance

Keywords:
data centers, distributed query processing, index partitioning, web crawling