Query-url bipartite based approach to personalized query recommendation

Query recommendation is considered an effective assistant in enhancing keyword based queries in search engines and Web search software. Conventional approach to query rec-ommendation has been focused on query-term based analysis over the user access logs. In this paper, we argue that utiliz-ing the connectivity of a query-URL bipartite graph to rec-ommend relevant queries can significantly improve the accu-racy and effectiveness of the conventional query-term based query recommendation systems. We refer to the Query-URL Bipartite based query reCommendation approach as QUBIC. The QUBIC approach has two unique characteristics. First, instead of operating on the original bipartite graph directly using biclique based approach or graph clustering, we extract an affinity graph of queries from the initial query-URL bi-partite graph. The affinity graph consists of only queries as its vertices and its edges are weighted according to a query-URL vector based similarity (distance) measure. By utilizing the query affinity graph, we are able to capture the propa-gation of similarity from query to query by inducing an im-plicit topical relatedness between queries. We devise a novel rank mechanism for ordering the related queries based on the merging distances of a hierarchical agglomerative clustering. We compare our proposed ranking algorithm with both naı̈ve ranking that uses the query-URL similarity measure directly, and the single-linkage based ranking method. In addition, we make it possible for users to interactively participate in the query recommendation process, to bridge the gap between the determinacy of actual similarity values and the indeter-minacy of users ’ information needs, allowing the lists of re-lated queries to be changed from user to user and query to query, thus personalizing the query recommendation on de-mand. The experimental results from two query collections demonstrate the effectiveness and feasibility of our approach. 1