Mining query logs to optimize index partitioning in parallel web search engines

ABSTRACT

Large-scale Parallel Web Search Engines (WSEs) needs to adopt a strategy for partitioning the inverted index among a set of parallel server nodes.

In this paper we are interested in devising an effective term-partitioning strategy, according to which the global vocabulary of terms and the associated inverted lists are split into disjoint subsets, and assigned to distinct servers. Due to the workload imbalance caused by the skewed distribution of terms in user queries, finding an effective partitioning strategy is considered a very complex task.

In this paper we first formally introduce Term Partitioning as a new optimization problem. Then we show how the knowledge mined from past WSE query logs can be profitably used to discover good solutions of this problem. Finally, we report many results to show that we are able to effectively reduce both the average number of servers activated per each query, along with the workload imbalance. Experiments are conducted on large query logs of real WSEs.

REFERENCES

• 1: Luiz André Barroso , Jeffrey Dean , Urs Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, v.23 n.2, p.22-28, March 2003 [doi>10.1109/MM.2003.1196112]
• 2: Brendon Cahoon , Kathryn S. McKinley , Zhihong Lu, Evaluating the performance of distributed architectures for information retrieval using a variety of workloads, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.1-43, Jan. 2000 [doi>10.1145/333135.333136]
• 3: Tiziano Fagni , Raffaele Perego , Fabrizio Silvestri , Salvatore Orlando, Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.51-78, January 2006 [doi>10.1145/1125857.1125859]
• 4: Donna Harman , Wayne McCoy , Robert Toense , Gerald Candela, Prototyping a distributed information retrieval system that uses statistical ranking, Information Processing and Management: an International Journal, v.27 n.5, p.449-459, 1991 [doi>10.1016/0306-4573(91)90062-Q]
• 5: Byeong-Soo Jeong , Edward Omiecinski, Inverted File Partitioning Schemes in Multiple Disk Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.142-153, February 1995 [doi>10.1109/71.342125]
• 6: Owen de Kretser , Alistair Moffat , Tim Shimmin , Justin Zobel, Methodologies for Distributed Information Retrieval, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.66, May 26-29, 1998
• 7: Ian A. Macleod , Patrick Martin , Brent Nordin , John R. Phillips, Strategies for building distributed information retrieval systems, Information Processing and Management: an International Journal, v.23 n.6, p.511-528, Sept. 2, 1987 [doi>10.1016/0306-4573(87)90056-2]
• 8: Alistair Moffat , William Webber , Justin Zobel, Load balancing for term-distributed parallel 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.1148232]
• 9: Alistair Moffat , William Webber , Justin Zobel , Ricardo Baeza-Yates, A pipelined architecture for distributed text query evaluation, Information Retrieval, v.10 n.3, p.205-231, June 2007 [doi>10.1007/s10791-006-9014-4]
• 10: A. Moffat and J. Zobel. What does it mean to 'measure performance'? In Proc. of the Intl. Conf. on Web Inf. Syst., pages 1--12, Brisbane, Australia, November 2004.
• 11: Berthier Ribeiro-Neto , Edleno S. Moura , Marden S. Neubert , Nivio Ziviani, Efficient distributed algorithms to build inverted files, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.105-112, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312663]
• 12: C. Santos-Badue, R. A. Baeza-Yates, B. A. Ribeiro-Neto, and N. Ziviani. Distributed query processing using partitioned inverted files. In Proc. of Intl. Symp. on String Process. and Inf. Retr., pages 10--20, 2001.
• 13: Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
• 14: Y. Xie and D. O'Hallaron. Locality in search engine queries and its implications for caching. In Proc. of IEEE Infocom 2002, New York, USA, June 2002.
• 15: Jiangong Zhang , Torsten Suel, Efficient Query Evaluation on Large Textual Collections in a Peer-to-Peer Environment, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.225-233, August 31-September 02, 2005 [doi>10.1109/P2P.2005.7]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing