An optimization framework for query recommendation

Query recommendations are an integral part of modern search engines. Their goal is to facilitate users ’ search tasks, as well as help them discover and explore concepts related to their information needs. In this paper, we present a formal treatment of the problem of query recommendation. In our framework we model the user-querying behavior by a proba-bilistic reformulation graph, or query-flow graph [Boldi et al. CIKM 2008], so that the sequence of queries submitted by a user can be seen as a path on this graph. Assigning score values to queries allows us to define suitable utility functions and to consider the expected utility achieved by performing a random walk on the query-flow graph. Furthermore, pro-viding recommendations can be seen as adding shortcuts in the query-flow graph that “nudge ” the reformulation paths of users, in such a way that users are more likely to follow paths with larger expected utility. We discuss in detail the most important questions that come up in the proposed framework. In particular, we pro-vide examples of meaningful utility functions to optimize, we discuss how to estimate the effect of recommendations on the reformulation probabilities, we address the complex-ity of the optimization problems we consider, and we suggest efficient algorithmic solutions. We validate our models and algorithms with extensive experimentation