Automatic classification of Web queries using very large unlabeled query logs

ABSTRACT

Accurate topical classification of user queries allows for increased effectiveness and efficiency in general-purpose Web search systems. Such classification becomes critical if the system must route queries to a subset of topic-specific and resource-constrained back-end databases. Successful query classification poses a challenging problem, as Web queries are short, thus providing few features. This feature sparseness, coupled with the constantly changing distribution and vocabulary of queries, hinders traditional text classification. We attack this problem by combining multiple classifiers, including exact lookup and partial matching in databases of manually classified frequent queries, linear models trained by supervised learning, and a novel approach based on mining selectional preferences from a large unlabeled query log. Our approach classifies queries without using external sources of information, such as online Web directories or the contents of retrieved pages, making it viable for use in demanding operational environments, such as large-scale Web search services. We evaluate our approach using a large sample of queries from an operational Web search engine and show that our combined method increases recall by nearly 40% over the best single method while maintaining adequate precision. Additionally, we compare our results to those from the 2005 KDD Cup and find that we perform competitively despite our operational restrictions. This suggests it is possible to topically classify a significant portion of the query stream without requiring external sources of information, allowing for deployment in operationally restricted environments.

REFERENCES

• 1: Jean-Marc Adamo, Data mining for association rules and sequential patterns: sequential and parallel algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 2: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 3: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Hourly analysis of a very large topically categorized web query log, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009048]
• 4: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David D. Lewis , Abdur Chowdhury , Aleksander Kolcz, Improving Automatic Query Classification via Semi-Supervised Learning, Proceedings of the Fifth IEEE International Conference on Data Mining, p.42-49, November 27-30, 2005 [doi>10.1109/ICDM.2005.80]
• 5: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David Grossman , David D. Lewis , Abdur Chowdhury , Aleksandr Kolcz, Automatic web query classification using labeled and unlabeled training data, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076138]
• 6: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , Ophir Frieder , David Grossman, Temporal analysis of a very large topically categorized Web query log, Journal of the American Society for Information Science and Technology, v.58 n.2, p.166-178, January 2007 [doi>10.1002/asi.v58:2]
• 7: Razvan Stefan Bot , Yi-fang Brook Wu , Xin Chen , Quanzhi Li, Generating better concept hierarchies using automatic document classification, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099627]
• 8: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 9: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Proceedings of the seventh international conference on World Wide Web 7, p.161-172, April 1998, Brisbane, Australia
• 10: Abdur Chowdhury , Greg Pass, Operational requirements for scalable search systems, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956945]
• 11: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 12: Craswell, N. and Hawking, D. 2004. Overview of the trec 2004 Web track. In Proceedings of the Thirteenth Text Retrieval Conference (TREC 2004). NIST, Gaithersburg, MD. 89--97.
• 13: Craswell, N., Hawking, D., Wilkinson, R., and Wu, M. 2003. Overview of the TREC 2003 Web track. In Proceedings of the Twelfth Text Retrieval Conference (TREC 2003). NIST, Gaithersburg, MD, 78--92.
• 14: Fernando Das-Neves , Edward A. Fox , Xiaoyan Yu, Connecting topics in document collections with stepping stones and pathways, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099573]
• 15: Caroline M. Eastman , Bernard J. Jansen, Coverage, relevance, and ranking: The impact of query operators on Web search engine results, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.383-411, October 2003 [doi>10.1145/944012.944015]
• 16: Eric J. Glover , Steve Lawrence , William P. Birmingham , C. Lee Giles, Architecture of a metasearch engine that supports user information needs, Proceedings of the eighth international conference on Information and knowledge management, p.210-216, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319980]
• 17: Luis Gravano , Vasileios Hatzivassiloglou , Richard Lichtenstein, Categorizing web queries according to geographical locality, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956925]
• 18: David A. Grossman , Ophir Frieder, Information Retrieval: Algorithms and Heuristics, Kluwer Academic Publishers, Norwell, MA, 1998
• 19: 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]
• 20: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 21: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 22: In-Ho Kang , GilChang Kim, Query type classification for web document retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860449]
• 23: Zsolt T. Kardkovács , Domonkos Tikk , Zoltán Bánsághi, The Ferrety algorithm for the KDD Cup 2005 problem, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.111-116, December 2005 [doi>10.1145/1117454.1117468]
• 24: Kowalczyk, P., Zukerman, I., and Niemann, M. 2004. Analyzing the effect of query class on document retrieval performance. In 17th Australian Joint Conference on Artificial Intelligence (AI-04). Springer-Verlag, Berlin, Germany, 550--561.
• 25: Krauth, W. and Mezard, M. 1987. Learning algorithms with optimal stability in neural networks. J. Phys. A 20, 745--752.
• 26: Lawrence, S. and Giles, C. L. 1998. Searching the World Wide Web Science, 98--100.
• 27: David D. Lewis, Evaluating and optimizing autonomous text classification systems, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.246-254, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215366]
• 28: Yaoyong Li , Hugo Zaragoza , Ralf Herbrich , John Shawe-Taylor , Jaz S. Kandola, The Perceptron Algorithm with Uneven Margins, Proceedings of the Nineteenth International Conference on Machine Learning, p.379-386, July 08-12, 2002
• 29: Light, M. and Greiff, W. 2002. Statistical models for the induction and use of selectional preferences. Cog. Sci. 26, 3 269--281.
• 30: R. Manmatha , Ao Feng , James Allan, A critical examination of TDT's cost function, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564465]
• 31: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 32: Martin, A., Doddington, G., Kamm, T., Ordowski, M., and Przybocki, M. 1997. The DET curve in assessment of detection task performance. In Proceedings of the 5th ESCA Conference on Speech Communication and Technology (Eurospeech '97), (Sept.). 1895--1898.
• 33: Diana McCarthy , John Carroll, Disambiguating Nouns, Verbs, and Adjectives Using Automatically Acquired Selectional Preferences, Computational Linguistics, v.29 n.4, p.639-654, December 2003 [doi>10.1162/089120103322753365]
• 34: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 35: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 36: Philip Stuart Resnik, Selection and information: a class-based approach to lexical relationships, University of Pennsylvania, Philadelphia, PA, 1993
• 37: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 38: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 39: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 40: Amanda Spink , Bernard J. Jansen, Web Search: Public Searching of the Web (Information Science and Knowledge Management), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 41: Amanda Spink , Bernard J. Jansen , Dietmar Wolfram , Tefko Saracevic, From E-Sex to E-Commerce: Web Search Changes, Computer, v.35 n.3, p.107-109, March 2002 [doi>10.1109/2.989940]
• 42: Amanda Spink , Seda Ozmutlu , Huseyin C. Ozmutlu , Bernard J Jansen, U.S. versus European web searching trends, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792555]
• 43: Amanda Spink , Dietmar Wolfram , Major B. J. Jansen , Tefko Saracevic, Searching the Web: the public and their queries, Journal of the American Society for Information Science and Technology, v.52 n.3, p.226-234, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1591>3.3.CO;2-I]
• 44: Sullivan, D. 2006. Searches per day. Search Engine Watch. Go online to http://searchenginewatch.com/reports/article.php/2156461.
• 45: Tague, J. M. 1981. The pragmatics of information retrieval experimentation. In Information Retrieval Experiment, K. S. Jones, Ed. Butterworth-Heinemann, London, U.K. 59--102.
• 46: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 47: David Vogel , Steffen Bickel , Peter Haider , Rolf Schimpfky , Peter Siemen , Steve Bridges , Tobias Scheffer, Classifying search engine queries using the web as background knowledge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.117-122, December 2005 [doi>10.1145/1117454.1117469]
• 48: Voorhees, E. M. 2004. Overview of the TREC 2004 question answering track. In Proceedings of the Thirteenth Text Retrieval Conference (TREC 2004, Nov.). NIST, Gaitheraburg, MD.
• 49: Ji-Rong Wen , Jian-Yun Nie , Hong-Jiang Zhang, Clustering user queries of a search engine, Proceedings of the 10th international conference on World Wide Web, p.162-168, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371974]
• 50: Ji-Rong Wen , Jian-Yun Nie , Hong-Jiang Zhang, Query clustering using content words and user feedback, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.442-443, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384083]
• 51: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation