Mining broad latent query aspects from search sessions

ABSTRACT

Search queries are typically very short, which means they are often underspecified or have senses that the user did not think of. A broad latent query aspect is a set of keywords that succinctly represents one particular sense, or one particular information need, that can aid users in reformulating such queries. We extract such broad latent aspects from query reformulations found in historical search session logs. We propose a framework under which the problem of extracting such broad latent aspects reduces to that of optimizing a formal objective function under constraints on the total number of aspects the system can store, and the number of aspects that can be shown in response to any given query. We present algorithms to find a good set of aspects, and also to pick the best k aspects matching any query. Empirical results on real-world search engine logs show significant gains over a strong baseline that uses single-keyword reformulations: a gain of 14% and 23% in terms of human-judged accuracy and click-through data respectively, and around 20% in terms of consistency among aspects predicted for "similar" queries. This demonstrates both the importance of broad query aspects, and the efficacy of our algorithms for extracting them.

REFERENCES

• 1: J. A. Aslam, E. Pelekov, and D. Rus. The star clustering algorithm for static and dynamic information organization. Journal of Graph Algorithms and Applications, 8(1):95--129, 2004.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Bodo Billerbeck , Falk Scholer , Hugh E. Williams , Justin Zobel, Query expansion using associated queries, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956866]
• 4: Paolo Boldi , Francesco Bonchi , Carlos Castillo , Debora Donato , Aristides Gionis , Sebastiano Vigna, The query-flow graph: model and applications, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458163]
• 5: Chris Buckley , Gerard Salton, Optimization of relevance feedback weights, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.351-357, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215383]
• 6: Huanhuan Cao , Daxin Jiang , Jian Pei , Qi He , Zhen Liao , Enhong Chen , Hang Li, Context-aware query suggestion by mining click-through and session data, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401995]
• 7: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 8: Steve Chien , Nicole Immorlica, Semantic similarity between search engine queries using temporal correlation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060752]
• 9: Paul - Alexandru Chirita , Claudiu S. Firan , Wolfgang Nejdl, Personalized query expansion for the web, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277746]
• 10: Nick Craswell , Onno Zoeter , Michael Taylor , Bill Ramsey, An experimental comparison of click position-bias models, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341545]
• 11: S. Cucerzan and E. Brill. Extracting semantically related queries by exploiting user session information. http://research.
• 12: microsoft.com/users/silviu/Papers/np-www06.pdf.
• 13: Hang Cui , Ji-Rong Wen , Jian-Yun Nie , Wei-Ying Ma, Probabilistic query expansion using query logs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511489]
• 14: Bruno M. Fonseca , Paulo Golgher , Bruno Pôssas , Berthier Ribeiro-Neto , Nivio Ziviani, Concept-based interactive query expansion, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099726]
• 15: Ariel Fuxman , Panayiotis Tsaparas , Kannan Achan , Rakesh Agrawal, Using the wisdom of the crowds for keyword generation, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367506]
• 16: Bernard J. Jansen , Amanda Spink , Jan Pedersen, A temporal comparison of AltaVista Web searching: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.6, p.559-570, April 2005 [doi>10.1002/asi.v56:6]
• 17: Rosie Jones , Kristina Lisa Klinkner, Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458176]
• 18: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 19: M. Pasca and B. V. Durme. Weakly-supervised acquisition of open-domain classes and class attributes from web documents and query logs. In ACL, pages 19--27, 2008.
• 20: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 21: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 22: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 23: Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
latent user intent, query aspects, search sessions