Search shortcuts: a new approach to the recommendation of queries

ABSTRACT

The recommendation of queries, known as query suggestion, is a common practice on major Web Search Engines. It aims to help users to find the information they are looking for, and is usually based on the knowledge learned from past interactions with the search engine. In this paper we propose a new model for query suggestion, the Search Shortcut Problem, that consists in recommending "successful" queries that allowed other users to satisfy, in the past, similar information needs. This new model has several advantages with respect to traditional query suggestion approaches. First, it allows a straightforward evaluation of algorithms from available query log data. Moreover, it simplifies the application of several recommendation techniques from other domains. Particularly, in this work we applied Collaborative Filtering to this problem, and evaluated the interesting results achieved on large query logs from AOL and Microsoft. Different techniques for analyzing and extracting information from query logs, as well as new metrics and techniques for measuring the effectiveness of recommendations are proposed and evaluated. The results obtained clearly show the importance of several of our contributions, and open an interesting field for future research.

REFERENCES

• 1: E. Agichtein, E. Brill, and S. Dumais. Improving web search ranking by incorporating user behavior information. In Proceedings of the 29th annual international ACM SIGIR 2006 Conference, pages 19--26, New York, NY, USA, 2006. ACM.
• 2: R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In W. Lindner, M. Mesiti, C. T Aijrker, Y. Tzitzikas, and A. Vakali, editors, Current trends in database technology -- EDBT 2004 workshops, volume 3268 of LNCS, pages 588--596. Springer, 2004.
• 3: E. Balfe and B. Smyth. Improving web search through collaborative query recommendation. In R. L. de Mantaras and L. Saitta, editors, Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI'2004, pages 268--272. IOS Press, 2004.
• 4: J. S. Breese, D. Heckerman, and C. M. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In G. F. Cooper and S. Moral, editors, Proceedings of the 14th annual UAI conference, pages 43--52. Morgan Kaufmann, 1998.
• 5: J. Canny. Collaborative filtering with privacy via factor analysis. In Proceedings of the 25th annual international ACM SIGIR 2002 Conference, pages 238--245, New York, NY, USA, 2002. ACM.
• 6: H. Cui, J.-R. Wen, J.-Y. Nie, and W.-Y. Ma. Probabilistic query expansion using query logs. In Proceedings of the 11th international WWW Conference, pages 325--332, New York, NY, USA, 2002. ACM.
• 7: B. M. Fonseca, P. B. Golgher, E. S. de Moura, and N. Ziviani. Using association rules to discover search engines related queries. In Proceedings of the First LA-WEB 2003 Conference, page 66, Washington, DC, USA, 2003. IEEE Computer Society.
• 8: V. Formoso, F. Cacheda, and V. Carneiro. Comparison of collaborative filtering algorithms: limitations of current techniques and proposals for scalable, high-performance recommender systems. Submitted to the ACM Transactions on the Web, 2008.
• 9: J. Herlocker, J. A. Konstan, and J. Riedl. An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms. Inf. Retr., 5(4):287--310, 2002.
• 10: J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl. Evaluating collaborative filtering recommender systems. ACM Trans. Inf. Syst., 22(1):5--53, 2004.
• 11: Z. Huang, H. Chen, and D. Zeng. Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering. ACM Trans. Inf. Syst., 22(1):116--142, 2004.
• 12: R. Jones, B. Rey, O. Madani, and W. Greiner. Generating query substitutions. In Proceedings of the 15th international WWW 2006 Conference, pages 387--396, New York, NY, USA, 2006. ACM Press.
• 13: D. Lemire and A. Maclachlan. Slope one predictors for online rating-based collaborative filtering. In Proceedings of SIAM Data Mining (SDM'05), 2005.
• 14: G. Pass, A. Chowdhury, and C. Torgeson. A picture of search. In Proceedings of the 1st Infoscale 2006 Conference, page 1, New York, NY, USA, 2006. ACM.
• 15: D. Pennock, E. Horvitz, S. Lawrence, and C. L. Giles. Collaborative filtering by personality diagnosis: A hybrid memory- and model-based approach. In Proceedings of the 16th UAI 2000 Conference, pages 473--480, Stanford, CA, 2000.
• 16: M. F. Porter. An algorithm for suffix stripping. pages 313--316, 1997.
• 17: F. Radlinski and T. Joachims. Query chains: learning to rank from implicit feedback. In Proceedings of the 11th acm SIGKDD 2005 Conference, pages 239--248, New York, NY, USA, 2005. ACM Press.
• 18: J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd ICML 2005 Conference, pages 713--719, New York, NY, USA, 2005. ACM.
• 19: B. Sarwar, G. Karypis, J. Konstan, and J. Reidl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international WWW 2001 Conference, pages 285--295, New York, NY, USA, 2001. ACM.
• 20: A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock. Methods and metrics for cold-start recommendations. In Proceedings of the 25th annual international ACM SIGIR 2002 Conference, pages 253--260, New York, NY, USA, 2002. ACM.
• 21: U. Shardanand and P. Maes. Social information filtering: algorithms for automating "word of mouth". In Proceedings of the SIGCHI 1995, pages 210--217, New York, NY, USA, 1995. ACM Press/Addison-Wesley Publishing Co.
• 22: B. Smyth. A community-based approach to personalizing web search. Computer, 40(8):42--50, 2007.
• 23: B. Smyth, E. Balfe, O. Boydell, K. Bradley, P. Briggs, M. Coyle, and J. Freyne. A live-user evaluation of collaborative web search. In In IJCAI, pages 1419--1424, 2005.
• 24: L. Ungar and D. Foster. Clustering methods for collaborative filtering. In Proceedings of the Workshop on Recommendation Systems. AAAI Press, Menlo Park California, 1998.
• 25: J. Wang, A. P. de Vries, and M. J. T. Reinders. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29th annual international ACM SIGIR 2006 Conference, pages 501--508, New York, NY, USA, 2006. ACM.
• 26: J.-R. Wen, J.-Y. Nie, and H.-J. Zhang. Clustering user queries of a search engine. In Proceedings of the WWW10, pages 162--168, New York, NY, USA, 2001. ACM Press.
• 27: R. W. White, M. Bilenko, and S. Cucerzan. Leveraging popular destinations to enhance web search interaction. ACM Trans. Web, 2(3):1--30, 2008.
• 28: O. R. Zaffiane and A. Strilets. Finding similar queries to satisfy searches based on query traces. In J.-M. Bruel and Z. Bellahsene, editors, OOIS Workshops, volume 2426 of LNCS, pages 207--216. Springer, 2002.
• 29: Z. Zhang and O. Nasraoui. Mining search engine query logs for query recommendation. In Proceedings of the 15th international WWW 2006 conference, pages 1039--1040, New York, NY, USA, 2006. ACM.
• 30: C.-N. Ziegler, S. M. McNee, J. A. Konstan, and G. Lausen. Improving recommendation lists through topic diversification. In Proceedings of the 14th international WWW 2005 conference, pages 22--32, New York, NY, USA, 2005. ACM.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Experimentation, Theory

Keywords:
collaborative filtering, evaluation, query suggestion model, search shortcut