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

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 vo-cabulary 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 distribu-tion of terms in user queries, finding an effective partitioning strategy is considered a very complex task. In this paper we first formally introduce Term Partition-ing as a new optimization problem. Then we show how the knowledge mined from past WSE query logs can be prof-itably used to discover good solutions of this problem. Fi-nally, we report many results to show that we are able to effectively reduce both the average number of servers acti-vated per each query, along with the workload imbalance. Experiments are conducted on large query logs of real WSEs