Clustering Related Queries Based on User Intent

October 13, 2010

Posted by Jayant Madhavan and Alon Halevy

People today use search engines for all their information needs, but when they pose a particular search query, they typically have a specific underlying intent. However, when looking at any query in isolation, it might not entirely be clear what the underlying intent is. For example, when querying for mars, a user might be looking for more information about the planet Mars, or the planets in the solar system in general, or the Mars candy bar, or Mars the Roman god of war. The ambiguity in intent is most pronounced for queries that are inherently ambiguous and for queries about prominent entities about which there are various different types of information on the Internet. Given such ambiguity, modern search engines try to complement their search results with lists of related queries that can be used to further explore a particular intent.

In a recent paper, we explored the problem of clustering the related queries as a means of understanding the different intents underlying a given user query. We propose an approach that combines an analysis of anonymized document-click logs (what results do users click on) and query-session logs (what sequences of queries do users pose in a search session). We model typical user search behavior as a traversal of a graph whose nodes are related queries and clicked documents. We propose that the nodes in the graph, when grouped based on the probability of a typical user visiting them within a single search session, yield clusters that correspond to distinct user intents.

Our results show that underlying intents (clusters of related queries) almost always correspond to well-understood, high-level concepts. For example, for mars, in addition to re-constructing each of the intents listed earlier, we also find distinct clusters grouping queries about NASA’s missions to the planet, about specific interest in life on Mars, as well as a Japanese comic series, and a grocery chain named Mars. We found that our clustering approach yields better results than earlier approaches that either only used document-click or only query-session information. More details about our proposed approach and an analysis of the resulting clusters can be found in our paper that was presented at the International World Wide Web conference earlier this year.