Efficient Document Partitioning for Load Balancing between Servers Using Term Frequency of Past Queries
Subject Areas : electrical and computer engineeringReyhaneh Torab 1 , Sajjad Zarifzadeh 2 *
1 - Yazd University
2 - Yazd University
Keywords: Load balancingdocument partitioninghistory of queriessearch engine,
Abstract :
The main goal of web search engines is to find the most relevant results with respect to the user query in a shortest possible time. To do so, the crawled documents have to be partitioned between several servers in order to use their aggregate retrieval and processing power. The search engines use different policies for efficient partitioning of documents. In this paper, we propose a new document partitioning method that intends to balance the load between servers to reduce the response time of queries. The idea is to weigh each term based on its daily frequency in log of past queries. We then assign a weight to each document via summing the weight of its substituent terms. The weight of a document approximates the likelihood of its presence in future search results. Finally, the documents are partitioned between servers in a way that the sum of document weights in each server becomes roughly equal. Our evaluation results show that the proposed method is able to balance the load by about 20% better than former algorithms, especially in the peak of search engine traffic.
[1] B. B. Cambazoglu, E. Kayaaslan, S. Jonassen, and C. Aykanat, "A term-based inverted index partitioning model for efficient distributed query processing," ACM Trans. Web, vol. 7, no. 3, pp. 15-23, Sept. 2013.
[2] Y. C. Ma, C. P. Chung, and T. F. Chen, "Load and storage balanced posting file partitioning for parallel information retrieval," J. Syst. Softw., vol. 84, no. 5, pp. 864-884, May 2011.
[3] A. Kulkarni, A. S. Tigelaar, D. Hiemstra, and J. Callan, "Shard ranking and cut off estimation for topically partitioned collections," in Proc. of the 21st ACM Int. Conf. on Information and Knowledge Management, pp. 555-564, Hawaii, USA, 1-2 Nov. 2012.
[4] A. Moffat, W. Webber, J. Zobel, and R. Baeza-Yates, "A pipelined architecture for distributed text query evaluation," Inf. Retr. Boston., vol. 10, no. 3, pp. 205-231, Jun. 2007.
[5] A. Kulkarni, J. Teevan, K. M. Svore, and S. T. Dumais, "Understanding temporal query dynamics," in Proc. of the 4th ACM Int. Conf. on Web Search and Data Mining, WSDM'11, pp. 167-176, Hong Kong, China, 9-12 Feb. 2011.
[6] K. M. Risvik and R. Michelsen, "Search engines and web dynamics," Comput. Networks, vol. 39, no. 3, pp. 289-302, Jun. 2002.
[7] S. Brin and L. Page, "The anatomy of a large-scale hypertextual web search engine," Computer Networks ISDN Syst., vol. 30, no. 1-7, pp. 107-117, Apr. 1998.
[8] A. Moffat, W. Webber, and J. Zobel, "Load balancing for term-distributed parallel retrieval," in Proc. of the 29th Annual ACM SIGIR Int. Conf. on Research and Development in Information Retrieval, pp. 348-355, Seattle, USA, 6-11Aug. 2006.
[9] D. Puppin, F. Silvestri, R. Perego, and R. Baeza-Yates, "Tuning the capacity of search engines: load-driven routing and incremental caching to reduce and balance the load," ACM Trans. Inf. Syst., vol. 28, no. 2, pp. 1-36, May 2010.
[10] C. Lucchese, S. Orlando, R. Perego, and F. Silvestri, "Mining query logs to optimize index partitioning in parallel web search engines," in Proc. of the 2nd Int. Conf. on Scalable Information Systems, pp. 43-52, Suzhou, China, 6-8 Jun. 2007.
[11] A. Kulkarni and J. Callan, "Selective search: efficient and effective search of large textual collections," ACM Trans. Inf. Syst., vol. 33, no. 4, pp. 1-33, Apr. 2015.
[12] A. Kulkarni, A. S. Tigelaar, D. Hiemstra, and J. Callan, "Shard ranking and cutoff estimation for topically partitioned collections," in Proc. of the 21st ACM International Conf. on Information and Knowledge Management, pp. 555-564, Hawaii, USA, 1-2 Nov. 2012.
[13] Y. Kim, J. Callan, J. S. Culpepper, and A. Moffat, "Load-balancing in distributed selective search," in Proc. of the 39th ACM SIGIR Int. Conf. on Research and Development in Information Retrieval, pp. 905-908, Pisa, Italy, 17-21 Jul. 2016.
[14] Z. Dai, C. Xiong, and J. Callan, "Query-biased partitioning for selective search," in Proc. of the 25th ACM International Conf. on Information and Knowledge Management, pp. 1119-1128, New York, USA, 24-28 Oct. 2016.
[15] Y. Kim, J. Callan, J. S. Culpepper, and A. Moffat, "Efficient distributed selective search," Information Retrieval J., vol. 20, no. 3, pp. 221-252, Jun. 2017.
[16] A. Kane and F. W. Tompa, "Small-term distribution for disk-based search," in Proc. of the ACM Symposium on Document Engineering, New York, USA, 4-7 Sept. 2017.
[17] S. Jonassen and S. E. Bratsberg, "Impact of the query model and system settings on performance of distributed inverted indexes," in Proc. of the 22nd Norwegian Informatics Conf., NIK'09, pp. 143-154, Oslo, Norway, 25-27 Nov. 2009.
[18] B. Ribeiro-Neto, E. S. Moura, M. S. Neubert, and N. Ziviani, "Efficient distributed algorithms to build inverted files," in Proc. of the 22nd Annual International ACM SIGIR Conf. on Research and Development in Information Retrieval, pp. 105-112, Berkeley, USA, 15-19 Aug. 1999.
[19] Z. Dai, C. Xiong, and J. Callan, "Query-biased partitioning for selective search," in Proc. of the 25th ACM Int. on Conf. on Information and Knowledge Management, pp. 1119-1128, New York, USA, 24-28 Oct. 2016.
[20] H. Patel, Inverted Index Partitioning Strategies for a Distributed Search Engine, University of Waterloo, 2010.
[21] Z. Gyongyi and H. Garcia-Molina, Web Spam Taxonomy, Stanford University, 2005.
[22] J. Zhou and T. Yang, "Selective early request termination for busy internet services," in Proc. of the 15th Int. Conf. on World Wide Web-WWW'06, pp. 605-614, Edinburgh, Scotland, 23-26 May 2006.
[23] K. Sparck Jones, "A statistical interpretation of term specificity and its application in retrieval," J. Doc., vol. 28, no. 1, pp. 11-21, Jan. 1972.
[24] Apache Lucene, Welcome to Apache Lucene, Apache Foundation, 2018. [Online]. Available: http://lucene.apache.org/.