Efficient interactive query expansion with complete search

Abstract

We present an efficient realization of the following interactive search engine \nfeature: as the user is typing the query, words that are related to the last \nquery word and that would lead to good hits are suggested, as well as selected \nsuch hits. The realization has three parts: (i) building clusters of related \nterms, (ii) adding this information as artificial words to the index such that \n(iii) the described feature reduces to an instance of prefix search and \ncompletion. An efficient solution for the latter is provided by the \nCompleteSearch engine, with which we have integrated the proposed feature. For \nbuilding the clusters of related terms we propose a variant of latent semantic \nindexing that, unlike standard approaches, is completely transparent to the \nuser. By experiments on two large test-collections, we demonstrate that the \nfeature is provided at only a slight increase in query processing time and \nindex size.