Term-level semantic similarity helps time-aware term popularity based query completion.

Query completion service, normally known in the form of query auto completion (QAC) and widely provided by common search engines, assists users to formulate their queries after only typing few keystrokes. Previous work on QAC basically ranks query candidates according to their query popularity which is collected from the search logs, ignoring the internal semantic similarity between terms inside a query. However, we argue semantically related terms are apt to be combined when generating a query. In addition, as users often engage in QAC at word boundary (i.e., after typing a full word), we suppose that the time-aware popularity of the first word in a query candidate could affect the ranking of QAC candidates. Hence, based on the Markov assumption, we propose a new QAC ranking method, which models the QAC engagement as a Markov Chain and takes the semantic similarity between query terms into account. We contrast our proposed model with the traditional query popularity-based QAC approaches and verify its effectiveness in terms of Mean Reciprocal Rank (MRR). The experimental results show that our model significantly outperforms the baselines, achieving an average MRR improvement around 4% over the baselines. [ABSTRACT FROM AUTHOR]