Exploring Query Auto-Completion and Click Logs for Contextual-Aware Web Search and Query Suggestion

ABSTRACT

Contextual data plays an important role in modeling search engine users' behaviors on both query auto-completion (QAC) log and normal query (click) log. User's recent search history on each log has been widely studied individually as the context to benefit the modeling of users' behaviors on that log. However, there is no existing work that explores or incorporates both logs together for contextual data. As QAC and click logs actually record users' sequential behaviors while interacting with a search engine, the available context of a user's current behavior based on the same type of log can be strengthened from the user's recent search history shown on the other type of log. Our paper proposes to model users' behaviors on both QAC and click logs simultaneously by utilizing both logs as the contextual data of each other. The key idea is to capture the correlation between users' behavior patterns on both logs. We model such correlation through a novel probabilistic model based on the Latent Dirichlet allocation (LDA) model. The learned users' behavior patterns on both logs are utilized to address not only the application of query auto-completion on QAC logs, but also the click prediction and relevance ranking of web documents on click logs. Experiments on real-world logs demonstrate the effectiveness of the proposed model on both applications.

References

1. Z. Bar-Yossef and N. Kraus. Context-sensitive query auto-completion. In Proceedings of the 20th international conference on World wide web, pages 107--116. ACM, 2011.
2. H. Bast and I. Weber. Type less, find more: fast autocompletion search with a succinct index. In Proceedings of the 29th annual international ACM SIGIR conference, pages 364--371. ACM, 2006.
3. D. Blei and M. Jordan. Variational inference for dirichlet process mixtures. In Bayesian Analysis, volume 1, pages 121--144, 2005.
4. D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. J. Mach. Learn. Res., 3:993--1022, March 2003.
5. H. Cao, D. Jiang, J. Pei, E. Chen, and H. Li. Towards context-aware search by learning a very large variable length hidden markov model from search logs. In Proceedings of the 18th International Conference on World Wide Web, pages 191--200, 2009.
6. 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 KDD, pages 875--883, 2008.
7. O. Chapelle and Y. Zhang. A dynamic bayesian network click model for web search ranking. In Proceedings of the 18th International Conference on World Wide Web, WWW '09, pages 1--10, New York, NY, USA, 2009. ACM.
8. N. Craswell, O. Zoeter, M. Taylor, and B. Ramsey. An experimental comparison of click position-bias models. In Proceedings of the 2008 International Conference on Web Search and Data Mining, pages 87--94. ACM, 2008.
9. A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological), pages 1--38, 1977.
10. H. Duan and B.-J. P. Hsu. Online spelling correction for query completion. In Proceedings of the 20th international conference on World wide web, pages 117--126. ACM, 2011.
11. G. E. Dupret and B. Piwowarski. A user browsing model to predict search engine click data from past observations. In Proceedings of the 31st annual international ACM SIGIR conference, pages 331--338. ACM, 2008.
12. J. Gao, G. Xu, and J. Xu. Query expansion using path-constrained random walks. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '13, pages 563--572, New York, NY, USA, 2013. ACM.
13. L. A. Granka, T. Joachims, and G. Gay. Eye-tracking analysis of user behavior in www search. In Proceedings of the 27th annual international ACM SIGIR conference, pages 478--479. ACM, 2004.
14. B.-J. P. Hsu and G. Ottaviano. Space-efficient data structures for top-k completion. In Proceedings of the 22nd international conference on World Wide Web, pages 583--594, 2013.
15. J.-Y. Jiang, Y.-Y. Ke, P.-Y. Chien, and P.-J. Cheng. Learning user reformulation behavior for query auto-completion. In Proceedings of the 37th international ACM SIGIR conference, pages 445--454. ACM, 2014.
16. T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, pages 133--142. ACM, 2002.
17. E. Kharitonov, C. Macdonald, P. Serdyukov, and I. Ounis. User model-based metrics for offline query suggestion evaluation. In Proceedings of the 36th international ACM SIGIR conference, pages 633--642. ACM, 2013.
18. L. Li, H. Deng, J. Chen, and Y. Chang. Learning parametric models for context-aware query auto-completion via hawkes processes. WSDM '17, pages 131--139, New York, NY, USA, 2017. ACM.
19. L. Li, H. Deng, A. Dong, Y. Chang, H. Zha, and R. Baeza-Yates. Analyzing user's sequential behavior in query auto-completion via markov processes. SIGIR '15, pages 123--132, New York, NY, USA, 2015. ACM.
20. Y. Li, A. Dong, H. Wang, H. Deng, Y. Chang, and C. Zhai. A two-dimensional click model for query auto-completion. In Proceedings of the 37th International ACM SIGIR Conference, pages 455--464. ACM, 2014.
21. C. Liu, F. Guo, and C. Faloutsos. Bayesian browsing model: Exact inference of document relevance from petabyte-scale data. ACM Transactions on Knowledge Discovery from Data (TKDD), 4(4):19, 2010.
22. M. Melucci. Contextual search: A computational framework. Foundations and Trends in Information Retrieval, 6(4--5):257--405, 2012.
23. M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: estimating the click-through rate for new ads. In Proceedings of the 16th international conference on World Wide Web, pages 521--530. ACM, 2007.
24. X. Shen, B. Tan, and C. Zhai. Context-sensitive information retrieval using implicit feedback. In Proceedings of the 28th international ACM SIGIR conference, pages 43--50, 2005.
25. M. Shokouhi. Learning to personalize query auto-completion. In Proceedings of the 36th international ACM SIGIR conference, pages 103--112. ACM, 2013.
26. M. Shokouhi and K. Radinsky. Time-sensitive query auto-completion. In Proceedings of the 35th international ACM SIGIR conference, pages 601--610. ACM, 2012.
27. A. Sun and C. Lou. Towards context-aware search with right click. In The 37th International ACM SIGIR Conference, pages 847--850, 2014.
28. H. Wang, C. Zhai, A. Dong, and Y. Chang. Content-aware click modeling. In Proceedings of the 22Nd International Conference on World Wide Web, WWW '13, pages 1365--1376, 2013.
29. S. Wang, Y. Wang, J. Tang, C. Aggarwal, S. Ranganath, and H. Liu. Exploiting hierarchical structures for unsupervised feature selection. SDM, 2017.
30. Y. Wang, S. Wang, J. Tang, G. Qi, H. Liu, and B. Li. Clare:a joint approach to label classification and tag recommendation. AAAI, 2017.
31. S. Whiting and J. M. Jose. Recent and robust query auto-completion. In Proceedings of the 23rd international conference on World wide web, pages 971--982, 2014.
32. Y. Zhang, W. Chen, D. Wang, and Q. Yang. User-click modeling for understanding and predicting search-behavior. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1388--1396. ACM, 2011.
33. Z. A. Zhu, W. Chen, T. Minka, C. Zhu, and Z. Chen. A novel click model and its applications to online advertising. In Proceedings of the third ACM international conference on Web search and data mining, pages 321--330. ACM, 2010.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Topic modeling

• Information systems

  • Information retrieval

    • Information retrieval query processing

    • Retrieval models and ranking