Query suggestion using hitting time

ABSTRACT

Generating alternative queries, also known as query suggestion, has long been proved useful to help a user explore and express his information need. In many scenarios, such suggestions can be generated from a large scale graph of queries and other accessory information, such as the clickthrough. However, how to generate suggestions while ensuring their semantic consistency with the original query remains a challenging problem.

In this work, we propose a novel query suggestion algorithm based on ranking queries with the hitting time on a large scale bipartite graph. Without involvement of twisted heuristics or heavy tuning of parameters, this method clearly captures the semantic consistency between the suggested query and the original query. Empirical experiments on a large scale query log of a commercial search engine and a scientific literature collection show that hitting time is effective to generate semantically consistent query suggestions. The proposed algorithm and its variations can successfully boost long tail queries, accommodating personalized query suggestion, as well as finding related authors in research.

References

1. E. Agichtein, S. Lawrence, and L. Gravano. Learning search engine specific query transformations for question answering. In Proceedings of the 10th international conference on World Wide Web, pages 169--178, 2001.
2. C. Anderson. The Long Tail: Why the Future of Business is Selling Less of More. Hyperion, 2006.
3. R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In EDBT Workshops, pages 588--596, 2004.
4. D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log. In Proceedings of KDD '00, pages 407--416, 2000.
5. S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30(1-7):107--117, 1998.
6. S. Chakrabarti, M. Joshi, and V. Tawde. Enhanced topic distillation using text, markup tags, and hyperlinks. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 208--216, 2001.
7. K. Church and B. Thiesson. The wild thing! In Proceedings of the ACL 2005 on Interactive poster and demonstration sessions, pages 93--96, 2005.
8. K. W. Church and B. Thiesson. The wild thing goes local. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 901--901, 2007.
9. N. Craswell and M. Szummer. Random walks on the click graph. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 239--246, 2007.
10. S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of EMNLP 2004, pages 293--300, 2004.
11. T. Haveliwala, S. Kamvar, and G. Jeh. An analytical comparison of approaches to personalizing pagerank, 2003.
12. T. Joachims, L. Granka, B. Pan, H. Hembrooke, and G. Gay. Accurately interpreting clickthrough data as implicit feedback. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pages 154--161, 2005.
13. R. Jones, B. Rey, O. Madani, and W. Greiner. Generating query substitutions. In Proceedings of the 15th international conference on World Wide Web, pages 387--396, 2006.
14. J. M. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46(5):604--632.
15. M. Li, Y. Zhang, M. Zhu, and M. Zhou. Exploring distributional similarity based models for query spelling correction. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, pages 1025--1032, 2006.
16. Q. Mei and K. Church. Entropy of search logs: how hard is search? with personalization? with backoff? In Proceedings of the international conference on Web search and web data mining, pages 45--54, 2008.
17. F. Radlinski and T. Joachims. Query chains: learning to rank from implicit feedback. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 239--248, 2005.
18. F. Radlinski and T. Joachims. Active exploration for learning rankings from clickthrough data. In Proceedings of KDD' 07, pages 570--579, 2007.
19. D. Shen, T. Walkery, Z. Zhengy, Q. Yangz, and Y. Li. Personal name classification in web queries. In Proceedings of the international conference on Web search and web data mining, pages 149--158, 2008.
20. X. Shen, B. Tan, and C. Zhai. Implicit user modeling for personalized search. In Proceedings of CIKM' 05, pages 824--831, 2005.
21. J.-R. Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine. In Proceedings of WWW '01, pages 162--168, 2001.
22. R. W. White and G. Marchionini. Examining the effectiveness of real-time query expansion. Inf. Process. Manage., 43(3):685--704, 2007.
23. G.-R. Xue, H.-J. Zeng, Z. Chen, Y. Yu, W.-Y. Ma, W. Xi, and W. Fan. Optimizing web search using web click-through data. In Proceedings of CIKM '04, pages 118--126, 2004.
24. C. Zhai and J. Lafferty. Model-based feedback in the language modeling approach to information retrieval. In Proceedings of CIKM' 01, pages 403--410, 2001.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing