The wisdom of advertisers: mining subgoals via query clustering

ABSTRACT

This paper tackles the problem of mining subgoals of a given search goal from data. For example, when a searcher wants to travel to London, she may need to accomplish several subtasks such as "book flights," "book a hotel," "find good restaurants" and "decide which sightseeing spots to visit." As another example, if a searcher wants to lose weight, there may exist several alternative solutions such as "do physical exercise," "take diet pills," and "control calorie intake." In this paper, we refer to such subtasks or solutions as subgoals, and propose to utilize sponsored search data for finding subgoals of a given query by means of query clustering. Advertisements (ads) reflect advertisers' tremendous efforts in trying to match a given query with implicit user needs. Moreover, ads are usually associated with a particular action or transaction. We therefore hypothesized that they are useful for subgoal mining. To our knowledge, our work is the first to use sponsored search data for this purpose. Our experimental results show that sponsored search data is a good resource for obtaining related queries and for identifying subgoals via query clustering. In particular, our method that combines ad impressions from sponsored search data and query co-occurrences from session data outperforms a state-of-the-art query clustering method that relies on document clicks rather than ad impressions in terms of purity, NMI, Rand Index, F1-measure and subgoal recall.

References

1. L. M. Aiello, D. Donato, U. Ozertem, and F. Menczer. Behavior-driven clustering of queries into topics. In Proc. of CIKM, pages 1373--1382, 2011.
2. R. Baeza-Yates, C. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In Current Trends in Database Technology-EDBT 2004 Workshops, pages 588--596, 2004.
3. D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log. In Proc. of KDD, pages 407--416, 2000.
4. P. Boldi, F. Bonchi, C. Castillo, D. Donato, A. Gionis, and S. Vigna. The query-flow graph: model and applications. In Proc. of CIKM, pages 609--618, 2008.
5. A. Broder. A taxonomy of web search. ACM SIGIR Forum, 36(2):3--10, 2002.
6. A. Broder, P. Ciccolo, M. Fontoura, E. Gabrilovich, V. Josifovski, and L. Riedel. Search advertising using web relevance feedback. In Proc. of CIKM, pages 1013--1022, 2008.
7. G. Buscher, S. T. Dumais, and E. Cutrell. The good, the bad, and the random: an eye-tracking study of ad quality in web search. In Proc. of SIGIR, pages 42--49, 2010.
8. H. Cao, D. Jiang, J. Pei, Q. He, Z. Liao, E. Chen, and H. Li. Context-aware query suggestion by mining click-through and session data. In Proc. of KDD, pages 875--883, 2008.
9. H. K. Dai, L. Zhao, Z. Nie, J.-R. Wen, L.Wang, and Y. Li. Detecting online commercial intention (OCI). In Proc. of WWW, pages 829--837, 2006.
10. C. Danescu-Niculescu-Mizil, A. Z. Broder, E. Gabrilovich, V. Josifovski, and B. Pang. Competing for users' attention: on the interplay between organic and sponsored search results. In Proc. of WWW, pages 291--300, 2010.
11. D. Donato, F. Bonchi, T. Chi, and Y. Maarek. Do you want to take notes?: identifying research missions in Yahoo! search pad. In Proc. of WWW, pages 321--330, 2010.
12. J. Fleiss and J. Cohen. The equivalence of weighted kappa and the intraclass correlation coefficient as measures of reliability. Educational and Psychological Measurement, 1973.
13. B. M. Fonseca, P. Golgher, B. Pôssas, B. Ribeiro-Neto, and N. Ziviani. Concept-based interactive query expansion. In Proc. of CIKM, pages 696--703, 2005.
14. T. Graepel, J. Candela, T. Borchert, and R. Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in Microsoft's Bing search engine. In Proc. of ICML, pages 13--20, 2010.
15. Q. Guo and E. Agichtein. Ready to buy or just browsing?: detecting web searcher goals from interaction data. In Proc. of SIGIR, pages 130--137, 2010.
16. D. Hillard, S. Schroedl, E. Manavoglu, H. Raghavan, and C. Leggetter. Improving ad relevance in sponsored search. In Proc. of WSDM, pages 361--370, 2010.
17. B. J. Jansen. The comparative effectiveness of sponsored and nonsponsored links for web e-commerce queries. ACM Transactions on the Web, 1(3), 2007.
18. B. J. Jansen, D. Booth, and A. Spink. Determining the informational, navigational, and transactional intent of web queries. Information Processing & Management, 44(3):1251--1266, 2008.
19. B. J. Jansen and M. Resnick. Examining searcher perceptions of and interactions with sponsored results. In Workshop on Sponsored Search Auctions, 2005.
20. K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems, 20(4):422--446, 2002.
21. R. Jones and K. L. Klinkner. Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs. In Proc. of CIKM, pages 699--708, 2008.
22. I. Kang and G. Kim. Query type classification for web document retrieval. In Proc. of SIGIR, pages 64--71, 2006.
23. E. Kanoulas, B. Carterette, P. D. Clough, and M. Sanderson. Evaluating multi-query sessions. In Proc. of SIGIR, pages 1053--1062, 2011.
24. Y. Liu, X. Ni, J.-T. Sun, and Z. Chen. Unsupervised transactional query classification based on webpage form understanding. In Proc. of CIKM, pages 57--66, 2011.
25. C. D. Manning, P. Raghavan, and H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008.
26. M. P. Kato, T. Sakai, and K. Tanaka. Structured query suggestion for specialization and parallel movement: effect on search behaviors. In Proc. of WWW, pages 389--398, 2012.
27. F. Radlinski, A. Broder, P. Ciccolo, E. Gabrilovich, V. Josifovski, and L. Riedel. Optimizing relevance and revenue in ad search: a query substitution approach. In Proc. of SIGIR, pages 403--410, 2008.
28. E. Sadikov, J. Madhavan, L. Wang, and A. Halevy. Clustering query refinements by user intent. In Proc. of WWW, pages 841--850, 2010.
29. X. Wang, D. Chakrabarti, and K. Punera. Mining broad latent query aspects from search sessions. In Proc. of KDD, pages 867--876, 2009.
30. J.-R.Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine. In Proc. of WWW, pages 162--168, 2001.
31. R. White and R. Roth. Exploratory search: Beyond the query-response paradigm. Synthesis Lectures on Information Concepts, Retrieval, and Services, 1(1):1--98, 2009.
32. W. Xu, E. Manavoglu, and E. Cantu-Paz. Temporal click model for sponsored search. In Proc. of SIGIR, pages 106--113, 2010.

Index Terms

• Information systems

  • Information retrieval