Generating query substitutions

Authors:

Abstract
We introduce the notion of query substitution, that is, gen- erating a new query to replace a user's original search query. Our technique uses modications based on typical substitu- tions web searchers make to their queries. In this way the new query is strongly related to the original query, contain- ing terms closely related to all of the original terms. This contrasts with query expansion through pseudo-relevance feedback, which is costly and can lead to query drift. This also contrasts with query relaxation through boolean or TFIDF retrieval, which reduces the specicit y of the query. We de- ne a scale for evaluating query substitution, and show that our method performs well at generating new queries related to the original queries. We build a model for selecting be- tween candidates, by using a number of features relating the query-candidate pair, and by tting the model to human judgments of relevance of query suggestions. This further improves the quality of the candidates generated. Experi- ments show that our techniques signican tly increase cover- age and eectiv eness in the setting of sponsored search.